Question 1

How do you choose a data structure for a problem? Walk me through your process.

Accepted Answer

Answer this by describing a process, not by listing structures — the process is what is being asked for. "I go in three steps. First — I list the operations in the problem: what gets inserted, removed, searched, iterated. Second — I identify which of them is inside the loop, i.e. repeats n times. That operation dictates the choice; the others can be O(n) without hurting. Third — I take the structure that makes that operation cheap and say out loud what I give up." Then show it with a concrete example — this pulls the answer out of the abstract: "For instance, in 'does this array contain a duplicate', the dominant operation is 'have I seen this value', repeated n times. A hash set makes it O(1), so the solution is O(n). In exchange I spend O(n) memory. The alternative is to sort and compare neighbours: O(n log n) time but O(1) memory. If memory were the constraint I'd take the second." The last sentence matters most: knowing both options and choosing by context. A candidate with one solution reads as having memorised; a candidate choosing between two reads as having understood.

Question 2

When would you choose a balanced tree (TreeMap) over a hash map?

Accepted Answer

Short answer: when you need order. That one word is the core; the rest unpacks it. Comparison: a hash map gives O(1) average lookup but keeps no order. A balanced tree gives O(log n) but keeps elements sorted. Four concrete cases where the tree wins — listing them makes the answer practical: Range queries: "all values between 100 and 500" — O(log n + result size) in a tree, a full O(n) scan in a hash map Nearest value: "the largest key below X" (floor/ceiling) — directly supported by a tree Min/max: O(log n) or O(1) in a tree, O(n) in a hash map Ordered iteration: iterating a tree yields sorted order; a hash map's iteration order is not something to rely on Add a practical example: "On a leaderboard where you need to look a user up by score and also answer 'who is above them', a hash map isn't enough — you need an ordered structure." Be careful: don't say "a tree is always better". If you only need key lookups, a hash map is faster and has a smaller constant factor. A tree's log n and pointer chasing are a real cost. Per language: TreeMap/sortedMapOf in Kotlin/Java, SplayTreeMap in Dart, and JavaScript has no standard balanced tree — you use a sorted array with binary search, or a library. Knowing that detail shows practical experience.

Question 3

Task: at any moment you must know the 10 most frequent elements in a stream. Which structures would you choose?

Accepted Answer

This is a combine two structures question; a single structure is not the expected answer. Clarifying questions first: how large is the stream — does it all fit in memory? What does "at any moment" mean — an exact answer after every element, or periodically? Must it be exact, or is approximate acceptable? The core solution — two structures: Hash map — element → count. The dominant operation is incrementing the counter, once per element: O(1) A min-heap of size 10 — holds the current best ten. If a new count exceeds the heap's root (the smallest), pop the root and push the new one: O(log 10) Result: O(n log k) for n elements, memory O(number of distinct elements). Why not a full sort: sorting all counts each time would be O(u log u), and sorting 999,990 elements to get 10 is pointless. A detail very few candidates raise: a count stored in the heap can go stale — when an element reappears, its heap value is already wrong. Two fixes: (1) rebuild the heap only at query time; (2) go lazy — on pop, compare against the hash map and discard stale entries. Raising this yourself is a strong signal. The scale answer (a senior signal): if the stream is huge and the distinct elements don't fit in memory, an exact answer becomes impossible — you use a probabilistic structure like Count-Min Sketch: fixed memory, small error. Demonstrating the "trade accuracy for memory" judgement is the real value here.

Question 4

A candidate uses a hash map for every problem. What is wrong with that approach?

Accepted Answer

A hash map really is the most broadly useful structure, so the habit is understandable — but it has three concrete problems. 1. It answers order-based questions badly. "The smallest key", "values between X and Y", "the nearest value", "iterate in order" — all O(n) in a hash map and O(log n) in an ordered structure. The candidate "solves" it with a hash map, but the complexity isn't optimal. 2. It wastes memory. Sometimes no structure is needed at all: two pointers solve pair-finding on a sorted array with O(1) memory; a single variable is enough for a plain counter. The "let me build a hash map" reflex hides those simpler solutions. 3. In some problems it is simply the wrong tool. Prefix search (trie), merging groups (union-find), maximum in a window (monotonic deque), repeatedly extracting a minimum (heap) — a hash map is not the first choice in any of them. How to phrase it — keep the critique constructive: "A hash map is a very powerful tool and the right choice for a large share of problems. The problem isn't using it, it's not justifying the choice. If the candidate says 'lookup is the dominant operation, so a hash map', that's sound reasoning. If they say 'I always use a hash map', they're answering before reading the problem." A practical self-check: ask yourself — "does this problem involve order, prefixes, ranges or a repeatedly extracted minimum?" If yes, a hash map is probably not the right choice.

Question 5

How do you read the choice between a stack and a queue from the problem statement?

Accepted Answer

The one-sentence rule: in which order must the elements be processed? Last in, first processed — a stack (LIFO). First in, first processed — a queue (FIFO). Signals for a stack — if the problem contains any of these: "The most recently opened must close first" — bracket matching, HTML/XML tag validation "Go back / undo" — the browser back button, an editor's undo stack "Rewrite the recursion iteratively" — you are modelling the call stack by hand "The next greater element to the right" style problems — the monotonic stack pattern Signals for a queue: "Process in arrival order" — a task queue, a print queue, a message broker "Layer by layer" — BFS, level-order traversal of a tree "Minimum number of steps" — BFS again "The last N elements" — a deque, when you need O(1) at both ends A practical detail that earns credit: in JavaScript array.shift() is O(n) because every element shifts. Unnoticeable on a small array, but on a large queue it creates O(n²) — then you use an array with head/tail indices, or a linked list. Kotlin's ArrayDeque and Dart's Queue already solve this. Knowing it signals that you've written real code. Closing: "The choice is dictated by the ordering requirement in the problem, not by my habits. If the question says 'the most recent', it's a stack; if it says 'the first', it's a queue."

Signal in the problem	Structure	Why
"Find by key", "does this value exist?", "how often does it occur?"	Hash map / hash set	`O(1)` average lookup and insert; no ordering kept
"Remove duplicates", "count the unique ones"	Set	`O(1)` membership, no need to store values
"The most recently added", "undo", "are the brackets balanced"	Stack (LIFO)	Only the last element matters — `O(1)` push/pop
"Process in arrival order", "traverse layer by layer"	Queue (FIFO)	The basis of BFS and every in-order processing problem
"Top K", "repeatedly take the minimum", "streaming median"	Heap (priority queue)	`O(log n)` insert, `O(1)` peek at the minimum; no full sort needed
"Values between X and Y", "nearest value", "iterate in order"	Sorted array / balanced tree (TreeMap, SplayTreeSet)	Order is preserved — range queries in `O(log n)`; a hash map cannot do this
"Starts with this prefix", "autocomplete"	Trie (prefix tree)	Lookup depends on the prefix length, not on the number of words
"Frequent insert/delete in the middle", "no indexing needed"	Linked list (or deque)	`O(1)` removal when you hold the node; but indexed access is `O(n)`
"Are these two in the same group", "merge the groups"	Union-Find (disjoint set)	Union and find are effectively `O(1)`

Choosing the right structure