41 — LLD: LRU Cache with `getRandom()` in O(1)

Google context: Reported in an NYC L4 loop in 2025 with a Hire / Leaning Hire outcome. It is two well-known problems fused into one — LRU Cache (LC 146) plus Insert/Delete/GetRandom (LC 380) — where you cannot solve one with a data structure that breaks the other. The signal is whether you can reason about data-structure composition under O(1) constraints, and whether you can express it cleanly as a class rather than a tangled blob. Google wants to see you recognize which invariants couple the structures, and refactor toward a single coherent abstraction.

Understanding the Problem

You need a cache that behaves like an LRU on get/put (evicting the least-recently-used on overflow), while also supporting delete(key) and getRandom() — both in O(1). The classic LRU relies on a hash map plus a doubly linked list. The classic getRandom relies on a hash map plus a contiguous array with a swap-pop trick. The challenge is that both structures share the same (key, value) records, and every mutation has to keep both of them synchronized — including the index inside the array.

What is this system?

It is a fixed-capacity key-value store. get and put act like any LRU — recently touched entries move to the front, the oldest entry is evicted when capacity is exceeded. On top of that, you can ask for a uniformly random entry or delete any entry by key, both in constant time. Think "session store" or "sampled cache" — workloads where you want LRU-style warmth guarantees but also need to pull samples out for probing, warming, or eviction policies.

Requirements

Clarifying Questions

You: To confirm the operations — get(key), put(key, value), delete(key), and getRandom(). All O(1) worst case or amortized?

Interviewer: get, put, delete are O(1) worst case. getRandom is O(1) with uniform distribution.

Uniform distribution matters. It rules out a hash-based "pick any bucket" shortcut.

You: When get(key) is called, does it count as a "use" and move the entry to most-recently-used?

Interviewer: Yes. Any successful get or put on an existing key bumps it to MRU.

You: And delete(key) — does that affect LRU ordering in any way, or just removes the entry?

Interviewer: Just removes it.

You: Does getRandom() count as a use? Should it update LRU position?

Interviewer: No. getRandom is a pure observer. It does not change ordering.

Good — that keeps getRandom decoupled from the linked list pointers.

You: On eviction — we always evict the LRU entry, and only when put exceeds capacity?

Interviewer: Right. Never evict on get or getRandom.

You: Thread safety?

Interviewer: Assume single-threaded for now, but call out where you would add locks.

You: What if I getRandom() on an empty cache?

Interviewer: Return null / throw — your call, just be consistent.

Final Requirements

get(key) -> V | null — O(1). Moves key to MRU if present.
put(key, value) — O(1). Inserts or updates; evicts LRU if at capacity after insert.
delete(key) -> bool — O(1).
getRandom() -> (K, V) | null — O(1). Uniform across current entries. Does not affect LRU order.
Capacity is fixed at construction.

Out of scope: Thread safety, persistence, TTL expiration, weighted random sampling.

Deferred tradeoffs: We assume hashMap operations are O(1) amortized — standard assumption in this class of problem.

Core Entities and Relationships

Walking through the nouns:

Node — the linked-list element. Has prev, next, key, value. Must also carry its index into the random-access array so that delete can patch the array in O(1). That last field is the load-bearing insight of the whole design.
DoublyLinkedList — owns the LRU ordering. Head is MRU, tail is LRU. Supports addFront, remove, removeTail.
LRURandomCache — top-level class that owns the hash map, the linked list, and the array. Every public method mutates all three in coordination.

Why not three separate "coordinator" classes? Because the coupling is tight — every delete touches all three, and no meaningful behavior emerges from any subset. One class with helper methods keeps the invariants visible.

Entity	Responsibility
`Node`	Stores `(key, value)` plus linked-list pointers and its current array index
`DoublyLinkedList`	Owns LRU ordering. Constant-time add-front, remove, remove-tail
`LRURandomCache`	Public API. Owns the hash map, the list, and the array. Keeps all three consistent

Class Design

Node

State:

key: K
value: V
prev: Node
next: Node
arrayIndex: int — position in the random-access array

The arrayIndex is the bridge between the two subsystems. Every mutation that touches the array must update this field on the affected nodes.

DoublyLinkedList

State:

head: Node (sentinel)
tail: Node (sentinel)

Methods:

addFront(node) — insert right after head
remove(node) — unlink
removeTail() -> Node — unlink and return the node before tail (the LRU)
moveToFront(node) — remove + addFront

Sentinel head and tail nodes eliminate null checks for first/last element operations.

LRURandomCache

State:

capacity: int
map: Map<K, Node> — key -> node (for O(1) lookup)
list: DoublyLinkedList — for LRU ordering
array: Node[] — dense array of all current nodes (for O(1) random access)
rng: Random

Methods:

get(key) -> V | null
put(key, value)
delete(key) -> bool
getRandom() -> (K, V) | null

Design decisions worth surfacing:

Why store Node in the array instead of just keys? Because when we swap-and-pop during delete, we need O(1) access to the node we just swapped in, to update its arrayIndex. Storing nodes saves a hash map lookup per swap.
Why does getRandom not update LRU order? The interviewer said so, but even if they had not, touching the list on every random access would break the "random sample does not affect warmth" mental model users expect.
Why no dedicated put-internal-no-evict helper? Because put has two branches (update vs insert) and each is only a handful of lines. Premature extraction hurts readability.

Design principles:

Composition over inheritance — the cache owns a list, not extends one.
Invariant-driven design — every public method is written by asking "what does each of (map, list, array) need to reflect after this call?"
Single source of truth per fact — the LRU order lives in the list. The value lives in the node. The random-access position lives in the array + arrayIndex. No fact is stored in two places where they can disagree.

Implementation

Core Method: `get(key)`

Look up map[key]. If missing, return null.
Move the node to the front of the list.
Return the node's value.

The array is untouched. LRU order changes, random sampling is unaffected.

Core Method: `put(key, value)`

If key exists:

Update the node's value.
Move it to the front.

If key does not exist:

Create a new node. Append it to the array at index array.length; set node.arrayIndex.
Add to the front of the list. Put it in the map.
If map.size > capacity, evict:
- Remove the tail node from the list.
- Remove its key from the map.
- Swap-pop from the array: replace array[evicted.arrayIndex] with array[last], update the swapped node's arrayIndex, pop last.

Core Method: `delete(key)`

Look up map[key]. If missing, return false.
Remove from the list.
Remove from the map.
Swap-pop from the array:
- If the node is not the last, copy array[last] into array[node.arrayIndex] and update the swapped node's arrayIndex.
- Pop the last.
Return true.

Core Method: `getRandom()`

If array is empty, return null.
Pick i = rng.nextInt(array.length).
Return (array[i].key, array[i].value).

Algorithmic decision: why the swap-pop trick

Bad: Store nodes in a list. Deletion is O(n) because you must shift. Random access by index is O(1) but deletes are a dealbreaker.

Good: Store nodes in an ArrayList and rebuild indices lazily. Deletes are still O(n) to find the slot unless you track the index.

Great: Each node knows its current array index. To delete, swap with the last element (O(1)), update the surviving swapped node's index, and pop. Delete becomes O(1) and random access stays O(1). The cost is one extra integer per node and the discipline to always update arrayIndex when you touch the array.

Verification

Setup: LRURandomCache(capacity=3).

Internal state: map = {}, list = [head][tail], array = [].

Step 1 — put("a", 1).

New node A. array = [A], A.arrayIndex = 0. list = head -> A -> tail. map = {a: A}.

Step 2 — put("b", 2).

array = [A, B]. B.arrayIndex = 1. list = head -> B -> A -> tail.

Step 3 — put("c", 3).

array = [A, B, C]. C.arrayIndex = 2. list = head -> C -> B -> A -> tail.

Step 4 — get("a") returns 1.

A moves to front. list = head -> A -> C -> B -> tail. array untouched.

Step 5 — put("d", 4) triggers eviction.

Insert D. array = [A, B, C, D], D.arrayIndex = 3. list = head -> D -> A -> C -> B -> tail. Size is 4 > 3, evict.
Evict tail = B. Remove from list and map. B's arrayIndex was 1. Swap-pop: array[1] = D, update D.arrayIndex = 1, pop. array = [A, D, C]. map = {a: A, c: C, d: D}.

Step 6 — getRandom().

rng.nextInt(3) returns 2. Return (C.key, C.value) = ("c", 3). LRU order unchanged.

Step 7 — delete("a").

A at index 0. Swap-pop: array[0] = C, update C.arrayIndex = 0, pop. array = [C, D]. Remove A from list and map.

Every step leaves all three structures consistent. The arrayIndex discipline is what makes it all work.

Complete Code Implementation

JavaC++TypeScript

java

import java.util.*;

public class LRURandomCache<K, V> {

    private static final class Node<K, V> {
        K key; V value;
        Node<K, V> prev, next;
        int arrayIndex;
        Node(K k, V v) { key = k; value = v; }
    }

    private final int capacity;
    private final Map<K, Node<K, V>> map = new HashMap<>();
    private final List<Node<K, V>> array = new ArrayList<>();
    private final Node<K, V> head = new Node<>(null, null);
    private final Node<K, V> tail = new Node<>(null, null);
    private final Random rng = new Random();

    public LRURandomCache(int capacity) {
        if (capacity <= 0) throw new IllegalArgumentException("capacity > 0");
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }

    public V get(K key) {
        Node<K, V> n = map.get(key);
        if (n == null) return null;
        moveToFront(n);
        return n.value;
    }

    public void put(K key, V value) {
        Node<K, V> n = map.get(key);
        if (n != null) {
            n.value = value;
            moveToFront(n);
            return;
        }
        Node<K, V> fresh = new Node<>(key, value);
        fresh.arrayIndex = array.size();
        array.add(fresh);
        map.put(key, fresh);
        addFront(fresh);
        if (map.size() > capacity) evictLRU();
    }

    public boolean delete(K key) {
        Node<K, V> n = map.remove(key);
        if (n == null) return false;
        unlink(n);
        removeFromArray(n);
        return true;
    }

    public Map.Entry<K, V> getRandom() {
        if (array.isEmpty()) return null;
        Node<K, V> n = array.get(rng.nextInt(array.size()));
        return Map.entry(n.key, n.value);
    }

    public int size() { return array.size(); }

    // --- internal helpers ---

    private void addFront(Node<K, V> n) {
        n.prev = head;
        n.next = head.next;
        head.next.prev = n;
        head.next = n;
    }

    private void unlink(Node<K, V> n) {
        n.prev.next = n.next;
        n.next.prev = n.prev;
    }

    private void moveToFront(Node<K, V> n) {
        unlink(n);
        addFront(n);
    }

    private void evictLRU() {
        Node<K, V> lru = tail.prev;
        unlink(lru);
        map.remove(lru.key);
        removeFromArray(lru);
    }

    private void removeFromArray(Node<K, V> n) {
        int i = n.arrayIndex;
        int last = array.size() - 1;
        if (i != last) {
            Node<K, V> moved = array.get(last);
            array.set(i, moved);
            moved.arrayIndex = i;
        }
        array.remove(last);
    }
}

cpp

#include <list>
#include <random>
#include <stdexcept>
#include <unordered_map>
#include <vector>

template <typename K, typename V>
class LRURandomCache {
    struct Node {
        K key; V value;
        int arrayIndex;
        Node* prev; Node* next;
    };

    int capacity_;
    std::unordered_map<K, Node*> map_;
    std::vector<Node*> array_;
    Node* head_;
    Node* tail_;
    std::mt19937 rng_{std::random_device{}()};

    void addFront(Node* n) {
        n->prev = head_; n->next = head_->next;
        head_->next->prev = n; head_->next = n;
    }
    void unlink(Node* n) {
        n->prev->next = n->next; n->next->prev = n->prev;
    }
    void moveToFront(Node* n) { unlink(n); addFront(n); }
    void removeFromArray(Node* n) {
        int i = n->arrayIndex;
        int last = (int)array_.size() - 1;
        if (i != last) {
            array_[i] = array_[last];
            array_[i]->arrayIndex = i;
        }
        array_.pop_back();
    }
    void evictLRU() {
        Node* lru = tail_->prev;
        unlink(lru);
        map_.erase(lru->key);
        removeFromArray(lru);
        delete lru;
    }

public:
    explicit LRURandomCache(int cap) : capacity_(cap) {
        if (cap <= 0) throw std::invalid_argument("capacity > 0");
        head_ = new Node{}; tail_ = new Node{};
        head_->next = tail_; tail_->prev = head_;
    }
    ~LRURandomCache() {
        for (auto* n : array_) delete n;
        delete head_; delete tail_;
    }

    bool get(const K& key, V& out) {
        auto it = map_.find(key);
        if (it == map_.end()) return false;
        moveToFront(it->second);
        out = it->second->value;
        return true;
    }

    void put(const K& key, const V& value) {
        auto it = map_.find(key);
        if (it != map_.end()) { it->second->value = value; moveToFront(it->second); return; }
        Node* n = new Node{key, value, (int)array_.size(), nullptr, nullptr};
        array_.push_back(n);
        map_[key] = n;
        addFront(n);
        if ((int)map_.size() > capacity_) evictLRU();
    }

    bool erase(const K& key) {
        auto it = map_.find(key);
        if (it == map_.end()) return false;
        Node* n = it->second;
        map_.erase(it);
        unlink(n);
        removeFromArray(n);
        delete n;
        return true;
    }

    bool getRandom(K& k, V& v) {
        if (array_.empty()) return false;
        std::uniform_int_distribution<int> dist(0, (int)array_.size() - 1);
        Node* n = array_[dist(rng_)];
        k = n->key; v = n->value;
        return true;
    }

    int size() const { return (int)array_.size(); }
};

typescript

class Node<K, V> {
  prev: Node<K, V> | null = null;
  next: Node<K, V> | null = null;
  arrayIndex = 0;
  constructor(public key: K, public value: V) {}
}

export class LRURandomCache<K, V> {
  private map = new Map<K, Node<K, V>>();
  private array: Node<K, V>[] = [];
  private head = new Node<K, V>(null as any, null as any);
  private tail = new Node<K, V>(null as any, null as any);

  constructor(private capacity: number) {
    if (capacity <= 0) throw new Error("capacity > 0");
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  get(key: K): V | null {
    const n = this.map.get(key);
    if (!n) return null;
    this.moveToFront(n);
    return n.value;
  }

  put(key: K, value: V): void {
    const existing = this.map.get(key);
    if (existing) {
      existing.value = value;
      this.moveToFront(existing);
      return;
    }
    const n = new Node(key, value);
    n.arrayIndex = this.array.length;
    this.array.push(n);
    this.map.set(key, n);
    this.addFront(n);
    if (this.map.size > this.capacity) this.evictLRU();
  }

  delete(key: K): boolean {
    const n = this.map.get(key);
    if (!n) return false;
    this.map.delete(key);
    this.unlink(n);
    this.removeFromArray(n);
    return true;
  }

  getRandom(): [K, V] | null {
    if (this.array.length === 0) return null;
    const i = Math.floor(Math.random() * this.array.length);
    const n = this.array[i];
    return [n.key, n.value];
  }

  size(): number { return this.array.length; }

  // --- internal helpers ---

  private addFront(n: Node<K, V>) {
    n.prev = this.head;
    n.next = this.head.next;
    this.head.next!.prev = n;
    this.head.next = n;
  }

  private unlink(n: Node<K, V>) {
    n.prev!.next = n.next;
    n.next!.prev = n.prev;
  }

  private moveToFront(n: Node<K, V>) {
    this.unlink(n);
    this.addFront(n);
  }

  private evictLRU() {
    const lru = this.tail.prev!;
    this.unlink(lru);
    this.map.delete(lru.key);
    this.removeFromArray(lru);
  }

  private removeFromArray(n: Node<K, V>) {
    const i = n.arrayIndex;
    const last = this.array.length - 1;
    if (i !== last) {
      const moved = this.array[last];
      this.array[i] = moved;
      moved.arrayIndex = i;
    }
    this.array.pop();
  }
}

Extensibility

1. "Can you make `getRandom` return weighted samples — more recent entries more likely?"

You answer: "Uniform random is O(1) because of the dense array. Weighted random breaks that unless we use a prefix-sum tree, which is O(log n). I would split getRandom() into getRandomUniform() kept at O(1) and getRandomWeighted() at O(log n), and introduce a Fenwick-backed structure only when needed. I do not want to pay log-n cost on the common path."

java

public interface RandomSampler<K, V> {
    Map.Entry<K, V> sample();
}

// UniformSampler (current behavior, O(1))
// WeightedSampler using a Fenwick tree over recency weights (O(log n))

Tradeoff: Weighted sampling is rarely needed. Do not pay the log-n cost up front. Offer it as a separate method.

2. "Make it thread-safe."

You answer: "The simplest correct thing is a single lock around the public methods. That serializes everything but keeps all three structures consistent. If contention becomes a bottleneck, I would consider a read-write lock — get/getRandom share a read lock only if get stops updating LRU order, which changes semantics. Striped locking by key does not work here because every mutation can ripple through the list and the array, which are shared."

java

public synchronized V get(K key) { /* ... */ }
public synchronized void put(K key, V value) { /* ... */ }
public synchronized boolean delete(K key) { /* ... */ }
public synchronized Map.Entry<K, V> getRandom() { /* ... */ }

Tradeoff: One lock is coarse. It is also correct and simple. Reach for fine-grained locking only after measuring.

3. "Add TTL — entries expire after N ms."

You answer: "I add expiresAt to Node. On get, if expired, I delete and return null. For proactive expiry, I run a background sweep — but that contradicts the O(1) guarantee, so I keep it lazy: expire on access. If the workload needs proactive expiry, I add a priority queue keyed by expiresAt, accepting O(log n) on put."

java

private static final class Node<K, V> {
    K key; V value;
    long expiresAt;          // new field
    int arrayIndex;
    Node<K, V> prev, next;
}

Tradeoff: Lazy expiry is free but can hold memory for expired keys until they are touched. Proactive expiry is strictly more work per put. Pick based on workload.

What is Expected at Each Level

Level	Expectations
Junior	Writes LRU alone (hash map + doubly linked list). When asked about `getRandom`, reaches for a list scan. With a hint, realizes an array is needed and struggles to keep it in sync.
Mid-level	Combines both structures cleanly. Recognizes that every `Node` needs to carry its `arrayIndex` so delete can do swap-pop in O(1). Traces through an eviction correctly on the first try.
Senior	Names the invariants up front: "the map is for O(1) lookup by key, the list owns LRU order, the array is for O(1) random sampling. Every mutation has to update whichever of the three is affected." Writes helper methods for `addFront`, `unlink`, `removeFromArray` so the public methods read like narrative. Proactively discusses thread safety, TTL, and weighted sampling as orthogonal extensions. Google signal: the refactoring instinct shows up when they write `get` and `put` first, notice the duplication between "update value and move to front" in `put` and "move to front" in `get`, and factor out `moveToFront` before being asked.

41 — LLD: LRU Cache with getRandom() in O(1) ​

Understanding the Problem ​

Requirements ​

Clarifying Questions ​

Final Requirements ​

Core Entities and Relationships ​

Class Design ​

Node ​

DoublyLinkedList ​

LRURandomCache ​

Implementation ​

Core Method: get(key) ​

Core Method: put(key, value) ​

Core Method: delete(key) ​

Core Method: getRandom() ​

Algorithmic decision: why the swap-pop trick ​

Verification ​

Complete Code Implementation ​

Extensibility ​

1. "Can you make getRandom return weighted samples — more recent entries more likely?" ​

2. "Make it thread-safe." ​

3. "Add TTL — entries expire after N ms." ​

What is Expected at Each Level ​

41 — LLD: LRU Cache with `getRandom()` in O(1)

Understanding the Problem

Requirements

Clarifying Questions

Final Requirements

Core Entities and Relationships

Class Design

Node

DoublyLinkedList

LRURandomCache

Implementation

Core Method: `get(key)`

Core Method: `put(key, value)`

Core Method: `delete(key)`

Core Method: `getRandom()`

Algorithmic decision: why the swap-pop trick

Verification

Complete Code Implementation

Extensibility

1. "Can you make `getRandom` return weighted samples — more recent entries more likely?"

2. "Make it thread-safe."

3. "Add TTL — entries expire after N ms."

What is Expected at Each Level