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.
Design Hit Counter
Core idea: You only ever care about the last 300 seconds, so you never need more than 300 numbers. Keep a fixed ring of 300 buckets keyed by
timestamp % 300, and every operation is O(1) with memory that never grows — no matter how hard the traffic hammers you.
1. The problem, in a fresh setting
You're running the metrics box behind a popular API gateway. Each time a request lands, the gateway calls hit(timestamp). Your dashboard polls getHits(timestamp) and wants one number: how many requests came in during the last 5 minutes — that is, with timestamps in the window (t - 300, t].
Timestamps arrive in seconds and are monotonically non-decreasing (each call's timestamp is >= the previous one — that's how wall-clock time works). Several hits can share the same second during a burst.
Implement HitCounter:
| Operation | Meaning |
|---|---|
HitCounter() |
construct an empty counter |
hit(timestamp) |
record one hit that happened at timestamp (seconds) |
getHits(timestamp) |
return the number of hits in the last 300 seconds, i.e. with timestamp in (timestamp - 300, timestamp] |
Example trace:
| Call | Returns | Why |
|---|---|---|
hit(1) |
— | a hit at second 1 |
hit(2) |
— | a hit at second 2 |
hit(3) |
— | a hit at second 3 |
getHits(4) |
3 | window is (−296, 4] → all three count |
hit(300) |
— | a hit at second 300 |
getHits(300) |
4 | window (0, 300] → seconds 1,2,3,300 |
getHits(301) |
3 | window (1, 301] → second 1 just aged out |
That last row is the whole game: at t = 301 the hit at second 1 falls outside (1, 301] and must silently disappear.
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