Design an LRU cache

01The design, in the six-step framework

1. Requirements and use cases

The interviewer usually starts with one sentence: build a cache with a fixed capacity that forgets the least recently used entry. Turn that into verbs before touching a class.

• A caller gets a value by key and receives it in O(1), or a miss marker if it is absent.
• A caller puts a key and value in O(1); if the key exists its value is replaced.
• Every get and every put makes that key the most recently used.
• When a put would exceed the capacity, the cache evicts exactly one entry: the one untouched for the longest time.
• A caller can read the current size and the capacity.

Out of scope unless asked: time-to-live expiry, persistence, and multi-process sharing. Those are separate problems (a key-value store with TTL, a cache manager with pluggable eviction).

Non-functional constraints that decide the design: both operations must be O(1) in the worst case, not amortised over a sort; memory must be proportional to capacity, not to the number of keys ever seen; and the class must be unit-testable without timing tricks, which means recency is defined by call order, not by a clock.

2. Core entities and relationships

Only three nouns matter.

• LRUCache: the public object; owns the capacity, the index and the recency list, and enforces the eviction rule.
• Node: one entry; holds the key, the value and the two neighbour links that make it movable in O(1).
• DoublyLinkedList: the recency order; head side is most recent, tail side is least recent; knows how to unlink any node and link at the head.

The index is a plain dictionary from key to Node. It is not its own class because it has no rules of its own. The cache composes the list and the index: they are created with the cache, never shared, and die with it. A Node is owned by the list, and the index merely points at it, which is aggregation rather than composition. That distinction matters for correctness: a node must be removed from both structures together, and only the cache knows that rule, so only the cache may call both. See relationships and multiplicity for the notation.

3. Interfaces and key methods

The public surface is deliberately tiny. Everything the interviewer will probe lives in the invariants, not in extra methods.

from typing import Generic, Hashable, Optional, TypeVar

K = TypeVar("K", bound=Hashable)
V = TypeVar("V")


class LRUCache(Generic[K, V]):
    def __init__(self, capacity: int) -> None:
        """capacity must be >= 1; raises ValueError otherwise."""

    def get(self, key: K) -> Optional[V]:
        """Return the value and mark key most recently used; None on a miss."""

    def put(self, key: K, value: V) -> None:
        """Insert or replace; mark key most recently used; evict the LRU entry if over capacity."""

    def __len__(self) -> int:
        """Number of entries currently held (never above capacity)."""

    def __contains__(self, key: K) -> bool:
        """Membership without touching recency (useful for tests and metrics)."""

Invariants every method must leave true: the index and the list hold exactly the same set of keys; the list order is the recency order with the head most recent; the length never exceeds the capacity; and a key present in the index is reachable from the list in O(1) through its node. __contains__ is the one method that reads without touching recency, and saying that aloud is part of designing method signatures: a method name should tell the caller whether it has side effects.

4. Design patterns and the choices behind them

Two structures that point at each other

The force is two different access patterns on the same entries: by key (random access) and by recency (ordered, with cheap moves). No single standard container gives O(1) for both. The hash map plus doubly linked list is the answer: the map finds a node in O(1), the list moves it in O(1) because every node knows its neighbours. The rejected alternative is a map plus a timestamp with a scan for the minimum on eviction; that makes put O(n) and fails the first requirement. A heap keyed by last-use time is also rejected: updating an arbitrary heap entry is O(log n) and needs a position index of its own.

Sentinel nodes instead of null checks

The force is the number of edge cases in a linked list: empty list, single node, removing the head, removing the tail. Two permanent sentinel nodes for head and tail mean every real node always has a previous and a next, so unlink is three assignments with no branches. This is encapsulation of the hard part: callers of the list never see a sentinel. The alternative, nullable head and tail pointers, works but doubles the branch count and is where interview bugs live.

Hashability as the only key contract

Keys can be anything hashable. The cache does not care about ordering or comparison, only equality and hashing. Saying this when asked "what can a key be" shows you know what the dictionary actually needs.

5. Core flow and code

The sequence for put("c", 3) on a full cache of capacity 2 holding a then b (b most recent):

1. The cache looks "c" up in the index; it is absent.
2. The cache creates a Node, pushes it to the front of the list and records it in the index. Length is now 3.
3. Length exceeds capacity, so the cache pops the back node, which is a.
4. The cache deletes a from the index using the key stored on the popped node. Length is 2.

Step 4 is why the node stores its key: without it the cache would have to search the index for the node, which is O(n).

from dataclasses import dataclass
from typing import Dict, Generic, Hashable, Optional, TypeVar

K = TypeVar("K", bound=Hashable)
V = TypeVar("V")


@dataclass(eq=False)
class Node(Generic[K, V]):
    key: Optional[K]
    value: Optional[V]
    prev: "Optional[Node[K, V]]" = None
    next: "Optional[Node[K, V]]" = None


class DoublyLinkedList(Generic[K, V]):
    """Recency order. head.next is most recent, tail.prev is least recent."""

    def __init__(self) -> None:
        self.head: Node[K, V] = Node(None, None)
        self.tail: Node[K, V] = Node(None, None)
        self.head.next = self.tail
        self.tail.prev = self.head

    def push_front(self, node: Node[K, V]) -> None:
        first = self.head.next
        node.prev, node.next = self.head, first
        self.head.next = node
        first.prev = node  # type: ignore[union-attr]

    def unlink(self, node: Node[K, V]) -> None:
        node.prev.next = node.next  # type: ignore[union-attr]
        node.next.prev = node.prev  # type: ignore[union-attr]
        node.prev = node.next = None

    def pop_back(self) -> Node[K, V]:
        last = self.tail.prev
        if last is self.head:
            raise IndexError("pop_back on empty list")
        self.unlink(last)  # type: ignore[arg-type]
        return last  # type: ignore[return-value]


class LRUCache(Generic[K, V]):
    def __init__(self, capacity: int) -> None:
        if capacity < 1:
            raise ValueError("capacity must be at least 1")
        self.capacity = capacity
        self.index: Dict[K, Node[K, V]] = {}
        self.order: DoublyLinkedList[K, V] = DoublyLinkedList()

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

    def put(self, key: K, value: V) -> None:
        node = self.index.get(key)
        if node is not None:
            node.value = value
            self._touch(node)
            return
        node = Node(key, value)
        self.index[key] = node
        self.order.push_front(node)
        if len(self.index) > self.capacity:
            evicted = self.order.pop_back()
            del self.index[evicted.key]  # type: ignore[arg-type]

    def _touch(self, node: Node[K, V]) -> None:
        self.order.unlink(node)
        self.order.push_front(node)

    def __len__(self) -> int:
        return len(self.index)

    def __contains__(self, key: object) -> bool:
        return key in self.index


if __name__ == "__main__":
    c: LRUCache[str, int] = LRUCache(2)
    c.put("a", 1)
    c.put("b", 2)
    assert c.get("a") == 1          # a is now most recent
    c.put("c", 3)                   # evicts b, not a
    assert "b" not in c and c.get("c") == 3
    c.put("a", 10)                  # replace keeps size at 2
    assert len(c) == 2 and c.get("a") == 10

6. Extensions, concurrency and what interviewers probe

• The get-then-put trap. After get("a") on a full cache, the next put must evict b, not a. The test at the bottom of the code checks exactly this; write it first.
• Replace must not grow the cache. A put on an existing key updates the value and recency but never triggers eviction. Candidates who insert first and then check capacity evict a live entry.
• LFU follow-up. The same two-structure idea extends to least frequently used by keeping one list per frequency; that is its own problem, with the thread-safety twist Google adds.
• Thread safety. One threading.Lock around get and put is correct and simple, because even a read mutates the list. Say that a read-write lock does not help here for exactly that reason. Sharding the cache by key hash is the next step if contention matters, covered under locks and mutexes.
• Capacity of zero or negative. Reject in the constructor; a cache that can hold nothing silently is a bug factory.
• What gets marked down. Scanning the dictionary for the oldest key on eviction (O(n)), forgetting to store the key on the node, and leaving stale neighbour pointers on an unlinked node so a later move corrupts the list. Keeping unlink and push_front as the only two list mutations is what makes the class easy to test.

02Where this question was reported

• LeetCode Discuss · LeetCode 146 (Medium); top Google-tagged design problem (freq 56.8 in liquidslr CSV)
• Prepfully · Prepfully Google coding guide: most commonly reported; judged on clean implementation (hash map + DLL, helper methods), LFU follow-up
• LLD Mastery · Google-tagged (Easy)
• LLD Mastery · Google-tagged with Amazon/Microsoft/Meta/Netflix
• LLD Canvas · Google-tagged (also Amazon, Uber); dummy head/tail, update recency on get and put
• devshreebharatia.substack.com · Listed among design-style LeetCode problems Google asks
• Exponent / Aced · Aced/Exponent: 'Design a cache with LRU eviction' under API and low-level design
• thita.ai · thita.ai Google kit: 'Design a Byte-Bounded File LRU Cache' (~60 min)
• Codemia · Codemia Advanced
• GitHub · awesome-low-level-design, Medium
• systemdesign.academy · systemdesign.academy solved; also /lld/lfu-cache
• thita.ai · thita.ai: LRU (applied) and Thread-Safe LRU (advanced)