LRU Cache — build the one behind functools.lru_cache
LRU Cache — from scratch
LRU = Least Recently Used. When cache is full and a new key arrives, the entry nobody touched in the longest time gets evicted. Default eviction policy for a reason: recent access predicts future access.
Python ships functools.lru_cache as a decorator. Building it yourself shows what's happening underneath.
How it works
Two structures cooperating:
- Look up key's value — hash map from key to node.
- Move to MRU, drop LRU — doubly-linked list, most recent at head, oldest at tail.
On get: look up node, splice out, re-insert at head. On put existing: same + overwrite. On put new past capacity: unlink tail's predecessor, delete its key.
Sentinel head + tail — real nodes always between them, so remove/add never null-check neighbours. Every op is four pointer writes with no branches.
Alternative: collections.OrderedDict with move_to_end + popitem(last=False). Three lines shorter. That's what CPython's lru_cache uses internally.
Common bugs
- Forgetting to remove from dict on eviction. Leaks memory.
- Move-to-front only on
put.getalso counts as a use. - No sentinels. Null-check hell.
- Capacity 0. Early return in
put.
Try it
- Rewrite using
OrderedDict. Confirm eviction order matches. - Add
stats()method returning hits, misses, size. Drive 1000 ops and print hit rate.
3 graded exercises
Write the code, click Check. We’ll tell you exactly what to fix.
- Exercise 1
Build an
LRUCacheclass with__init__(capacity),get(key), andput(key, value). Usecollections.OrderedDict.getreturns -1 when the key is missing. - Exercise 2
Extend the LRU cache so that when
putoverflows capacity, the least-recently-used entry is evicted. A freshputcounts as most-recent;geton an existing key also refreshes it. - Exercise 3
Add a
peek(key)method that returns the value forkey(or -1) WITHOUT marking it as recently used.getandputstill refresh recency and evict on overflow.