Design an LRU Cache
You'll learn to
- -Explain why a hash map plus a doubly linked list gives constant-time get and put
- -Trace the cache by hand through a sequence of operations, and see which key is evicted
- -Name the follow-ups: why get needs a lock too, and how an eviction policy becomes a Strategy
A cache keeps a small number of things close at hand so you do not have to fetch them again. LRU stands for Least Recently Used: when the cache is full and a new item arrives, throw out the item that has gone the longest without being used. This is as much a data-structures problem as an object-design problem, which is why it is a favorite. It tests whether you can combine two data structures to hit a speed target, then wrap them in a clean class.
An Analogy: The Pile on Your Desk
Your desk holds only a few books. Whenever you use a book, you put it on top of the pile. When the desk is full and you need space, you take the book at the bottom, the one you have not touched for longest. The pile is the recency order. Two problems remain: finding a book anywhere in the pile quickly, and moving it to the top without lifting the others. An index card box (a hash map) solves the first, and a pile where each book is hooked to its neighbors (a doubly linked list) solves the second.
The Speed Requirement That Drives the Design
Both get(key) and put(key, value) must take O(1) time, which means constant time: the work does not grow as the cache holds more items. A hash map alone finds a key instantly, but knows nothing about recency. A linked list alone can move a node to the front in constant time, but finding a node by key means walking the list, which is O(n), the cost growing with the list. Combine them: the map points straight at the node, and the list does the reordering.
The Combined Structure
A doubly linked list is a chain where every link knows both its previous and next link, so you can unhook any link in one step. Here the front of the chain is the most recently used and the back is the least. The code below is complete and runnable. After the class, a short script exercises it.
Trace it by hand to see why. The front of the list is shown first.
- -put(1): the list is [1].
- -put(2): the list is [2, 1].
- -get(1): key 1 is used, so it moves to the front: [1, 2].
- -put(3): the list becomes [3, 1, 2], which is over capacity 2, so the back (key 2) is evicted: [3, 1].
- -get(2): key 2 is gone, so the answer is -1.
Why Dummy Head and Tail Nodes
The dummy (sentinel) head and tail are two permanent placeholder nodes at the ends of the list. They exist only to remove edge cases. Without them, adding to an empty list or removing the last real node needs special checks for a missing neighbor. With them, _remove and _add_to_front work the same whether the list holds 0, 1 or 1,000 real nodes. Interviewers notice that kind of edge-case removal.
Follow-Up: Thread-Safety
Both get and put change shared state: the map and the list pointers. Under concurrent use, a single lock around both methods is the simple and correct starting point. The deceptive part is that get looks like a read, but it moves a node to the front, so it changes the recency order and needs the lock too.
Follow-Up: A Pluggable Eviction Policy
If asked to support LFU (Least Frequently Used) as well, which evicts the item used the fewest times, treat it as a Strategy opportunity. Extract an EvictionPolicy interface with on_access() and evict(), let LRUPolicy and LFUPolicy each keep their own bookkeeping, and make the cache depend only on the interface.
Say explicitly that get is not a pure read, because it changes recency order. Flagging that unprompted shows you understand why both methods need the lock, not only put.
Interview Signal is part of Pro
See a real weak answer next to a real strong one for this exact topic.
Quiz is part of Pro
Test what you just read with a short quiz, and bank the XP.
Forge Level 40: LRU Cache asks you to implement get()/put() with O(1) least-recently-used eviction, graded by running your actual code against real test cases.
Discussion0
Join the Discussion
Sign in to leave comments, reply to others, or like insights.
No comments yet. Be the first to start the thread!