vizlearn

Design an LRU cache

Interview QuestionsBy Updated

Two structures, because neither alone gives you both operations in O(1). A hash map for lookup by key, and a doubly linked list for recency order — the map stores the node, so touching an entry unlinks and relinks it in constant time, and eviction is whatever sits at the tail.

Overview

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.

Dicts, sets & hashingCoding problemHard

Step through it

What to watch

  • A get is not read-only — it changes the order.
  • Eviction always takes the oldest, which is why order must be maintained.
  • The map stores the node, which is what makes unlinking O(1).

Say this out loud

"Hash map plus doubly linked list. The map gives O(1) lookup and holds the node itself, so I can unlink it in O(1) without scanning. Most recent at the head, evict from the tail. In Python I'd reach for OrderedDict and move_to_end."

Design an LRU cache

Design a cache with O(1) get and put that evicts the least recently used entry.

Why the list must be doubly linked

Removing a node in O(1) requires knowing the node before it. A singly linked list would need a scan to find the predecessor, which puts you back at O(n). The backward pointer is the whole reason for the extra memory.

Most implementations also use sentinel head and tail nodes, so no insertion or removal is ever a special case — the same trick as the dummy head in a linked-list delete.

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.

Run it in Python

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.

lru_cache.pyPython 3
Output
How the code works
  1. self.map = {}   # key -> NODEThe join between the two structures. Storing the node rather than the value is what turns "remove this key from the order" into a pointer update instead of a scan.
  2. self.head, self.tail = Node(), Node()Sentinels. With a real head and tail always present, unlinking never has to check for None — the same trick as the dummy head in a linked-list delete.
  3. get() calls _unlink then _push_frontA read mutates the structure. That surprises people, and it is the definition of "recently used" — a cache where reads did not count would be FIFO, not LRU.
  4. oldest = self.tail.prevEviction in O(1) because the order is maintained continuously. Searching for the least recently used at eviction time would be O(n) and defeat the whole design.
Change one thing
  • Change get so it does not reorder. You now have a FIFO cache, and the eviction sequence changes — run it and see.
  • Add a capacity=0 case. Every put should evict immediately; most implementations crash.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.


    



Check yourself
0 of 3
Answer without scrolling back up.
  1. Why does an LRU cache need a doubly linked list rather than a singly linked one?
  2. What does the hash map store as its value?
  3. Does a successful get change the cache?





 Cheat sheet
Design an LRU cache
Two structures, because neither alone gives you both operations in O(1). A hash map for lookup by key, and a doubly linked list for recency order — the map stores the node, so touching an entry unlinks and relinks it in constant time, and eviction is whatever sits at the tail.
INTERVIEW · vizlearn.in/interview/design-an-lru-cache.html
More in Interview
InterviewLongest consecutive sequenceInterviewSubarray sum equals kInterviewWhen should you use a set instead of a list?InterviewWhat happens if you modify a collection while looping over it?
About the author
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.
About VizLearnGitHubLinkedInContact