Design an LRU Cache

1. Problem & Why It's Asked

The single most common LLD warm-up because the "obvious" solution (a dict) doesn't give O(1) eviction, and the correct solution (hash map + doubly linked list) is a specific, well-known composition of data structures — this problem tests whether you know that composition, not whether you can invent it live.

2. Requirements

Functional: get(key) -> value and put(key, value), both O(1). Fixed capacity; when full, evict the least recently used entry before inserting a new one. get and put both count as "using" a key (move it to most-recently-used position).

Non-functional: true O(1) per operation (not amortized, not O(log n)) — this rules out a sorted structure. Thread-safety as a common follow-up.

3. The Fast Path: Python's OrderedDict

For an interview where the interviewer accepts using a language's built-in ordered-dict semantics, this is the correct first answer — but be ready for the follow-up "now implement it without OrderedDict", which is what section 5 is for.

from collections import OrderedDict

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

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)   # mark as most recently used
        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 least-recently-used (front of order)

OrderedDict internally maintains a doubly linked list alongside its hash table — which is exactly why move_to_end and popitem(last=False) are both O(1). Knowing why this works, not just that it does, is what separates "I memorized this" from "I understand the underlying structure."

4. Class Diagram (from-scratch version)

classDiagram
    class Node {
        +int key
        +int value
        +Node prev
        +Node next
    }
    class LRUCache {
        -int capacity
        -dict~int,Node~ map
        -Node head
        -Node tail
        +get(key) int
        +put(key, value)
        -_remove(node)
        -_add_to_front(node)
    }
    LRUCache "1" --> "*" Node
    Node --> Node : prev/next

5. From-Scratch Implementation (the real follow-up)

Hash map gives O(1) key lookup; doubly linked list gives O(1) reordering (move-to-front) and O(1) eviction (remove from the tail) — neither alone achieves both.

class Node:
    __slots__ = ("key", "value", "prev", "next")
    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value
        self.prev: "Node | None" = None
        self.next: "Node | None" = None


class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.map: dict[int, Node] = {}
        # sentinel head/tail avoid null-checks on every insert/remove
        self.head = Node()
        self.tail = Node()
        self.head.next = self.tail
        self.tail.prev = self.head

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

    def _add_to_front(self, node: Node) -> None:
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

    def get(self, key: int) -> int:
        if key not in self.map:
            return -1
        node = self.map[key]
        self._remove(node)
        self._add_to_front(node)          # mark as most recently used
        return node.value

    def put(self, key: int, value: int) -> None:
        if key in self.map:
            self._remove(self.map[key])

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

        if len(self.map) > self.capacity:
            lru = self.tail.prev            # least-recently-used = just before sentinel tail
            self._remove(lru)
            del self.map[lru.key]

Why sentinel head/tail nodes: without them, _remove/_add_to_front need special-casing for "list is empty" or "removing the only node" — sentinels make every real node have a real prev and next, unconditionally, which is what makes the removal/insertion logic branch-free.

6. Thread Safety

Neither version above is thread-safe as written — two threads calling put concurrently can corrupt the linked list (a classic lost-update on head.next/tail.prev). Fix:

import threading

class ThreadSafeLRUCache(LRUCache):
    def __init__(self, capacity: int):
        super().__init__(capacity)
        self._lock = threading.RLock()   # RLock: get/put don't call each other here,
                                          # but RLock is the safe default if that changes later

    def get(self, key: int) -> int:
        with self._lock:
            return super().get(key)

    def put(self, key: int, value: int) -> None:
        with self._lock:
            super().put(key, value)

A single lock serializes all access — correct, and the right starting answer. The scaling follow-up ("this cache is hit by thousands of threads/sec") is sharding: partition keys across N independent LRUCache instances (shard = hash(key) % N), each with its own lock, trading a slightly wrong global LRU ordering (only exact within a shard) for much lower lock contention — the same shard-vs-single-lock trade-off that shows up in [[Database Replication & Sharding]] and [[Rate Limiter (OOD)]].

7. Complexity

8. Variants Worth Knowing

• LFU (Least Frequently Used) instead of LRU — evict by access count, not recency. Needs a frequency-bucketed structure (dict of frequency → doubly linked list of keys at that frequency) to stay O(1); a common "now make it LFU" follow-up.
• TTL-aware LRU — entries also expire after a fixed time regardless of recency; requires checking/lazily purging expired entries on access, or a background sweep.

9. Interview Drills

1. Why not just use a plain dict and track a separate "last used" timestamp per key? — Eviction would require scanning all entries to find the minimum timestamp — O(n), not O(1). The doubly linked list makes "find the least recently used" an O(1) pointer read (tail.prev) instead of a scan.
2. How would you make this an LFU cache instead? — Track an access-frequency count per key; maintain a dict from frequency → doubly-linked list of keys at that frequency, plus a pointer to the current minimum frequency. On access, move the key from its old frequency's list to freq+1's list, updating the minimum-frequency pointer if the old list becomes empty. Same O(1) discipline, more bookkeeping.
3. Scale this to a distributed cache serving many app servers. — This is now the [[Caching & Redis]] problem, not the in-process LRU problem — Redis itself uses approximate LRU (samples N random keys, evicts the least recently used among the sample) rather than true LRU, trading a small accuracy loss for avoiding the overhead of a fully precise global ordering across a distributed store.

Cross-links

[[Caching & Redis]] · [[OOD Design Patterns]] · [[Rate Limiter (OOD)]] · [[Database Replication & Sharding]]