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.
Insert Delete GetRandom O(1)
Core idea: Keep the elements in a plain array so you can grab a random index in O(1), and keep a hash map
value → indexso you can find any element in O(1) — the only tricky part, deleting from the middle of an array without leaving a hole, is solved by swapping the victim with the last element and popping the tail.
This problem is a small gem because it forces you to admit that no single built-in data structure does everything you need. A set gives O(1) membership but can't hand you a uniformly random element in O(1). A list gives O(1) random indexing but O(n) removal. The interview is really asking: can you combine two structures so each covers the other's weakness? Let's build it up from the clumsy single-structure attempts to the clean two-structure answer.
Problem, rephrased
Imagine you're running a live raffle drum at a fair.
- A new ticket can be dropped in the drum with
insert(ticket). If that exact ticket is already inside, nothing changes and you report "already in" — no duplicate tickets allowed. - A ticket can be pulled out by name with
remove(ticket)(someone left early and wants their ticket back). If it isn't in the drum, you report "not found." - At any moment the announcer spins the drum and
get_random()must return a ticket, with every ticket currently inside equally likely to come out.
The drum is constantly changing — tickets going in and out all evening — and every one of these three actions must feel instant (average O(1)), no matter how full the drum gets.
| Operation | Input | Returns | Behavior |
|---|---|---|---|
insert(x) |
a value | True if newly added, False if already present |
no duplicates |
remove(x) |
a value | True if removed, False if absent |
must not break O(1) random access |
get_random() |
— | a value currently stored | uniformly random over the current set |
The get_random() row is what rules out the obvious answers, and the remove(x) row is where all the cleverness lives.
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson