lru-cache

Difficulty: Medium · Topic: Linked List · Practice it on parikshan: /practice/lru-cache/start

The story

Redis runs maxmemory-policy allkeys-lru on tens of thousands of production clusters worldwide. When the cache fills, the policy evicts the least recently used key in roughly O(1). The internal data structure has to support, on every GET and SET:

look up a key in constant time,
mark it as most recently used in constant time, and
when capacity is exceeded, evict the least recently used key in constant time.

There is exactly one combination of primitives that achieves all three: a hash map for O(1) key lookup, plus a doubly-linked list for O(1) ordering updates and tail evictions. CDNs (Cloudflare, Akamai), CPU L1/L2 caches in microarchitecture, Memcached, MySQL's query cache, Apple's NSCache, browsers' HTTP cache, and Linux's page cache all use a structural variant of this.

lru-cache is the canonical version. It is the most complex problem in the Linked List cluster because the right data structure is itself the answer and you have to design it. The standard library has a shortcut (collections.OrderedDict in Python collapses the problem to ten lines), but the deep skill is implementing it from scratch, because the day you need an LRU in C, Java, Rust, or Go, the shortcut is not there.

What's actually being asked

Design a data structure LRUCache with three operations:

__init__(capacity): create the cache with positive integer capacity.
get(key): return the value if the key exists, otherwise -1. A get counts as a use; the key becomes the most recently used.
put(key, value): insert or update. If inserting exceeds capacity, evict the least recently used key first. A put makes the key the most recently used.

Both operations must run in O(1) average time. Up to 100,000 operations per test; capacity up to 3,000.

The naive approach

Option 1: a dict plus a Python list of keys in usage order. Every get and put does list.remove(key) (O(n)) and list.append(key) (O(1) amortised). Total O(n) per operation. Correct, slow; the parikshan stress test of 100,000 operations TLEs.

Option 2: a dict plus a usage timestamp on each entry, evicting by scanning for the min timestamp on overflow. Also O(n) per overflow. Same fate.

Option 3 (the Python shortcut): collections.OrderedDict. move_to_end(key) is O(1) and popitem(last=False) evicts the least recently used in O(1). Ten lines of code, fully correct, asymptotically optimal. Use it in real-world Python.

The parikshan-recommended path: implement option 3 from scratch with a hash map and a doubly-linked list. The OrderedDict shortcut is a wrapper around exactly that data structure inside CPython.

The key insight

The hash map provides random access. Given a key, it tells you the node holding that key's value, in O(1).

The doubly-linked list provides ordering with O(1) insert, O(1) delete given a node reference, and O(1) head/tail access. Most-recently-used at the head, least-recently-used at the tail (the convention varies; pick one and commit). The doubly-linked part is essential: a singly-linked list cannot delete a node in O(1) without re-walking, because you need the predecessor to fix its next pointer. A doubly-linked node has a prev pointer; deletion is two pointer reassignments.

get(key) becomes: hash-lookup the node, move it to the head, return the value. Two operations, both O(1).

put(key, value) becomes: if the key exists, update the node's value and move it to the head. If it does not exist, create a node, insert it at the head, add it to the hash map. If the cache now exceeds capacity, remove the tail node and delete its key from the hash map.

The trick that makes the linked-list code tractable: sentinel head and tail nodes. Allocate a head dummy and a tail dummy at construction. The real nodes live between them. Every operation operates on nodes that have non-null prev and next neighbours, eliminating the "is this the first node" and "is this the last node" branches the Linked List primer warns about.

Step-by-step approach

class Node:
    __slots__ = ('key', 'val', 'prev', 'next')
    def __init__(self, key=0, val=0):
        self.key = key
        self.val = val
        self.prev = self.next = None

class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.map = {}                                 # key -> Node
        self.head = Node()                            # sentinel; real MRU is head.next
        self.tail = Node()                            # sentinel; real LRU is tail.prev
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node):                          # detach node from list (O(1))
        node.prev.next = node.next
        node.next.prev = node.prev

    def _add_to_head(self, node):                     # insert just after head (O(1))
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    def _move_to_head(self, node):                    # remove + add: O(1)
        self._remove(node)
        self._add_to_head(node)

    def get(self, key):
        if key not in self.map:
            return -1
        node = self.map[key]
        self._move_to_head(node)
        return node.val

    def put(self, key, value):
        if key in self.map:                           # update path
            node = self.map[key]
            node.val = value
            self._move_to_head(node)
            return
        node = Node(key, value)                       # insert path
        self.map[key] = node
        self._add_to_head(node)
        if len(self.map) > self.cap:
            lru = self.tail.prev
            self._remove(lru)
            del self.map[lru.key]

Invariants:

The hash map and the linked list contain exactly the same set of keys.
head.next is the most-recently-used real node; tail.prev is the least-recently-used.
Both helpers _remove and _add_to_head operate on a node that is already (or about to be) properly linked at both ends; the sentinels guarantee non-null neighbours.

The reason Node stores key (not just val): when evicting, we need the key to delete from the hash map. Without key on the node, eviction is O(n) (you have to find which dict entry pointed to this node).

Worked example

LRUCache(2) (capacity 2):

Op	List (head→tail)	Map keys	Output
put(1, 1)	1	{1}	null
put(2, 2)	2 → 1	{1, 2}	null
get(1)	1 → 2	{1, 2}	1
put(3, 3)	3 → 1 (evict 2)	{1, 3}	null
get(2)	3 → 1	{1, 3}	-1
put(4, 4)	4 → 3 (evict 1)	{3, 4}	null
get(1)	4 → 3	{3, 4}	-1
get(3)	3 → 4	{3, 4}	3
get(4)	4 → 3	{3, 4}	4

Every operation: one hash lookup, at most two pointer adjustments. Constant time end-to-end.

Complexity

Time: O(1) average per get and put. Hash operations are O(1) average; doubly-linked list operations are O(1) worst case.
Space: O(capacity). One node and one hash entry per stored key, plus two sentinels.

The "average" caveat is the hash map's worst case (O(n) on a pathological collision avalanche). In CPython, dict resizing is amortised; Robin-Hood and open-addressing maps have stronger worst cases. For exam purposes, "O(1) amortised" is the correct phrasing.

Common pitfalls

Singly-linked list: O(1) insert but O(n) delete-by-node. Use doubly-linked. Almost every wrong agent-generated LRU starts with a single-linked list and accumulates branching to work around it.
Missing sentinels: the four edge cases (empty list, single node, MRU is the only node, LRU is the only node) all collapse to "I forgot to null-check". Two sentinels make all four go away.
Not storing key on the node: eviction becomes O(n) when you scan the map to find the dict entry that pointed to the evicted node.
Touching the LRU on get of a missing key: get for a missing key returns -1 and does not count as a use (because there is no node to move). Some agent code accidentally inserts a missing key.
Capacity ≤ 0: the spec excludes this. Defensive checks are over-engineering; trust the spec.
Updating the value but forgetting to move-to-head on put of an existing key: the key was just accessed; it should be MRU. A wrong cache that updates the value but leaves the node in its old position evicts the wrong key next.
Python OrderedDict shortcut on parikshan: legal and correct. But the deep skill is the from-scratch version. parikshan's integrity score is the same; your interview prep is not.

Where this shows up in the enterprise

Redis maxmemory-policy: as in the opening story.
CPU caches: hardware LRU approximations (pseudo-LRU, NRU) for L1/L2/L3.
CDNs (Cloudflare, Akamai, Fastly): edge-cache eviction in worker memory.
MySQL InnoDB buffer pool: LRU with a "young" / "old" sublist; the Linked List skeleton is the same.
Linux page cache: active and inactive LRU lists.
macOS NSCache / Foundation cache: same structure, language-specific wrapper.
Browser HTTP cache (Chromium, Firefox): per-origin LRU eviction of response bodies.
GPU shader cache: drivers use LRU on compiled-shader binaries.

Wherever a "keep the recently used, drop the stale" policy is enforced and the workload is hot enough that O(n) eviction is unacceptable, this exact structure is the answer.

Variants you'll see elsewhere

lfu-cache: Least Frequently Used. Two-dimensional structure (frequency buckets each holding their own LRU list). The doubly-linked list discipline carries over; the bucketing adds another hash map.
lru-cache-with-ttl: expiry on top of LRU. A min-heap of expiry times plus the LRU structure.
arc-cache: Adaptive Replacement Cache. Two LRU lists (recently-cached, recently-evicted) plus self-tuning. Backbone of NetApp's WAFL.
2q-cache: a fast-then-slow LRU variant. Two queues; nodes graduate between them.
clock-pro: a CPU-friendly LRU approximation using bitfields on a circular buffer.

Every cache replacement policy beyond FIFO is a refinement of this structure.

How parikshan turns this into a learning loop

lru-cache is the capstone of the Linked List cluster. Recommended sequence on parikshan:

Solve reverse-linked-list, middle-of-linked-list, remove-nth-from-end, and palindrome-linked-list first. The dummy-head and pointer-manipulation muscle memory is non-negotiable here.
In practice mode, AI off, code the from-scratch version with sentinels. Run public tests.
The dynamic private tests will throw: capacity 1 (every put evicts the previous), get-on-missing followed by put-on-same-key (must not double-insert), put-on-existing (update + move-to-head), 100,000 operations to verify O(1).
Solve the same problem using collections.OrderedDict as a sanity check. Compare line counts (~10 lines vs ~50). The OrderedDict version is the production answer in Python; the from-scratch version is the interview answer everywhere.
Re-solve in your weakest language (the Linked List primer mentions C, Java, Rust, Go specifically). The from-scratch version ports directly; the OrderedDict version does not exist.

In the AI-integrated workspace

LRU is the design problem where AI agents produce the widest spread of code quality. Three failure modes account for most wrong answers:

Singly-linked list: O(1) puts, O(n) gets. The 100,000-operation private test TLEs and the agent cannot explain why.
Missing key on the node: eviction is O(n). Same TLE, different surface.
Forget to move-to-head on update path: silently evicts the wrong key. The bug is invisible until a workload mixes get and put on the same key.

Verification ritual on every agent-generated LRU:

Find the node class. Does it have prev and next? Does it store key? If either is missing, refactor.
Find the sentinel head and tail. If they are not allocated in __init__, the four edge-case bugs are lurking.
Trace by hand: put(1, 1), put(2, 2), put(1, 10), put(3, 3), get(2). The expected output of the last get is -1 (because put(1, 10) made 1 the MRU; 3 then evicted 2). Wrong update-path code returns 2.
Ask: "what is the worst-case time of get?" The answer must be "O(1) amortised". If the agent says "O(n)" or hesitates, the algorithm is wrong.

The deeper lesson the LRU cache teaches: the right data structure IS the algorithm. Once you can compose hash maps with doubly-linked lists fluently, problems like LFU, ARC, and clock-pro stop being mysteries and become the same compositional exercise. Engineers who think this way design caches, schedulers, and storage engines; engineers who do not, copy from Stack Overflow and ship the wrong eviction policy. parikshan's Linked List cluster is engineered to take you from reverse-linked-list to designing your own cache structure in seven problems.