Choosing the Right Data Structure — Revision Notes
Half of algorithm interviews are really "pick the right data structure." The optimal solution usually falls out once you choose a structure whose strengths match the operations the problem needs most (fast lookup? ordering? min/max? prefix?).
Match structure to need
| Need | Reach for |
|---|---|
| O(1) lookup / dedup / seen-before | Hash set / hash map |
| Ordered data, range queries | Sorted array / balanced BST / TreeMap |
| Repeated min or max | Heap (priority queue) |
| LIFO / undo / matching brackets | Stack |
| FIFO / BFS / sliding window | Queue / deque |
| Prefix relationships, autocomplete | Trie |
| Connectivity / grouping | Union-Find (DSU) |
Ask: which operation runs most often? Optimise the structure for that.
Exam Tricks & Tips
- 🎯 "Have I seen this before?" → hash map. Counting, deduping, two-sum all scream hashing.
- 🎯 "Repeatedly need the smallest/largest" → heap. Top-K and merge-K problems are heap tells.
- 🎯 "Matching / most-recent" → stack. Brackets, next-greater-element, undo.
- 🎯 "Shortest path in unweighted graph / level order" → queue (BFS).
- 🎯 State the trade-off — a hash map costs O(n) space to buy O(1) time; say so.
- ❌ Common mistake: forcing arrays everywhere and getting O(n²) when a hash map would give O(n).
Expected pattern: Implicit in most problems; sometimes explicit ("what data structure would you use and why?").
Quick recap: Identify the most-frequent operation, then pick the structure that makes it cheap; state the space/time trade-off.
Choosing the Right Data Structure — Flashcards (Interview Prep)
Cover the answer, recall, then check. 11 cards on choosing data structures.
Q1. What is half of algorithm interviews really about?
A1. Choosing the right data structure for the operations the problem needs most.
Q2. Signal for a hash map/set?
A2. "Have I seen this before?" — counting, deduping, or two-sum problems.
Q3. Signal for a heap (priority queue)?
A3. Repeatedly needing the smallest or largest — Top-K, merge-K.
Q4. Signal for a stack?
A4. Matching or most-recent logic — brackets, next-greater-element, undo.
Q5. Signal for a queue/BFS?
A5. Level-order traversal or shortest path in an unweighted graph.
Q6. Structure for prefix/autocomplete problems?
A6. A Trie.
Q7. Structure for connectivity/grouping?
A7. Union-Find (Disjoint Set Union).
Q8. Structure for ordered data with range queries?
A8. Sorted array, balanced BST, or TreeMap.
Q9. Key question to pick a structure?
A9. Which operation runs most often? Optimise for that one.
Q10. Trade-off to state when using a hash map?
A10. It spends O(n) space to buy O(1) lookups — say so explicitly.
Q11. Common mistake in structure choice?
A11. Forcing arrays everywhere and getting O(n²) where a hash map gives O(n).
Choosing the Right Data Structure
Most coding-interview optimisations come down to one move: picking the data structure whose strengths match the operation you keep repeating. Candidates who know the cost of each operation can look at a brute force, spot the expensive step, and swap in the right structure almost mechanically. This is the highest-leverage knowledge in a coding round.
What this covers / why it matters: the core data structures, their operation costs, and how to match a structure to a problem's needs. It turns "how do I speed this up?" into a lookup.
The approach
Beginner — know the cost table cold
| Structure | Lookup | Insert | Delete | Ordered? |
|---|---|---|---|---|
| Array | O(1) by index, O(n) by value | O(n) | O(n) | yes |
| Hash map / set | O(1) avg | O(1) | O(1) | no |
| Balanced BST / TreeMap | O(log n) | O(log n) | O(log n) | yes |
| Heap (priority queue) | O(1) peek min/max | O(log n) | O(log n) | partial |
| Stack | O(1) top | O(1) | O(1) | LIFO |
| Queue / Deque | O(1) ends | O(1) | O(1) | FIFO |
Intermediate — match the operation to the structure
Read the problem for its dominant operation:
- "Have I seen this before?" / dedupe / fast lookup → hash set/map.
- "Smallest / largest so far", "top k" → heap.
- "Most recent", "matching brackets", "undo" → stack.
- "First in first out", BFS, level order → queue/deque.
- "Need things in sorted order and fast updates" → balanced BST / TreeMap.
Advanced — combine structures
Hard problems often need two structures working together. An LRU cache is a hash map (O(1) lookup) plus a doubly linked list (O(1) reordering). A median-of-a-stream uses two heaps. Recognising when to pair structures — one for fast lookup, one for ordering — is the mark of a strong candidate.
Worked example
"Return the k most frequent elements in an array."
Reasoning by operations: first I need counts — "how many times have I seen x?" → a hash map (O(n) to build). Then I need the top k by count — "largest so far" → a heap. Push each (count, value) into a min-heap of size k; if it exceeds k, pop the smallest. That's O(n log k).
"I chose a hash map because counting is a pure lookup-and-increment (O(1) each), and a size-k min-heap because I only ever need the k largest, so I don't pay to fully sort all n distinct values." Two structures, each matched to one operation.
What interviewers look for
- You know operation costs and quote them accurately.
- You match structure to the dominant operation, not by habit.
- You justify the choice in terms of the required complexity.
- You can combine structures for harder problems.
Do's and don'ts
- Do identify the repeated operation, then pick the structure for it.
- Do state the complexity your choice gives.
- Don't default to arrays/lists for everything.
- Don't reach for a heap when a full sort or a hash map is simpler and enough.
- Mnemonic: LOST — Lookup→hash, Ordering→tree/heap, Stack/queue for order-of-processing, Test the cost.
Choosing a data structure by familiarity rather than by the operation you're repeating — e.g. doing an O(n) linear search inside a loop when a hash set gives O(1). Always name the hot operation first, then pick the structure whose cost for that operation is lowest.
- ✓- Memorise the lookup/insert/delete costs of the core structures.
- ✓- Read the problem for its dominant repeated operation, then match a structure.
- ✓- Lookup→hash, top-k/min-max→heap, LIFO→stack, FIFO→queue, ordered+fast→BST.
- ✓- Hard problems combine structures (LRU = hash map + linked list).
- ✓Optimisation is often just picking the structure whose strength matches the operation you repeat. Know the cost table, identify the hot operation, and choose — or combine — structures to hit the required complexity.
Choosing the Right Data Structure — Worked Example
Worked Example
Problem/Question: "Design the data structure behind a browser autocomplete that suggests words as the user types a prefix." — Which structure, and why?
Solution/Model answer:
Reasoning through options:
- Array + linear scan: check every word for the prefix — O(N x L) per keystroke, too slow for a large dictionary.
- Hash set: great for exact-match lookup, but hashes don't support prefix queries — wrong tool.
- Sorted array + binary search: can find a prefix range in O(log N), workable, but insertion is costly.
- Trie (prefix tree): the natural fit — each path spells a prefix; retrieving all completions of a prefix is O(L + k) where L is prefix length and k the number of results. Insertions are O(L).
Choice: a Trie, optionally storing top-k suggestions per node for speed. "I'd pick a trie because the query is inherently prefix-based, which is exactly what a trie is optimised for."
Answer/Takeaway: Match the data structure to the operation the problem demands — prefix queries to a trie, fast membership to a hash set, ordered range queries to a balanced BST/sorted array, LIFO/FIFO to a stack/queue. Justify the choice by the required operations and their complexity.
- ✓- Let the required operation drive the structure: prefix→trie, membership→hash, ordered→BST, min/max→heap.
- ✓- Compare 2-3 candidate structures aloud with their complexities before committing.
- ✓- A hash set can't do prefix/range queries — know each structure's limits, not just its strengths.