From Hashing to LRU Caches
You'll learn to
- -Explain why a hashmap alone cannot implement a recency-based eviction policy
- -Describe how pairing a hashmap with a doubly-linked list gives O(1) get, put, and evict
- -Trace through an LRU cache's internal state across a sequence of operations
Back in the hashing tier you built a hashmap that gives O(1) average-case lookup by key. That solved "where is this value?" but it said nothing about "how recently was this value used?" Real production caches - page caches, connection pools, the query cache sitting in front of a database - have to answer both, because memory is finite: when the cache is full and a new item needs a slot, something has to be evicted, and evicting the wrong thing (the item you are about to need again) tanks your hit ratio. Level 11 asks you to build the algorithm almost every real cache uses to make that decision: Least Recently Used, or LRU.
The Problem: Hashmaps Have No Sense of Time
A plain dict stores unordered key-value pairs; nothing about it tells you which key was touched first versus a millisecond ago. You could scan every entry and check a "last used" timestamp on eviction, but that is O(n) per eviction - unacceptable when a cache is evicting thousands of times per second under load. You need a structure that keeps entries ordered by recency AND lets you jump straight to any entry by key. That is two different data structures doing two different jobs, wired together.
The Fix: A Doubly-Linked List Ordered by Recency
A doubly-linked list can keep items ordered from most-recently-used (the head) to least-recently-used (the tail), and because each node has both a prev and a next pointer, you can splice any node out of the middle in O(1) once you already have a reference to it - no traversal required. That "once you have a reference to it" is exactly what the hashmap supplies: map each key to a reference to its node in the list. Now get(key) looks up the node via the hashmap in O(1), then moves that node to the head of the list in O(1) since it was just used. put(key, value) either updates an existing node and moves it to the head, or creates a new node at the head; if the cache is now over capacity, the node at the tail - the true least-recently-used entry - is evicted, and its key is removed from the hashmap too.
Every operation here - hashmap lookup, linked-list splice - is O(1). That is the whole point: an LRU cache has to make an eviction decision on nearly every request without ever becoming the bottleneck itself.
How would you design a cache with O(1) get and put that evicts the least-recently-used item?
"I would keep a list of items and remove the oldest one when it's full."
"I'd pair a hashmap for O(1) key lookup with a doubly-linked list ordered by recency, so both the lookup and the eviction stay O(1) - the hashmap gives me the node directly, and the linked list lets me splice it in O(1) without scanning."
Why can't a hashmap alone implement LRU eviction?
Level 11: LRU Cache asks you to build exactly this data structure from scratch - a hashmap plus a doubly-linked list working together to give O(1) get, put, and eviction. No OrderedDict, no functools.lru_cache: wire up the node class and the pointer surgery yourself so the mechanism is not a black box the next time you reach for one.