1Understand
The idea
Start from the complexity each operation must have, then combine structures so that each covers what the others cannot. An LRU cache pairs a hash map (find in O(1)) with a doubly linked list (reorder in O(1)); a min stack keeps the running minimum next to each value. Write down the invariant that ties them together.
Intuition
Start from the complexity each operation must meet, then combine structures so each covers what the others cannot. An LRU cache pairs a hash map (O(1) find) with a doubly linked list (O(1) move-to-front). A min stack stores the running minimum beside each value.
Write down the invariant that ties the pieces together, e.g. "map key → node address; list order is recency." Without the invariant, the design drifts.
Interview design problems are less about clever algorithms and more about honest complexity bookkeeping.
What you will be able to do
- Pick structures from the complexity targets
- Keep all internal structures in sync
When to use it
- Design a class with operations in O(1)
- Cache with eviction
- Stack or queue with extra queries
2See it
Walkthrough
O(1) set with delete
list + idx map, swap-remove the value.
1 / 6
idx
- 1→ 0
- 2→ 1
- 3→ 2
Array stores values; map stores indices for O(1) lookup.
Live template
Line 1 active
Complexity: time O(1) per op (target), space O(n)
Target O(1) or O(log n) per operation as stated. Using list.remove (O(n)) behind a dict quietly breaks LRU. Tree maps give O(log n) ordered ops when O(1) is impossible.
Read the walkthrough as text
LRU cache. Capacity 2; operations put(1,1), put(2,2), get(1), put(3,3), get(2).
- After two puts: list order
1,2(2 most recent), map holds both. get(1)moves1to front → order2,1.put(3,3)evicts least recent2; map deletes2; list1,3.get(2)misses →-1.
Hash map alone cannot reorder in O(1); a list alone cannot find in O(1). Together they can.
3Recognise it
Kinds of problems (11)
Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.
Min stack
Example. Stack with getMin in O(1).
How. Secondary stack tracks running minimum on each push.
Queue from two stacks
Example. FIFO using two stacks.
How. Pour in-stack to out-stack when out empty on pop.
LRU cache
Example. Capacity-limited cache evicts least recently used.
How. OrderedDict or hash + doubly linked list: move to end on access.
Insert / delete / get-random in O(1)
Example. RandomizedSet with uniform random.
How. List plus index map; swap delete with last for O(1) remove.
Time-based key-value store
Example. Get key at timestamp.
How. Map key → sorted list of (timestamp, value); binary search floor timestamp.
Iterator design
Example. Peeking iterator or flatten nested list iterator.
How. Stack of pending elements; advance to next valid on hasNext.
Hash map from scratch (buckets and resizing)
Example. Design hash map with chaining.
How. Buckets of (key, value); resize when load factor exceeds threshold.
Frequency buckets (LFU cache, max-frequency stack)
Example. LFU cache eviction.
How. Map key→node; buckets by freq; evict from min freq bucket LRU.
Circular buffer (circular queue)
Example. Fixed-size queue with head/tail modulo capacity.
How. Array with front/rear indices; full when (rear+1)%cap == front.
History navigation (browser history, undo)
Example. Visit, back, forward stack design.
How. Stack back; move current to forward stack on visit; clear forward on new visit.
Several maps working together (check-in systems, feeds)
Example. All-one data structure or tweet counts per user.
How. Split roles: global count map + per-key freq map stay in sync on changes.
Common mistakes
Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.
Structures out of sync
Why it happens. One structure is the source of truth.
How it fails. LRU: delete key from dict but node stays in linked list, ghost entries.
Fix. Every mutating op updates all paired structures in one transaction.
Linear-time operation
Why it happens. n is small in examples so scanning is fine.
How it fails. getRandom scans list O(n), violates O(1) spec at scale.
Fix. Meet each op target: hash+list swap-delete, OrderedDict move_to_end, etc.
Capacity edge case
Why it happens. Evict then insert is the same as insert then evict at capacity.
How it fails. LRU at cap: put existing key evicts LRU before updating, wrong key removed.
Fix. Update existing key without eviction; evict only on new key when full.
4Check yourself
Concept check
A short quiz on this lesson before you practise. Optional, and it does not gate coding.
Ready to practise?
Mastery comes from solving. The lesson is optional context.