LRU Cache

A cache keeps a small number of recent results so you do not recompute or refetch them. When it is full, something must go. Least recently used (LRU) eviction throws out the entry that has gone untouched the longest, on the bet that it is the least likely to be needed soon. Browsers, databases and CDNs all use variations of it.

As an interview problem it is a design question in disguise. A hash map gives O(1) lookup, but it has no idea which key is oldest. The solution pairs the map with a second structure that tracks recency, and the challenge is making both O(1). It is the most-asked problem that combines this section with the next one, Linked Lists.

The problem

Design a class LRUCache with a fixed capacity:

• get(key) returns the value stored for key, or −1 if it is not there. A successful get counts as a use.
• put(key, value) stores the value, replacing any old value for that key. It also counts as a use. If this adds a new key to a full cache, first evict the least recently used key.

Both operations must run in O(1) average time. Example with capacity 2:

The get(7) in row 3 is why 3, not 7, is evicted in row 4. And put(7, 71) updates a key that already exists, so nothing is evicted even though the cache is full.

Constraints: capacity up to 3,000; up to 2 × 10⁵ calls.

Clarifying questions

• Does put on an existing key count as a use? Yes — it moves that key to most recent.
• Does a failed get change anything? No.
• Can capacity be 0? Assume capacity ≥ 1.
• Thread safety? Not needed here; mention it as a follow-up.

Approach 1: a dict plus a list of keys in recency order

Keep values in a dict and a list of keys ordered from least to most recent. On every use, remove the key from the list and append it at the end; to evict, pop the front.

1class LRUCacheSimple:2    """Dict for values, list for recency. get and put are O(capacity)."""34    def __init__(self, capacity: int) -> None:5        self.capacity = capacity6        self.values: dict[int, int] = {}7        self.order: list[int] = []            # least recent first89    def get(self, key: int) -> int:10        if key not in self.values:11            return -112        self.order.remove(key)                # O(capacity) scan13        self.order.append(key)14        return self.values[key]1516    def put(self, key: int, value: int) -> None:17        if key in self.values:18            self.order.remove(key)19        elif len(self.values) == self.capacity:20            oldest = self.order.pop(0)        # O(capacity) shift21            del self.values[oldest]22        self.values[key] = value23        self.order.append(key)

It is correct, and it is the right first thing to say. But list.remove(key) scans for the key and then shifts everything after it, and pop(0) shifts the whole list. Each operation is O(capacity). With capacity 3,000 and 2 × 10⁵ calls, that is up to about 6 × 10⁸ element moves — and the problem explicitly asks for O(1).

The key insight

We need three operations to be O(1): find a key, move a key to the most-recent end, and remove the least-recent key. A hash map does the first. A list fails at the other two because removing from the middle means shifting.

A doubly linked list can remove any node in O(1) — if you already hold the node. Each node knows the node before it and the node after it, so unlinking it is two pointer writes, with no search and no shift. And "if you already hold the node" is exactly what the hash map provides: store key → node instead of key → value.

So the design is:

• A map from key to list node, for O(1) lookup.
• A doubly linked list of nodes in recency order: least recent at the front, most recent at the back.
• Each node stores its key as well as its value, so that when we evict the front node we know which map entry to delete.
• Two sentinel nodes, one at each end, so the list is never empty and inserting or removing never needs an "is this the first node?" branch. This is the dummy-head idea from the Linked Lists section, used at both ends.

Approach 2: OrderedDict

Python's collections.OrderedDict is exactly a hash map plus a doubly linked list, with O(1) move_to_end and popitem(last=False).

1from collections import OrderedDict23class LRUCacheOrdered:4    """OrderedDict remembers order and moves a key to the end in O(1)."""56    def __init__(self, capacity: int) -> None:7        self.capacity = capacity8        self.data: OrderedDict[int, int] = OrderedDict()910    def get(self, key: int) -> int:11        if key not in self.data:12            return -113        self.data.move_to_end(key)            # now the most recent14        return self.data[key]1516    def put(self, key: int, value: int) -> None:17        if key in self.data:18            self.data.move_to_end(key)19        self.data[key] = value20        if len(self.data) > self.capacity:21            self.data.popitem(last=False)     # drop the least recent

Time: O(1) average for both operations. Space: O(capacity).

Offer this, and say what it is made of. Many interviewers accept it; many then say "now build it without the library". Be ready for that.

Approach 3: hash map plus a hand-built doubly linked list

1class Node:2    """A doubly linked node that carries its own key, for eviction."""34    def __init__(self, key: int = 0, value: int = 0) -> None:5        self.key = key6        self.value = value7        self.prev: Node | None = None8        self.next: Node | None = None91011class LRUCache:12    """Hash map for O(1) lookup + doubly linked list for O(1) reordering."""1314    def __init__(self, capacity: int) -> None:15        self.capacity = capacity16        self.node_of: dict[int, Node] = {}17        self.oldest = Node()                  # sentinel before the least recent18        self.newest = Node()                  # sentinel after the most recent19        self.oldest.next = self.newest20        self.newest.prev = self.oldest2122    def _unlink(self, node: Node) -> None:23        node.prev.next = node.next24        node.next.prev = node.prev2526    def _append(self, node: Node) -> None:27        """Insert just before the newest sentinel."""28        last = self.newest.prev29        last.next = node30        node.prev = last31        node.next = self.newest32        self.newest.prev = node

The two helpers are the only places that touch pointers. _unlink makes the neighbours of node point at each other. _append puts node between the current last real node and the newest sentinel. Because the sentinels always exist, neither helper needs a check for None.

1    def get(self, key: int) -> int:2        node = self.node_of.get(key)3        if node is None:4            return -15        self._unlink(node)6        self._append(node)                    # touched, so now the most recent7        return node.value89    def put(self, key: int, value: int) -> None:10        node = self.node_of.get(key)11        if node is not None:                  # existing key: update and refresh12            node.value = value13            self._unlink(node)14            self._append(node)15            return16        if len(self.node_of) == self.capacity:17            victim = self.oldest.next         # least recent real node18            self._unlink(victim)19            del self.node_of[victim.key]      # why the node stores its key20        node = Node(key, value)21        self.node_of[key] = node22        self._append(node)

"Move to most recent" is always unlink, then append. Eviction takes the node right after the oldest sentinel. Updating an existing key returns early, before the capacity check, so an update never evicts.

Running the example operations through this class gives exactly the table in the problem section: 70, −1, −1, 71 for the four get calls, with keys 3 and then 5 evicted. The state after each call, printed from the linked list itself, matched the "cache after" column row for row.

Time: O(1) average per operation — one map lookup plus a constant number of pointer writes. Space: O(capacity) — one map entry and one node per key, plus two sentinels.

Edge cases

• Capacity 1: every new key evicts the previous one; the sentinels keep this branch-free.
• Updating a key in a full cache: must not evict anything. The early return in put guarantees it.
• get on a missing key: returns −1 and changes no order.
• Putting the same key repeatedly: each call updates the value and moves the node to the back; the map never grows.

Follow-ups

• LFU (least frequently used) cache: evict the key with the fewest uses, breaking ties by recency. Keep a map from key to node, a map from use-count to its own doubly linked list, and the current minimum count. Still O(1) per operation.
• Entries that expire after a time limit: store an expiry time in each node; on get, treat an expired node as missing and remove it.
• Many threads: wrap get and put in one lock. Note that get also writes (it reorders), so a read-write lock does not help as much as it seems.