Which Data Structure? A Decision Guide for Coding Interviews
Pick the right data structure fast in a coding interview: four questions that narrow the field, a constraint-to-structure map, and how to justify it out loud.
- hash map vs array interview
- when to use a heap
- DSA patterns interview
- data structure trade-offs
Short answer: ask four questions in order. What am I looking up, and by what key? Do I need order? Do I need every element or only the min/max? What changes, and how often? The answers usually force the choice: hash map or set for lookup by value, array for position, heap for extremes, something sorted for ranges. Then say the cost of your choice out loud.
Most people who lose a round on data structures knew every structure on the syllabus. What they could not do was pick one in ninety seconds and defend it. Interviewers are not testing whether you can recite how a red-black tree rebalances. They are watching whether your choice follows from the constraints you were given.
Four questions that narrow it fast
Ask these out loud, in this order, before you name a structure:
- What am I looking up, and by what key? Lookup by value means a hash map or set. Lookup by position means an array. Lookup by rank or range means something sorted.
- Do I need order? Insertion order, sorted order, or none. This one question rules out half the options.
- Do I need every element, or only an extreme? If you only ever touch the min or max, you want a heap, not a sort.
- What changes, and how often? Frequent inserts in the middle punish arrays. Frequent random access punishes linked lists.
Saying those answers aloud is exactly the reasoning interviewers score. It sounds like competence instead of guesswork.
The constraint-to-structure map
| What the problem says | Reach for | Cost you accept | Practice |
|---|---|---|---|
| "Have I seen this before?" | Hash set | O(n) memory, no order | Two Sum |
| "Count occurrences" / "group by" | Hash map | Same, plus hashing keys | Group Anagrams |
| "Kth largest" / "top k" | Heap of size k | O(n log k), no random access | Kth Largest Element |
| "Next greater / previous smaller" | Monotonic stack | Harder to explain clearly | Daily Temperatures |
| "Max of every window of size k" | Deque | Index bookkeeping | Sliding Window Maximum |
| "Sorted, and I need a boundary" | Binary search | Sorting cost if not already sorted | Binary Search |
| "Prefix" / "autocomplete" | Trie | Memory, and setup time in a short round | Implement Trie |
| "Which things are connected?" | Union-find or BFS/DFS | Extra structure to justify | Number of Islands |
Look at the third column. Every choice is a trade, and naming the cost yourself is what separates a senior-sounding answer from a lucky one.
Three misfires that show up constantly
- Sorting when a heap would do. "Top 5 of 10 million" does not need a full sort. Sorting is O(n log n) and needs all the data up front; a size-5 heap is O(n log 5) and works on a stream.
- A map where a set belongs. If you never read the value, you are telling the interviewer you did not think about what you needed.
- A hash map when you needed order. You end up sorting the keys at the end and quietly paying O(n log n) after claiming O(n).
Say the choice, then the cost
A two-sentence pattern that works on almost any problem:
"I need membership checks by value and I don't care about order, so a hash set gives me O(1) average lookup. That costs O(n) extra memory; if you want constant space I'd sort first and use two pointers instead."
The second sentence, the alternative you did not pick, is the part most candidates skip. It shows you chose instead of defaulting. If saying this under time pressure feels unnatural, that is a rehearsal problem, not a knowledge problem.
A ten-minute daily drill
Take five problem statements you have not solved. Do not solve them. For each, write only the structure, the reason, the cost, and one alternative. You will get faster at the first three minutes of the interview, which set up everything after. Pair the drill with the problem-reading framework so you pull out the constraints before you commit.
FAQ
Should I mention advanced structures like segment trees?
Only if the constraints demand one and you can implement it. Naming a structure you cannot code does more harm than good.
Is a Python dict enough for every map question?
In interviews, usually. Know that it preserves insertion order (guaranteed since Python 3.7) but does not give you sorted iteration. Say which property you are relying on.
How do I justify memory use?
Quote the cost against the input size. "n is at most 10^5, so an O(n) set is a few megabytes at most" usually ends the discussion. The time complexity guide covers the arithmetic.
Summary: good choices of data structures for coding interviews come from four questions (key, order, extremes, mutation), not from memorizing a catalogue. Name the structure, name its cost, and name the alternative you passed on.