LRU cache

The most common warm-up in low-level design rounds, and a favourite coding question too. It tests whether you can combine two data structures so that each covers the other's weakness, and whether you can keep pointer code correct under pressure.

1. The prompt

What the interviewer is watching for: that you explain why one structure isn't enough, use sentinels to avoid edge cases, and keep the dictionary and the list in sync on every path.

2. Clarify the requirements

Spend the first five minutes here. Ask, then write the answers down where the interviewer can see them.

3. The classes

4. How it works

Capacity 2. Watch the list reorder on every access, and the tail fall off when a third key arrives.

Both operations do the same two cheap things: a dictionary lookup, and a constant number of pointer changes. Neither ever scans the list.

5. Patterns and why

6. The code

Generic in all three languages. put returns the evicted key, which makes the behaviour easy to test and to log.

from __future__ import annotations
from typing import Generic, Optional, TypeVar

K = TypeVar("K")
V = TypeVar("V")


class Node(Generic[K, V]):
    """One entry in the recency list."""

    def __init__(self, key: Optional[K] = None, value: Optional[V] = None) -> None:
        self.key = key
        self.value = value
        self.prev: Optional[Node[K, V]] = None
        self.next: Optional[Node[K, V]] = None


class LRUCache(Generic[K, V]):
    """get and put in O(1): a dict finds the node, a doubly linked list keeps recency order."""

    def __init__(self, capacity: int) -> None:
        if capacity < 1:
            raise ValueError("capacity must be at least 1")
        self.capacity = capacity
        self.nodes: dict[K, Node[K, V]] = {}
        self.head: Node[K, V] = Node()   # sentinel: head.next is the most recent
        self.tail: Node[K, V] = Node()   # sentinel: tail.prev is the least recent
        self.head.next, self.tail.prev = self.tail, self.head

    def get(self, key: K) -> Optional[V]:
        node = self.nodes.get(key)
        if node is None:
            return None
        self._move_to_front(node)
        return node.value

    def put(self, key: K, value: V) -> Optional[K]:
        """Insert or update; returns the evicted key, if any."""
        node = self.nodes.get(key)
        if node is not None:
            node.value = value
            self._move_to_front(node)
            return None
        node = Node(key, value)
        self.nodes[key] = node
        self._add_front(node)
        if len(self.nodes) > self.capacity:
            lru = self.tail.prev
            assert lru is not None and lru is not self.head
            self._unlink(lru)
            del self.nodes[lru.key]  # type: ignore[arg-type]
            return lru.key
        return None

    def keys_by_recency(self) -> list[K]:
        out, node = [], self.head.next
        while node is not self.tail:
            assert node is not None
            out.append(node.key)
            node = node.next
        return out

    def _unlink(self, node: Node[K, V]) -> None:
        assert node.prev is not None and node.next is not None
        node.prev.next, node.next.prev = node.next, node.prev

    def _add_front(self, node: Node[K, V]) -> None:
        first = self.head.next
        assert first is not None
        node.prev, node.next = self.head, first
        self.head.next = first.prev = node

    def _move_to_front(self, node: Node[K, V]) -> None:
        self._unlink(node)
        self._add_front(node)


if __name__ == "__main__":
    cache: LRUCache[int, str] = LRUCache(2)
    cache.put(1, "one")
    cache.put(2, "two")
    print("get 1 ->", cache.get(1) or "miss")
    print("put 3, evicted", cache.put(3, "three"))
    print("get 2 ->", cache.get(2) or "miss")
    print("put 4, evicted", cache.put(4, "four"))
    print("get 1 ->", cache.get(1) or "miss")
    print("get 3 ->", cache.get(3) or "miss")
    print("most recent first:", " ".join(str(k) for k in cache.keys_by_recency()))

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

/** get and put in O(1): a Map finds the node, a doubly linked list keeps recency order. */
class LRUCache<K, V> {
  private nodes = new Map<K, LruNode<K, V>>();
  private head = new LruNode<K, V>(); // sentinel: head.next is the most recent
  private tail = new LruNode<K, V>(); // sentinel: tail.prev is the least recent

  constructor(private readonly capacity: number) {
    if (capacity < 1) throw new Error("capacity must be at least 1");
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

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

  /** Insert or update; returns the evicted key, if any. */
  put(key: K, value: V): K | null {
    const existing = this.nodes.get(key);
    if (existing) {
      existing.value = value;
      this.moveToFront(existing);
      return null;
    }
    const node = new LruNode<K, V>(key, value);
    this.nodes.set(key, node);
    this.addFront(node);
    if (this.nodes.size > this.capacity) {
      const lru = this.tail.prev!;
      this.unlink(lru);
      this.nodes.delete(lru.key as K);
      return lru.key;
    }
    return null;
  }

  keysByRecency(): K[] {
    const out: K[] = [];
    for (let n = this.head.next!; n !== this.tail; n = n.next!) out.push(n.key as K);
    return out;
  }

  private unlink(node: LruNode<K, V>): void {
    node.prev!.next = node.next;
    node.next!.prev = node.prev;
  }

  private addFront(node: LruNode<K, V>): void {
    const first = this.head.next!;
    node.prev = this.head;
    node.next = first;
    this.head.next = node;
    first.prev = node;
  }

  private moveToFront(node: LruNode<K, V>): void {
    this.unlink(node);
    this.addFront(node);
  }
}

const cache = new LRUCache<number, string>(2);
cache.put(1, "one");
cache.put(2, "two");
console.log("get 1 ->", cache.get(1) ?? "miss");
console.log("put 3, evicted", cache.put(3, "three"));
console.log("get 2 ->", cache.get(2) ?? "miss");
console.log("put 4, evicted", cache.put(4, "four"));
console.log("get 1 ->", cache.get(1) ?? "miss");
console.log("get 3 ->", cache.get(3) ?? "miss");
console.log("most recent first:", cache.keysByRecency().join(" "));

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

/** get and put in O(1): a HashMap finds the node, a doubly linked list keeps recency order. */
class LRUCache<K, V> {
    private static final class Node<K, V> {
        K key;
        V value;
        Node<K, V> prev, next;

        Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

    private final int capacity;
    private final Map<K, Node<K, V>> nodes = new HashMap<>();
    private final Node<K, V> head = new Node<>(null, null); // sentinel: head.next is the most recent
    private final Node<K, V> tail = new Node<>(null, null); // sentinel: tail.prev is the least recent

    LRUCache(int capacity) {
        if (capacity < 1) throw new IllegalArgumentException("capacity must be at least 1");
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }

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

    /** Insert or update; returns the evicted key, or null. */
    K put(K key, V value) {
        Node<K, V> node = nodes.get(key);
        if (node != null) {
            node.value = value;
            moveToFront(node);
            return null;
        }
        node = new Node<>(key, value);
        nodes.put(key, node);
        addFront(node);
        if (nodes.size() > capacity) {
            Node<K, V> lru = tail.prev;
            unlink(lru);
            nodes.remove(lru.key);
            return lru.key;
        }
        return null;
    }

    List<K> keysByRecency() {
        List<K> out = new ArrayList<>();
        for (Node<K, V> n = head.next; n != tail; n = n.next) out.add(n.key);
        return out;
    }

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

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

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

public class Main {
    static String orMiss(String v) {
        return v == null ? "miss" : v;
    }

    public static void main(String[] args) {
        LRUCache<Integer, String> cache = new LRUCache<>(2);
        cache.put(1, "one");
        cache.put(2, "two");
        System.out.println("get 1 -> " + orMiss(cache.get(1)));
        System.out.println("put 3, evicted " + cache.put(3, "three"));
        System.out.println("get 2 -> " + orMiss(cache.get(2)));
        System.out.println("put 4, evicted " + cache.put(4, "four"));
        System.out.println("get 1 -> " + orMiss(cache.get(1)));
        System.out.println("get 3 -> " + orMiss(cache.get(3)));
        System.out.println("most recent first: "
                + cache.keysByRecency().stream().map(String::valueOf).collect(Collectors.joining(" ")));
    }
}

Output (the same in all three languages)

get 1 -> one
put 3, evicted 2
get 2 -> miss
put 4, evicted 1
get 1 -> miss
get 3 -> three
most recent first: 3 4

7. Concurrency and edge cases

• Every get is a write. It reorders the list, so a read-write lock doesn't help: wrap both methods in one lock, or use striped caches (one lock per shard of keys) for throughput.
• Keep the map and list in sync on every path, including updates to an existing key and evictions.
• Store the key in the node. Eviction finds the tail node and must delete its key from the dictionary.
• Built-ins exist: Python's OrderedDict (move_to_end, popitem(last=False)) and Java's LinkedHashMap with access order. Mention them; build it by hand if asked.

8. Follow-up questions

What interviewers ask once the core works, and a short answer for each.

How would you add a time-to-live?

Store an expiry time in each node; treat expired entries as misses on get, and remove them lazily, or with a background sweep.

How would you make it thread-safe?

A lock around get and put (both mutate). For high throughput, shard the keys across several caches, each with its own lock.

LFU instead of LRU?

Keep a frequency per key and a list of keys per frequency, plus the current minimum frequency; eviction takes the least recently used key from the minimum-frequency list, still O(1).

How would you measure it?

Count hits, misses and evictions; the hit ratio tells you whether the capacity is right.

9. Common mistakes

10. Check yourself

Your turn

1. Add TTL (15 min). Give each node an expiry time and treat expired entries as misses.
2. Add statistics (5 min). Count hits, misses and evictions.
3. Make it thread-safe (5 min). Write a wrapper class with one lock, using the decorator pattern.