How do you choose the right data structure for a problem?

Question

IT Interview Practice · Accepted Answer

Pick the structure whose **most frequent operations are cheapest** for your access pattern. Start by listing the operations you'll perform, estimate their frequency, then match them to a structure's strengths.

## A decision checklist

```text
1. How do you access data?  by index -> array
                            by key   -> hash map
                            by order -> tree / heap
2. Need ordering?           sorted   -> balanced BST / sorted array
                            FIFO     -> queue
                            LIFO     -> stack
3. Frequent middle inserts? -> linked list
4. Need fast "seen it?"     -> set / hash map
5. Need "best/min/max next" -> heap (priority queue)
```

## Match operations to complexity

| Need | Best structure | Key op cost |
|---|---|---|
| Random access by index | dynamic array | O(1) |
| Lookup by key | hash map | O(1) avg |
| Sorted + range queries | balanced BST | O(log n) |
| Min/max repeatedly | heap | O(log n) pop |
| FIFO / LIFO | queue / stack | O(1) |
| Prefix search | trie | O(L) |

## Example reasoning

```text
"Find the 10 most frequent words in a huge file."
 - count frequencies  -> hash map (O(1) updates)
 - keep top 10        -> min-heap of size 10 (O(log 10) per word)
```

## Why it matters

Choosing well is often the difference between an O(n) and an O(n²) solution — the single biggest lever on performance.

Interviewers test exactly this reasoning: they want to see you map requirements to operation costs, not memorize structures.

Need	Best structure	Key op cost
Random access by index	dynamic array	O(1)
Lookup by key	hash map	O(1) avg
Sorted + range queries	balanced BST	O(log n)
Min/max repeatedly	heap	O(log n) pop
FIFO / LIFO	queue / stack	O(1)
Prefix search	trie	O(L)

A decision checklist

Match operations to complexity

Example reasoning

Why it matters

Related questions