What are Design Problems?
Design problems ask you to build a small stateful object rather than calculate one answer. The object receives a sequence of operations, and every operation can change what the next one should return.
You need to know the common operations of maps, linked lists, stacks, queues, and heaps. The short version is: translate each required operation into a time limit, then combine the smallest set of data structures that meets every limit.
The Core Idea: Design from Operations
Consider LRU Basic Operations with capacity 3. The cache must find a key quickly, move a recently used key to the front, and remove the least recently used key when full.
Can one ordinary array do all three in constant time? No. A map finds keys quickly, while a doubly linked list changes recency order quickly.
It is like a small library desk with a catalog and a return cart. The catalog tells us where a book is, while the cart order tells us which untouched book has waited longest.
How an LRU Operation Changes State
The Rule You Keep True
Every key in the map must have exactly one matching node in the linked order, and the order must match the eviction policy. After every operation, the most recently used LRU key is at one end and the least recently used key is at the other.
The policy changes the bookkeeping:
- LRU orders entries by most recent access.
- LFU groups or orders entries by access count, then uses recency to break ties.
- Min Stack stores extra minimum information with each stack state.
LFU Frequency Matters is the one that usually trips us up. Frequency alone is not enough because two keys can share the same count. The implementation needs a second rule, usually least recent within the lowest-frequency group.
Picking the Right Shape
From Rule to Code
- List every public operation and its required running time.
- Choose one data structure for lookup and another only when an operation still cannot meet its limit.
- Write the state invariant before implementing the methods.
- Update every structure inside the same operation.
- Test a sequence that exercises updates, capacity, eviction, and ties.
Each operation finishes after the bounded map and list work required by the policy, giving O(1) average LRU access and updates.
When to use it
- •The problem describes an object that must support several operations over time.
- •The required performance depends on combining more than one data structure.
- •Recent use, frequency, capacity, or eviction order affects future behavior.
- •The prompt asks you to implement a cache, iterator, scheduler, or stateful service.
How to identify it
- •The prompt gives method names such as `get` and `put` instead of one input and one output.
- •Each operation changes the state seen by later operations.
- •Several operations have explicit **O(1)** or **O(log n)** requirements.
- •No single standard data structure satisfies every required operation.
Key insights
- →Start from the required operations and their time limits before choosing data structures.
- →A map provides fast lookup, while a linked order provides fast recency changes for an LRU cache.
- →Every copy of the same fact must be updated together after each operation.
- →Sentinel nodes remove special cases at the ends of a linked list.
- →An invariant is more useful than a diagram of classes because it describes valid state after every call.
Common mistakes
- 01Choosing a data structure before listing the operations it must support.
- 02Updating the map but forgetting to update the linked order, or doing the reverse.
- 03Treating an update to an existing key like an insertion without refreshing its recency.
- 04Evicting the wrong key when LFU entries share the same frequency.
- 05Adding abstractions that do not support a stated operation or invariant.