LRU Cache Interview Design Talk Track
"Design an LRU cache" is one of the most common coding-design hybrids in interviews. It looks simple until eviction, updates, and O(1) requirements collide. This LRU cache interview design talk track gives you a structure, sample sentences, and a bug checklist so you can stay calm for 30–45 minutes.
What "LRU" means in one sentence
Least Recently Used: when the cache is full and you need space, evict the item that hasn't been read or written for the longest time. Every get or put that touches a key makes that key the most recent.
Clarify before coding (2–3 minutes)
Ask:
- Capacity is fixed at construction?
getreturns a sentinel (e.g.-1) on miss?puton an existing key updates value and recency?- Required time complexity? (Usually O(1) average for get/put)
- Thread safety required? (Usually no unless stated)
Opening line:
"I'll aim for O(1) get and put using a hash map from key to node, plus a doubly linked list ordered from most to least recently used."
The standard data structure
| Piece | Role |
|---|---|
HashMap<key, Node> | O(1) lookup of the list node |
| Doubly linked list | Recency order; move nodes to head on access |
| Dummy head / tail | Avoid null edge cases at ends |
capacity | Evict from tail when full on insert |
Node fields: key, value, prev, next (store key in the node so eviction can delete from the map).
Operation talk track
get(key)
- If key not in map → return miss sentinel
- Else move that node to the most-recent position (head)
- Return its value
put(key, value)
- If key exists → update value, move node to head, return
- Else create a new node, insert at head, add to map
- If size > capacity → remove tail's previous (true LRU), delete from map
Narrate moves as small helpers: remove(node), add_to_head(node), pop_lru().
Complexity
"Each get/put does a constant number of pointer updates and one hash map operation, so average time is O(1). Space is O(capacity)."
Edge cases checklist
- [ ] Capacity
0or1 - [ ] Get on empty cache
- [ ] Put when already at capacity
- [ ] Put updating an existing key (must refresh recency, no eviction)
- [ ] Repeated gets on the same key
- [ ] Evict then immediately get the evicted key (miss)
Dry-run a short script aloud:
"Capacity 2. put(1,a), put(2,b), get(1), put(3,c) → key 2 should be gone."
Common bugs
| Bug | Result | Fix |
|---|---|---|
| Singly linked list only | O(n) remove | Use doubly linked list |
| Forget to update map on eviction | Stale lookups | Delete key when popping LRU |
| Forget move-on-get | Wrong eviction order | Always move on successful get |
| Null at list ends | Crashes | Dummy head and tail |
| Evict on update of existing key | Wrong size behavior | Update path should not create a new entry |
Follow-ups you may hear
| Follow-up | Short answer direction |
|---|---|
| LFU instead of LRU | Frequency + recency structures; more bookkeeping |
| TTL / expiration | Min-heap or timing wheel plus map |
| Thread-safe cache | Lock striping or concurrent map + careful list ops; discuss tradeoffs |
Why not only OrderedDict? | Fine if language provides it—say it implements the same idea |
If your language has OrderedDict / LinkedHashMap, you can use it if you can explain the same invariants. Interviewers often still want the explicit list+map reasoning.
Implementation order (stay paced)
| Minutes | Focus |
|---|---|
| 0–5 | Clarify + state map + DLL approach |
| 5–15 | Node, helpers, get |
| 15–30 | put + eviction |
| 30–40 | Dry-run the capacity-2 script |
| 40+ | Follow-ups |
Soft practice note
LRU is mostly careful pointer work under observation. Timed rehearsal with narration helps more than re-reading diagrams. If you want a structured way to practice design-style coding prompts and stay composed under pressure, Luna Interview is built for rehearsal and prep—before the interview, not as a way around the rules during one.
Closing sentence you can reuse
"Hash map for O(1) access, doubly linked list for O(1) recency updates, dummy head and tail to keep removals simple—and every get/put refreshes order so eviction always pops the true LRU."
That's the talk track. Nail the dry-run, and the design reads as deliberate instead of lucky.
Rehearse with an AI interview copilot, then browse commonly reported interview questions.