Choosing the Right Data Structure

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.

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).

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.

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.