Design Data Structures

10 cards, about a minute. Read them the night before an interview, or right after the chapter to lock it in.

1. ◆what it is

   A design question = an API + a cost per method. Pick one structure per method's question, glue them with an invariant, keep them in sync on every call.

   #1
2. ↯use it when

   "Design X" or "implement the class" with methods like insert, get, pop, ls — and targets like O(1) or O(log n) per call.

   #2
3. { }template

   Routine: API → cost per method → structures → invariant as a comment → code each method → dry-run a script of calls.

   #3
4. { }template

   O(1) delete: values.set(i, last); indexOf.put(last, i); values.remove(size - 1); indexOf.remove(val);

   #4
5. O( )cost

   RandomizedSet O(1) avg · FreqStack O(1) avg · TimeMap set O(1) amortized, get O(log v) · file system O(depth · log c) · DetectSquares O(one column).

   #5
6. !trap

   Swap-with-last: update the moved element's index, and remove val from the map last — or deleting the last element breaks.

   #6
7. !trap

   list.remove(5) on a List<Integer> removes index 5, not the value 5. And "/a".split("/") starts with an empty string.

   #7
8. ✦pro tip

   Most frequent, newest wins → count → stack groups + a maxFreq that moves by ±1. Value at time t → floor search in a time-sorted history.

   #8
9. ✦pro tip

   Paths → a trie of names (TreeMap children give sorted ls). Shapes from stored points → count copies, loop over one column.

   #9
10. ✦pro tip

    Say average for HashMap and amortized for ArrayList.add. Then dry-run: empty, delete the last element, duplicates, a tie.

    #10

Shaky on a card? Open the chapter or flip its recall cards.