Design & Data Structures
Design custom data structures that combine standard components to achieve specific time/space complexity guarantees.
Core Concepts
Design problems test your ability to combine multiple data structures to achieve all required operations efficiently. Classic problems include:
- LRU Cache: HashMap + Doubly Linked List → O(1) get and put.
- LFU Cache: Two HashMaps + Doubly Linked Lists → O(1) operations.
- Min Stack: Stack + auxiliary stack tracking minimums.
- Trie (Prefix Tree): Each node stores children map + isEnd flag.
- Iterator Design: Flatten/traverse complex structures lazily.
- Randomized Set: HashMap + ArrayList → O(1) insert, delete, getRandom.
Cheatsheet Formulas
- LRU Cache: HashMap<key, Node> + DLL. On get/put → move node to head. On capacity → remove tail.
- Trie insert: For each char, create node if absent. Mark last node as end.
- Trie search: Traverse char by char. Return false if any node missing.
- RandomizedSet: Map stores key→index in list. Swap with last on delete.
- Median Finder: Max-heap (lower half) + Min-heap (upper half). Balance sizes on insert.