LRU Cache

Design a fixed-capacity cache with get(key) and put(key, value), both O(1). When it's full, evict the least recently used entry. (LC 146)

This is the canonical object-design interview problem — less an algorithm than a composition exercise. It's in the circuit because it trains the skill the design rounds actually score: choosing two structures whose strengths cover each other's weaknesses, and saying why.

The recipe

Say before you type: "No single structure does this. A hash map gives O(1) lookup but has no order; a list has order but O(n) lookup. So: a map from key to node, and a doubly-linked list as the recency order — most recent behind the head, eviction victim in front of the tail."

1. Map<key, node> — find any entry in O(1).
2. Doubly-linked list with sentinel head and tail — recency order, O(1) splice anywhere.
3. get: look up the node, unlink it, re-insert at the front, return its value.
4. put: replace if present; insert at front; over capacity → the node before the tail sentinel is the LRU, remove it and delete its key from the map.

The code

class DNode {
  key: number; val: number;
  prev: DNode | null = null;
  next: DNode | null = null;
  constructor(key = 0, val = 0) { this.key = key; this.val = val; }
}

class LRUCache {
  private capacity: number;
  private map = new Map<number, DNode>();
  private head = new DNode(); // sentinel: most-recent side
  private tail = new DNode(); // sentinel: least-recent side

  constructor(capacity: number) {
    this.capacity = capacity;
    this.head.next = this.tail;  // sentinels remove all null-checking
    this.tail.prev = this.head;
  }

  private remove(node: DNode): void {
    node.prev!.next = node.next;
    node.next!.prev = node.prev;
  }

  private insertFront(node: DNode): void {
    node.next = this.head.next;
    node.prev = this.head;
    this.head.next!.prev = node;
    this.head.next = node;
  }

  get(key: number): number {
    const node = this.map.get(key);
    if (!node) return -1;
    this.remove(node);
    this.insertFront(node); // touching it makes it most-recent
    return node.val;
  }

  put(key: number, value: number): void {
    const existing = this.map.get(key);
    if (existing) { this.remove(existing); this.map.delete(key); }

    const node = new DNode(key, value);
    this.map.set(key, node);
    this.insertFront(node);

    if (this.map.size > this.capacity) {
      const lru = this.tail.prev!;   // least-recently used
      this.remove(lru);
      this.map.delete(lru.key);      // THIS is why the node stores its key
    }
  }
}

Why this shape — the three sentences that score

1. "Doubly linked, because I need O(1) removal from the middle." A get promotes an arbitrary node; unlinking it needs its predecessor. Singly-linked would make finding that predecessor an O(n) walk — the prev pointer is what you're paying for.
2. "Sentinel head and tail, so there are no edge cases." With permanent dummy nodes at both ends, every real node always has a prev and a next — empty list, single element, front, back: all the same code path.
3. "The node stores its own key, so eviction can delete from the map." At eviction you're holding a node (from the tail) and must remove its map entry. Without the key on the node, that's an O(n) reverse search. This is the detail people miss until it breaks.

Complexity

	Cost	Because
Time	O(1) get and put	One map operation plus a constant number of pointer splices
Space	O(capacity)	One node + one map entry per cached item

Traps

• Wiring insertFront in the wrong order and orphaning half the list — write the four pointer assignments in a fixed ritual and trace them once on paper.
• Forgetting the map delete at eviction. The list shrinks, the map doesn't, capacity silently grows.
• On put of an existing key: remove the old node first, or it lingers in the list as a ghost.

The TypeScript shortcut worth naming

JavaScript's Map preserves insertion order, so an interview-legal LRU exists with no linked list: on access, delete then re-set the key (moves it to the back); the LRU victim is map.keys().next().value. Mention it, then say why the linked list version is still the one to write when asked — the Map trick is JS-specific, and the composed-structures version is what the question is testing. Knowing both, and which to present, is the senior move.

The pattern this trains

"O(1) get and put" → hash map + linked list. The same composition (index for lookup + ordered structure for policy) underlies LFU caches, rate limiters, and the async request cache in the practical set — where this exact problem reappears wearing a Promise.