LeetCode 146 – LRU Cache

LRU Cache is the most common design question on the list, and it is a design question rather than an algorithms one: no clever insight, just the recognition that no single data structure does what is required, and that combining two gives every operation in O(1). It is also the problem where getting the pointer surgery right matters more than getting the idea right, because everyone gets the idea.

The problem

Design a cache with a fixed capacity supporting:

• get(key) — return the value, or -1 if absent.
• put(key, value) — insert or update; if that exceeds capacity, evict the least recently used entry.

Both must run in O(1) average time.

LRUCache(2)
put(1,1)      cache: {1=1}
put(2,2)      cache: {1=1, 2=2}
get(1)   -> 1  1 is now the most recent
put(3,3)      evicts 2, NOT 1     cache: {1=1, 3=3}
get(2)   -> -1
put(4,4)      evicts 1            cache: {3=3, 4=4}
get(1)   -> -1
get(3)   -> 3
get(4)   -> 4

Note that get counts as a use. That is the line people skip, and it is what makes the fourth step evict 2 rather than 1.

Why one structure is not enough

The last row is the hinge. A doubly linked list can unlink and re-insert a node in constant time — if you have a reference to it. Finding it is the slow part. So:

Hash map from key to node, doubly linked list for order. The map answers "where is it", the list answers "which is oldest", and each covers exactly the other's weakness.

Why doubly, and why sentinels

Doubly linked: removing a node requires rewiring its predecessor, and in a singly linked list finding the predecessor is O(n) — which would destroy the whole point.

Sentinel head and tail nodes that always exist: every real node then has a non-null prev and next, so unlink and insert have no special cases for the ends. Without them, every operation needs "is this the first node? the last? the only one?", and that is where the bugs live. Two wasted objects to delete a dozen branches is an excellent trade, and saying so is part of the answer.

head <-> [most recent] <-> ... <-> [least recent] <-> tail
 ^                                                       ^
 sentinel                                         sentinel
                                            evict from here

Java

class LRUCache {
    private static class Entry {
        int key, value;
        Entry prev, next;
        Entry(int key, int value) { this.key = key; this.value = value; }
    }

    private final int capacity;
    private final Map<Integer, Entry> index = new HashMap<>();
    // Sentinels: every real node has a non-null prev and next, so no edge cases.
    private final Entry head = new Entry(0, 0);
    private final Entry tail = new Entry(0, 0);

    public LRUCache(int capacity) {
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        Entry entry = index.get(key);
        if (entry == null) return -1;

        moveToFront(entry);        // a read counts as a use
        return entry.value;
    }

    public void put(int key, int value) {
        Entry existing = index.get(key);

        if (existing != null) {
            existing.value = value;      // update, do NOT insert a duplicate
            moveToFront(existing);
            return;
        }

        if (index.size() == capacity) {
            Entry lru = tail.prev;       // the node just before the tail sentinel
            unlink(lru);
            index.remove(lru.key);       // remove by KEY -- this is why the node stores it
        }

        Entry fresh = new Entry(key, value);
        index.put(key, fresh);
        insertAfterHead(fresh);
    }

    private void moveToFront(Entry entry) {
        unlink(entry);
        insertAfterHead(entry);
    }

    private void unlink(Entry entry) {
        entry.prev.next = entry.next;
        entry.next.prev = entry.prev;
    }

    private void insertAfterHead(Entry entry) {
        entry.next = head.next;
        entry.prev = head;
        head.next.prev = entry;
        head.next = entry;
    }
}

The node stores its own key, which looks redundant next to a map keyed by it. It is not: on eviction you hold the node and need to delete the corresponding map entry, and without the key on the node there is no way to do that in O(1). Forgetting it is the most common structural bug in this problem, and the symptom is a map that grows forever.

The update branch in put is the second one. Treating an existing key as an insert puts a duplicate node in the list, so the size accounting drifts and a stale node is eventually evicted instead of the real one.

Python

from collections import OrderedDict


class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = OrderedDict()

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1

        self.cache.move_to_end(key)        # O(1): it IS a hash map plus a linked list
        return self.cache[key]

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.move_to_end(key)

        self.cache[key] = value

        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)  # evict the oldest

OrderedDict is exactly the structure described above — CPython implements it as a dict plus a doubly linked list — so move_to_end and popitem are genuinely O(1) and this is not cheating.

It is, however, worth saying that out loud rather than letting it look like you dodged the question. An interviewer asking this wants to know you could build it; the honest framing is "the standard library has the exact structure, and here is what it is doing underneath". Be ready to write the Java version if asked.

Complexity

Average, not worst case — hash collisions can degrade a lookup. The list operations are genuinely O(1) worst case. That distinction is worth stating precisely, because "O(1)" for a hash map is always an average.

The follow-ups

Thread safety. Nothing here is safe under concurrent access — two threads can evict simultaneously and corrupt the list. A single lock is the honest answer; a striped or sharded cache is the scalable one. Say which you would build and why.

LFU Cache (460) evicts by frequency instead of recency, and needs a third structure: a map from frequency to a list of keys at that frequency, plus a running minimum. It is markedly harder and a common follow-up.

What about TTL? Real caches expire entries by time as well, which needs either lazy expiry on read or a separate priority queue. Mentioning it shows you have thought about caches rather than about this exercise.

What the interviewer is checking

• That you identify two structures and say what each covers.
• Why the list must be doubly linked.
• Sentinel nodes, and that they exist to delete edge cases.
• That the node stores its key, for O(1) eviction from the map.
• That get counts as a use.
• That put on an existing key updates rather than inserting.
• Capacity 1, and eviction when full.
• That O(1) on the map is an average, not a worst case.