← Design DS · guided lesson
Design Data Structures
the story
Design from the API (abstract data types)
Every tool here exists because something was too slow or broke without it. Here is what.
In 1974 Barbara Liskov and Stephen Zilles published "Programming with Abstract Data Types" at an ACM SIGPLAN symposium.
Their idea: describe a data type by the operations its users may call, and keep its representation hidden inside.
Liskov's 2008 Turing Award citation honours her contributions to programming language and system design, "especially related to data abstraction, fault tolerance, and distributed computing".
Every Java interface you use — List, Map, Deque — is this idea: one API, several representations behind it, each with its own costs.
the problem it solved
Code that reaches into a structure's fields everywhere can't change the structure without breaking. Fixing the operations first lets the inside change freely.
why it matters: without it
Without fixing the API and the per-method costs first, you polish one method and discover at the end that another one is O(n) — the most common way design rounds go wrong.
sources: Liskov & Zilles — Programming with Abstract Data Types (ACM SIGPLAN Notices 9(4), 1974) ↗ · ACM — Barbara Liskov, 2008 A.M. Turing Award ↗
also in this chapter: Array + index map (swap-with-last delete) · Group by count (a bucket per frequency) · Versioned values (floor lookup by time) · Tree of names (paths as a trie) · Counting map (store counts, not copies)
the idea
The idea in 30 seconds
A design question hands you an API (a class and its methods) and a cost for each method. Your job: choose the fields so that every method meets its cost.
You rarely invent anything. You compose pieces you already know: a HashMap to find, an array to pick by index, a stack for newest first, a TreeMap for nearest ≤ x, a trie for paths.
The glue is an invariant: one sentence about the fields that is true after every call. A method may break it for a moment, but restores it before it returns.
picture this
A database table with indexes. The table holds the rows, and you add one index for each query that must be fast; every insert or delete updates the table and all its indexes together. A design answer is the same: one store, one helper structure per fast method, all kept in sync.
watch it
Insert Delete GetRandom O(1): swap with the last
Predict mode is on. Before each step, guess what happens, then watch. Wrong guesses are fine; that is how it sinks in.
Insert Delete GetRandom O(1): swap with the last
Top: the ArrayList. Bottom: the HashMap from value to index. A remove copies the last value into the hole, fixes its index and drops the end — nothing shifts.
On this screen ← / → step the simulation. Use the buttons below to move through the lesson.
watch it
Maximum Frequency Stack: one stack per count
Predict mode is on. Before each step, guess what happens, then watch. Wrong guesses are fine; that is how it sinks in.
Maximum Frequency Stack: one stack per count
A value pushed f times sits once in each of groups 1…f. pop takes the top of the highest group: the most frequent value, and among ties the newest.
On this screen ← / → step the simulation. Use the buttons below to move through the lesson.
key idea 1 of 9
Read it once. Say it out loud once. Bas.
The routine: state the API → write each method's target cost → pick one structure per method's question → write the invariant over the fields → code method by method → dry-run a script of calls.
key idea 2 of 9
Read it once. Say it out loud once. Bas.
One question, one structure: find by key → HashMap · pick by position or at random → ArrayList · newest first → stack · oldest first → queue · smallest or largest → heap · nearest ≤ x, sorted order → TreeMap or a sorted list + binary search · by path or prefix → trie.
key idea 3 of 9
Read it once. Say it out loud once. Bas.
Swap with the last: an array can drop any slot in O(1) when order doesn't matter. Copy the last element into the hole, update its index in the map, remove the end.
key idea 4 of 9
Read it once. Say it out loud once. Bas.
Group by a changing count: keep value → count plus count → stack of values. A count moves by exactly 1 per call, so the top group is tracked with one integer, never searched.
key idea 5 of 9
Read it once. Say it out loud once. Bas.
Append-only history is sorted for free: when timestamps only grow, appending keeps each key's list sorted, and "value at time t" is a binary search for the floor.
key idea 6 of 9
Read it once. Say it out loud once. Bas.
Paths are tries of names: split /a/b/c on / and walk a tree of nodes, each mapping a name to a child. TreeMap children hand ls its names already sorted.
key idea 7 of 9
Read it once. Say it out loud once. Bas.
Count, don't copy: store item → how many copies and loop over a small candidate set (one column of points) instead of every stored item.
key idea 8 of 9
Read it once. Say it out loud once. Bas.
Say each method's cost precisely: HashMap is O(1) average, ArrayList.add is O(1) amortized, TreeMap is O(log n) worst case.
key idea 9 of 9
Read it once. Say it out loud once. Bas.
LRU Cache, Min Stack, Design Twitter, Implement Trie, Design Circular Queue and Design HashSet live in their own chapters. Practise them here as design rounds (see Also practise this here).
spot the pattern
When you see this, think this
"insert, delete and getRandom, all in O(1)"
HashMap value → index + ArrayList; delete by swapping with the last element
"pop the most frequent; on a tie, the most recent"
count map + map from count to a stack, plus maxFreq
"value at timestamp t", "latest version ≤ t", "snapshot"
Per-key history sorted by time + floor search (binary search or TreeMap.floorEntry)
"mkdir", "ls", paths like /a/b/c, nested names
Trie of names: each node maps a name to a child; TreeMap children for sorted output
+3 more signals on the chapter page
watch out
A trap or two
Many wrong answers in interviews come from small slips like these, not from the hard part.
- Swap-with-last: forgetting
indexOf.put(last, i)— the moved element keeps a stale index, and a later remove deletes the wrong slot. - Swap-with-last: calling
indexOf.remove(val)beforeindexOf.put(last, i). When val is the last element, the put brings it back.
quick check
One question. No pressure.
values = [10, 40, 30, 20] and indexOf maps each value to its index. You remove 40 by swapping with the last. What is values now, and what is indexOf.get(20)?
now try
Your first real problem
You know enough to try this one. Stuck? Use the hints; that is what they are for.
Insert Delete GetRandom O(1)
open the problem →recall
Flip a few cards
Answer in your head first, then flip. Grade yourself honestly; the schedule brings back what you forget.
What are the steps of the design-round routine?
Question 1: What are the steps of the design-round routine?
done
Lesson complete
Chalo, that is the core. The full chapter has the rest: cost tables, Java details and more problems.