Data Structure Design
What is this?
Here someone hands you a wish list of operations — "add a number, remove a number, and give me a random one, all instantly" — and your job is to build a container that grants every wish at full speed. It is like designing a backpack with the perfect set of pockets so that whatever you reach for comes out immediately. The catch: one kind of pocket can't do it all, so you stitch two simple structures together and let each cover the other's weak spot.
💡 Fun fact: The LRU cache built in this chapter — a hash map glued to a doubly linked list — is exactly how real systems decide what to keep in fast memory. It powers browser caches, CPU caches, and databases like Redis, all to hit that magic O(1) lookup and eviction.
🔓 The 5 problems in this chapter are free. Sign in with Google or Microsoft to start solving.
Core idea: You're handed an API with required complexities and must build a structure that honors all of them at once. Since operations pull in different directions, the winning move is almost always to combine two simple structures so each does what it's best at — turning every operation into O(1) or O(log n).
The method
- List the operations and their target complexities. That's the spec.
- For each op, name the structure that makes it cheap (lookup → hash map; random index → array; ordering/recency → linked list/heap; windowed/versioned → ring buffer / history + bisect).
- If no single structure covers all ops, pair two and keep them in sync.
- State the invariant — what's always true between calls (e.g. "the map and the list reference the same nodes"). Bugs live where the invariant slips.
The five problems
| Problem | Structures combined | Key op made cheap |
|---|---|---|
| Design Circular Queue | array + head + count, % k |
O(1) bounded FIFO |
| Insert Delete GetRandom O(1) | dynamic array + value→index map | O(1) remove via swap-to-end |
| Design Hit Counter | 300 fixed buckets keyed by t % 300 |
O(1) windowed count, bounded memory |
| LRU Cache | hash map + doubly linked list | O(1) get/put + recency eviction |
| Snapshot Array | per-index (snap_id, val) log + binary search |
versioned read ∝ writes, not snaps×length |
The progression builds the core trick: Circular Queue introduces the ring; RandomizedSet the array+map pairing; LRU the canonical map+DLL combo; Hit Counter and Snapshot Array show the same "don't store more than you need" instinct for time windows and versions.
The recurring trade
No single structure is great at everything. A hash map finds fast but has no order; an array indexes fast but deletes slowly; a linked list reorders fast but can't random-access. Pair them — map+DLL, array+map — and each covers the other's weakness. That pairing is data-structure design.
📓 Draw it yourself
- LRU map+DLL. Draw the hash map pointing into a doubly linked list; promote on
get, evict the tail on overflow. - Swap-to-end. For RandomizedSet, delete a middle element by swapping with the last and popping — update the moved element's index.
Snap photos and embed them with the /host-diagrams skill.
Key takeaways
- Start from the API + complexities; pick structures that make each op cheap.
- Combine two structures when one can't do it all (map+DLL, array+map) — the defining pattern.
- Bound your memory: ring buffers for windows (Hit Counter), change-logs for versions (Snapshot Array).
- State and preserve the invariant linking the two structures — that's where bugs hide.
- Why interviewers love it: it's how real caches, queues, and indexes are actually built.
Order: Design Circular Queue → Insert Delete GetRandom O(1) → Design Hit Counter → LRU Cache → Snapshot Array.