Designing Data Structures
Intermediate · 26 min read · Problem-Solving Patterns, Design, Matrices & Advanced Topics
LRU and LFU caches, O(1) random sets, time-based maps and iterators — combine two structures.
"Design an LRU cache" is one of the most-asked interview questions there is, and it frightens people because it doesn't look like an algorithm problem. There's no array to scan and no pattern name in the statement, just a class with methods that must all run in O(1).
The method: list the operations, then pair structures
Write each required operation next to the structure that does it fast:
LRU cache: hash map + doubly linked list
The map stores key → list node, so after a lookup you can unlink the node directly, without searching.
LFU cache: three maps and a minimum counter
Now we need, in O(1):
Insert, delete, get random, all in O(1)
The order of the two index updates matters when val is the last element. Writing index.put(last, i) first and index.remove(val) second handles that case correctly. The tests in the reference solution cover it.
Time-based key-value store: map + sorted list
Timestamps arrive in increasing order, so each key's list of timestamps is already sorted. A get is a binary search for the last timestamp that isn't too big:
Iterators: hold the next element
Iterator problems all ask you to compute lazily: produce the next element only when asked. The trick is to keep one element of look-ahead (or a stack of positions) inside the object.
Design problems at a glance
Practice ladder
Interview questions
- Why does an LRU cache need both a hash map and a doubly linked list?
- How do you remove an arbitrary element from an array-backed set in O(1)?
Further reading
Key takeaways
- Design problems = list the operations, then combine two structures whose strengths cover each other.
- LRU: hash map to doubly linked list nodes, sentinels, node stores its key.
- LFU: count to LinkedHashSet buckets plus a minFreq that only resets or steps up.
- O(1) delete from an array: swap with the last element and update the index map.
- Iterators compute lazily: buffer one element or keep a stack of iterators; hasNext must be safe to repeat.