LRU Cache (Design)

“Design a least-recently-used (LRU) cache.” The prompt fits in one sentence, but the design only works when two data structures preserve one ordering invariant after every read and write. This case study builds that class model first; the coding-judge version comes later.

Requirements

Fix the eviction contract and complexity target before choosing a container. A cache that returns the right values but scans on every access has missed half the prompt.

TTL expiry, persistence, distributed-cache behavior, and thread-safety internals are out of scope. They are useful design-review extensions, but adding them to the first model would hide the data-structure invariant the interview is asking for.

Clarifying questions to ask

Each answer changes either the public contract or the structure needed behind it.

• Is capacity fixed or resizable? Fixed for this design. The constructor rejects zero and negative values. Resizing later would need a rule for immediate evictions when the new capacity is smaller than the current size.
• Does get() count as a use? Yes. A successful read moves that entry to the most-recently-used end. A miss changes nothing.
• Is eviction strictly LRU? Yes. We are not approximating recency and we are not counting frequency. LFU, FIFO, random replacement, and segmented policies solve different workloads.
• Is O(1) required or only desirable? Required on average for both operations. A linear search or shift fails the contract even when it is short on a capacity-two example.
• What key and value types are supported? The cache is generic over K and V. Its hash-map behavior follows the language's key equality rules; in JavaScript, Map supports primitive and object keys.
• What represents a miss? get() returns undefined. If the product must distinguish a missing key from a deliberately stored undefined, return a tagged result or add has(key); this skeleton keeps the conventional interview signature.
• What happens when put() receives an existing key? Update the same node, move it to the front, and keep the size unchanged. Evicting another key on an update would violate capacity semantics.
• Which end is most recent? The list uses head.next as most-recently used and tail.prev as least-recently used. Naming both ends before coding prevents reversed eviction logic.
• Do we expose removal or iteration? Not in the core API. Both could be added, but iteration would need a declared order and removal would have to update the map and list together.
• Must it be thread-safe? The core model is single-threaded. A production wrapper must remember that get() mutates recency, so it is not a read-only critical section even though it does not change the value.

Entity extraction

Run the noun pass before reaching for a memorized implementation:

1. An LRU cache has a fixed capacity and stores key-value entries.
2. A get marks an entry most-recently used.
3. A put may evict the least-recently-used entry.
4. A HashMap finds an entry's node by key.
5. A doubly-linked list orders nodes from head to tail, and every node links to a previous and next node.

Now sort those nouns by responsibility:

The verb pass makes the collaboration explicit:

The key invariant in plain language is: every real list node appears exactly once in the map under its own key, and every map entry points to exactly that list node. head.next is the most recent real node; tail.prev is the least recent.

Before get("a"), one cache might read MRU → c ⇄ b ⇄ a ← LRU. The map jumps directly to node a, the list detaches it from the tail side, and the order becomes MRU → a ⇄ c ⇄ b ← LRU. No entry between c and a is scanned or shifted.

Core class diagram

Four boxes are enough. The map answers “where is this key?”, while the list answers “which key is oldest?”

The two sentinel nodes never hold cache entries. They make every real node have both a predecessor and successor, so removing the first, middle, or last entry uses the same four link assignments. The sentinels also make an empty list unambiguous: head.next === tail and tail.prev === head.

The Node → Node self-association is drawn once even though each node has both prev and next. Two edges between the same boxes would add no design information and would make the diagram ambiguous.

Critical-flow sequence diagram

Assume capacity is two and recency is MRU → a ⇄ b ← LRU. A new put("c", 3) misses, adds c to the front, briefly makes size three, and evicts b from both structures.

The temporary size of three exists only inside one synchronous put(). By the time the method returns, b is in neither the list nor the map. Deleting it from only one structure would leave either a ghost list node or a map pointer to an entry that no longer participates in eviction.

An existing-key put() takes a shorter path: map hit, update that node's value, move it to the front, return. Size never grows, so no unrelated key is evicted.

TypeScript skeleton

The skeleton uses generic keys and values, a map to real nodes, and sentinel head and tail nodes. Every list operation changes a constant number of references.

export {};
 
class Node<K, V> {
  public prev: Node<K, V> | null = null;
  public next: Node<K, V> | null = null;
 
  private constructor(
    public readonly key: K,
    public value: V,
  ) {}
 
  public static entry<K, V>(key: K, value: V): Node<K, V> {
    return new Node(key, value);
  }
 
  public static sentinel<K, V>(): Node<K, V> {
    return new Node<K, V>(undefined as K, undefined as V);
  }
}
 
class DoublyLinkedList<K, V> {
  private readonly head = Node.sentinel<K, V>();
  private readonly tail = Node.sentinel<K, V>();
 
  public constructor() {
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }
 
  public addFirst(node: Node<K, V>): void {
    if (node.prev !== null || node.next !== null) {
      throw new Error("cannot add a node that is already linked");
    }
 
    const first = this.head.next;
    if (first === null) {
      throw new Error("head sentinel is disconnected");
    }
 
    node.prev = this.head;
    node.next = first;
    first.prev = node;
    this.head.next = node;
  }
 
  public moveToFront(node: Node<K, V>): void {
    if (node.prev === this.head) return;
    this.remove(node);
    this.addFirst(node);
  }
 
  public removeLast(): Node<K, V> | null {
    const last = this.tail.prev;
    if (last === null) {
      throw new Error("tail sentinel is disconnected");
    }
    if (last === this.head) return null;
 
    this.remove(last);
    return last;
  }
 
  private remove(node: Node<K, V>): void {
    if (node === this.head || node === this.tail) {
      throw new Error("cannot remove a sentinel");
    }
 
    const previous = node.prev;
    const following = node.next;
    if (previous === null || following === null) {
      throw new Error("cannot remove an unlinked node");
    }
 
    previous.next = following;
    following.prev = previous;
    node.prev = null;
    node.next = null;
  }
}
 
class LRUCache<K, V> {
  private readonly nodes = new Map<K, Node<K, V>>();
  private readonly order = new DoublyLinkedList<K, V>();
 
  public constructor(private readonly capacity: number) {
    if (!Number.isSafeInteger(capacity) || capacity <= 0) {
      throw new Error("capacity must be a positive integer");
    }
  }
 
  public get size(): number {
    return this.nodes.size;
  }
 
  public get(key: K): V | undefined {
    const node = this.nodes.get(key);
    if (node === undefined) return undefined;
 
    this.order.moveToFront(node);
    return node.value;
  }
 
  public put(key: K, value: V): void {
    const existing = this.nodes.get(key);
    if (existing !== undefined) {
      existing.value = value;
      this.order.moveToFront(existing);
      return;
    }
 
    const node = Node.entry(key, value);
    this.order.addFirst(node);
    this.nodes.set(key, node);
 
    if (this.nodes.size <= this.capacity) return;
 
    const evicted = this.order.removeLast();
    if (evicted === null) {
      throw new Error("cache exceeded capacity without an LRU node");
    }
    this.nodes.delete(evicted.key);
  }
}
 
function read(
  cache: LRUCache<string, number>,
  key: string,
): string {
  const value = cache.get(key);
  return value === undefined ? "miss" : String(value);
}
 
const cache = new LRUCache<string, number>(2);
cache.put("a", 1);
cache.put("b", 2);
 
console.log(`get(a): ${read(cache, "a")}`);
cache.put("c", 3);
 
console.log(`get(b): ${read(cache, "b")}`);
console.log(`get(a): ${read(cache, "a")}`);
console.log(`get(c): ${read(cache, "c")}`);

get(a): 1 get(b): miss get(a): 1 get(c): 3

After inserting a and b, get("a") moves a ahead of b. Inserting c then evicts tail.prev, which is b. The later reads prove that b left the map while a and c remain.

The type assertions exist only inside Node.sentinel(): sentinel payloads are never read, while real nodes always come from Node.entry(). Keeping that exception at one construction point lets the rest of the list remain fully generic.

Design-review checklist

This is where the interviewer asks whether the complexity claim survives every edge case.

• Why HashMap plus doubly-linked list: The map provides average O(1) key lookup. The list moves a known node and removes tail.prev in O(1). Neither structure alone provides both operations portably with the required bound.
• Why not an array: Finding a key is O(n) without another index, while moving a hit to the front or removing the first element shifts entries. Adding a map beside the array fixes lookup but not constant-time recency movement.
• Why not a single ordered map: A tree-ordered map sorts by key, not access time, and is usually O(log n). Some languages provide an access-ordered hash map, and JavaScript Map can use delete-plus-set insertion-order behavior; those are valid library shortcuts that hide or specialize the same ordering machinery. The explicit map and list is the portable class model.
• Why get() is a mutation: A hit changes which key will be evicted next. Any lock, audit, test, or const claim must account for the link update even though the returned value is unchanged.
• Sentinel nodes: Fixed head and tail objects remove empty, first, middle, and last-node branches from link manipulation. Their payloads are never entries and must never reach the map.
• One-node identity: Updating an existing key changes the indexed node and moves that same object. Creating a second node would put duplicate keys in the list and make later eviction delete the wrong map entry.
• Eviction ordering: Add the new node, update the map, detect overflow, remove the list tail, then delete that node's key. Whichever exact ordering an implementation chooses, callers must never observe the structures between those coordinated steps.
• Capacity one: put(a), get(a), then put(b) must leave only b. Sentinels make removing the sole real node use the same path as every other tail eviction.
• Thread safety: One mutex around get() and put() is the clearest strict-LRU baseline. Striped locks divide keys across a fixed set of locks, but all hits still mutate a global list; sharding the cache by key with one lock and capacity per shard often gives a more honest scalable trade-off at the cost of approximate global LRU.
• Deadlock risk: If an implementation combines key stripes with a recency lock, define one acquisition order. A hit that takes them in the reverse order of eviction can deadlock even when each method looks locally safe.
• TTL variant: Expiry adds a clock and another ordering question. Checking TTL only on get() is lazy cleanup; proactive cleanup needs a timer wheel or expiry heap, and neither should silently replace the LRU order.
• LFU variant: Least-frequently used needs counts and frequency buckets, not a renamed tail pointer. Policy changes can require a different model rather than another flag on Node.
• Testing recency: Cover hit-to-front, miss-without-mutation, eviction after a hit, repeated hits, and insertion order. Assert returned values and the exact next key evicted.
• Testing updates: Update an existing key at full capacity and assert its value changes, its recency moves, size stays fixed, and no third key disappears.
• Testing boundaries: Cover capacity one, invalid capacities, object keys, and a stored value that is otherwise falsy. Property tests can compare random operations with a slow reference model.
• With more time: Add deletion, resizing, eviction callbacks, metrics, synchronization, TTL, or sharding only after stating how each feature changes the core invariant and complexity promise.

The LRU cache earns constant-time behavior by keeping lookup and recency separate, then restoring their shared invariant before each call returns. Next, a rate limiter and then chess close the case studies.