Run it: Design an LRU cache in code
The from-scratch version with sentinel nodes, the OrderedDict version, and both run through the same sequence of operations so their answers can be compared.
The full cache wires get and put on top of those two pointer helpers, evicting any sits just before the tail sentinel once the map grows past capacity.
The implementation
Touching key 1 makes 2 the least recently used, so the next insert evicts it. The second block rebuilds the same cache and continues from there.
The line to point at is del self.map[lru.key]. Evicting from the list without removing from the dictionary leaves a dangling entry. And the cache reports hits for items it has discarded. That is why the node stores its own key. The list gives you the node. And you need the key to clean up the map.
Why one structure is not enough
A dictionary gives O(1) lookup and knows nothing about order. A list keeps order and needs O(n) to find and remove an arbitrary element. The requirement is both at once, so you carry both.
The join between them is the important part: the map's value is not the cached value, it is the node in the linked list. That is what lets you go from a key straight to its position and unlink it without walking anything.
Why the list must be doubly linked
To move a node to the front on access, it must be unlinked from its current position — which requires knowing its predecessor.
In a singly linked list, finding the predecessor means walking from the head: O(n). A doubly linked list stores prev, so unlinking is four pointer assignments and O(1).
That is the specific reason for the "doubly" in the answer, and being able to say it is what distinguishes understanding from recall.
The other implementation detail worth building in from the start is sentinel nodes. A dummy head and tail. They remove every special case for inserting at the front, removing from the back, and handling an empty list. This is where a hand-rolled version usually breaks.
The Python answer
collections.OrderedDict is exactly a dict plus a doubly linked list, and it exposes move_to_end and popitem(last=False). That is the version to write in real code, and the ten-line implementation is a fine answer if you can also explain what it is doing underneath.
Say which one the interviewer wants. "Implement it from scratch" means the nodes; "use it" means OrderedDict, or functools.lru_cache if it is memoisation rather than a cache you control.
The Python shortcut
OrderedDict maintains insertion order with O(1) reordering, which collapses the whole implementation:
move_to_end and popitem(last=False) are both O(1), because OrderedDict is itself a dict plus a doubly linked list. The same design, provided by the standard library.
In an interview, write the manual version unless told if not; the question is about the data structure choice. Mentioning OrderedDict afterwards shows you know the library, and mentioning functools.lru_cache — which is a C implementation of this for function memoisation — shows you know where it is already used.
Eviction policies
LRU is one choice among several, and knowing the options is a common follow-up.
| Policy | Evicts | Good when |
|---|
| LRU | Least recently used | Recent access predicts future access |
| LFU | Least frequently used | Some items are persistently popular |
| FIFO | Oldest inserted | Simple; access does not matter |
| MRU | Most recently used | Sequential scans that will not revisit |
| Random | An arbitrary item | Cheap, and surprisingly competitive |
| TTL | Anything expired | Freshness matters more than recency |
| ARC / 2Q | Adaptive between recency and frequency | Mixed workloads |
LRU's weakness is a sequential scan larger than the cache: it evicts all of it useful while caching items that will never be read again. That is the case LFU and the adaptive policies exist to handle, and databases use variants of 2Q or ARC for exactly this reason.
LFU's weakness is the mirror image: an item popular once stays cached forever unless counts decay.
Making it production-ready
An interview answer stops at the data structure. The follow-up questions usually go here:
Thread safety. Every operation mutates both structures, so concurrent access needs a lock. And a single lock makes the cache a contention point. Sharding by key hash into several on its own-locked caches is the standard fix.
Memory limits by size, not count. Real caches bound total bytes. So each entry carries a size and eviction continues until the total fits.
TTL alongside LRU. Entries expire on time and on pressure. This usually means a lazy check on access plus a background sweep.
Metrics. Hit rate is the number that justifies the cache's existence, and eviction rate shows whether it is too small.
Distributed caching. Once there are several machines, consistent hashing decides which node owns a key, and invalidation becomes the hard problem.
For the underlying ideas, see hash tables, linked lists and time complexity.