LLD: LRU Cache¶

Difficulty: Advanced | Time: 30–40 minutes

1. Problem Statement¶

Design an in-memory cache with a fixed capacity. When the cache is full and a new key is inserted, evict the least recently used entry. Both get(key) and put(key, value) must run in O(1) time.

This is the class-level version of the problem; Cache Strategies and Distributed Cache cover the same eviction idea at the system-design layer — where the cache lives, how it's sharded, what happens when a node holding the cache dies. Here, the constraint is purely algorithmic: one process, one thread of reasoning about a data structure.

2. Requirements¶

Functional (in scope):

• get(key) -> value | None — returns the value and marks the key as most-recently-used; None/miss if absent
• put(key, value) — inserts or updates; marks as most-recently-used; evicts the LRU entry if capacity is exceeded
• Fixed capacity, set at construction

Explicitly out of scope for v1: TTL-based expiry (a real addition, noted in Extensibility), persistence, distributed/multi-node caching (see Distributed Cache for that version of the problem).

3. Entities¶

Node (the linked-list element holding key + value), LRUCache (owns the hash map and the list).

4. Class Design¶

classDiagram
    class Node {
        +key: K
        +value: V
        +prev: Node
        +next: Node
    }

    class LRUCache {
        -capacity: int
        -map: Dict~K, Node~
        -head: Node
        -tail: Node
        +get(key) V
        +put(key, value) void
        -_remove(node) void
        -_add_to_front(node) void
    }

    LRUCache *-- Node : owns
    Node --> Node : prev/next (intrusive doubly linked list)

Why a hash map and a doubly linked list, not one or the other: a hash map alone gives O(1) get/put but has no notion of "order of use" — finding the LRU entry to evict would be O(n). A linked list alone gives O(1) reordering (move a node to the front) but O(n) lookup by key. Combining them is the entire trick: the hash map gives O(1) access to a node, and the doubly linked list gives O(1) reordering of that node once you have it — no scan required for either operation.

flowchart LR
    HEAD["head (MRU)"] <--> N1["Node: b"] <--> N2["Node: a"] <--> N3["Node: c"] <--> TAIL["tail (LRU)"]
    MAP["map: {'a': →N2, 'b': →N1, 'c': →N3}"] -.O(1) lookup.-> N2

5. Patterns Applied¶

• No Gang-of-Four pattern is the "right answer" here — this is a data-structure design problem, not a behavior-variation problem, and that distinction is itself worth stating out loud: not every LLD problem has a pattern waiting to be named, and reaching for one anyway (e.g. wrapping eviction in an unnecessary Strategy for a single, fixed policy) is the over-engineering failure mode called out in Design Patterns.
• Strategy legitimately earns its place only if the requirement is "support multiple eviction policies" (LRU today, LFU later) — see Extensibility below for exactly that variation.

6. Core Code¶

from threading import Lock
from typing import Generic, TypeVar

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


class Node(Generic[K, V]):
    __slots__ = ("key", "value", "prev", "next")

    def __init__(self, key: K, value: V):
        self.key = key
        self.value = value
        self.prev: "Node[K, V] | None" = None
        self.next: "Node[K, V] | None" = None


class LRUCache(Generic[K, V]):
    def __init__(self, capacity: int):
        if capacity <= 0:
            raise ValueError("capacity must be positive")
        self.capacity = capacity
        self._map: dict[K, Node[K, V]] = {}
        # sentinel head/tail avoid null-checks on every insert/remove
        self._head = Node(None, None)          # MRU side
        self._tail = Node(None, None)           # LRU side
        self._head.next = self._tail
        self._tail.prev = self._head
        self._lock = Lock()

    def _remove(self, node: Node[K, V]) -> None:
        node.prev.next = node.next
        node.next.prev = node.prev

    def _add_to_front(self, node: Node[K, V]) -> None:
        node.next = self._head.next
        node.prev = self._head
        self._head.next.prev = node
        self._head.next = node

    def get(self, key: K) -> V | None:
        with self._lock:
            node = self._map.get(key)
            if node is None:
                return None
            self._remove(node)
            self._add_to_front(node)            # mark as most-recently-used
            return node.value

    def put(self, key: K, value: V) -> None:
        with self._lock:
            if key in self._map:
                node = self._map[key]
                node.value = value
                self._remove(node)
                self._add_to_front(node)
                return

            if len(self._map) >= self.capacity:
                lru = self._tail.prev            # node just before sentinel tail
                self._remove(lru)
                del self._map[lru.key]

            node = Node(key, value)
            self._map[key] = node
            self._add_to_front(node)

Every operation — lookup (_map.get), reorder (_remove + _add_to_front, both pure pointer surgery), and eviction (_tail.prev, a direct pointer, not a scan) — is O(1). No loop anywhere in get or put.

7. Edge Cases¶

8. Concurrency¶

Unlike Parking Lot, where per-resource locking bought real concurrency, an LRU cache's get mutates shared list pointers on every call, including reads — a get isn't read-only, because it reorders the list. That structural fact changes the trade-off:

• A single lock around the whole cache (as in the code above) is the correct default here, not a premature pessimization — because get isn't actually read-only, a read-write lock wouldn't help: every get needs the same exclusive access a put does, since both mutate the linked list.
• What would make a finer-grained lock worth it: if reads vastly outnumbered writes and "most recently used" tracking could tolerate being slightly stale (e.g., approximate LRU via a periodic background sweep instead of pointer surgery on every read) — that's a real production technique (e.g., Redis's approximate LRU using random sampling) but it's a deliberate accuracy-for-throughput trade you should name explicitly, not silently substitute for exact LRU.
• Where a genuine race would bite without the lock: two threads both calling get on the same key concurrently could interleave their _remove/_add_to_front pointer writes and corrupt the list (a node's next/prev pointing somewhere inconsistent) — this is a worse failure mode than the parking-lot double-booking, because a corrupted linked list can silently break every subsequent operation, not just one contested resource.

9. Extensibility¶

Interview Questions¶

Key Takeaways¶

Previous: Elevator System | Next: LLD Problem Roadmap