Question 1

How should you prepare for a rapid-fire round?

Accepted Answer

The core principle: preparation happens by speaking out loud, not by reading. Everything looks clear when you read silently; forming the sentence in 30 seconds is a different skill entirely, and it is the one being tested. A concrete protocol: Build a list of 20 fundamental questions (array vs linked list, hash map, collisions, stack/queue, heap, Big O, BFS/DFS, sorting, stability, binary search, and so on) Cover the answers and answer each out loud against a 30-second timer Score each 0-3: 3 = direct answer + why + example, within time; 1 = correct but vague ("it's faster"); 0 = wrong or invented Everything scoring 0-1 goes on tomorrow's repeat list Record yourself once — uncomfortable, and the highest-value step: that's where you see the over-long answers and the filler words What you don't need to memorise: exact numbers, full algorithm code, the invariants of exotic structures. They aren't asked in this round. What you must know: the mechanism and complexity of everyday structures, what Big O means, and how to compare two algorithms. The one sentence that matters most — close with it: "The point of preparing isn't to memorise answers but to know the reason behind each one — because in rapid-fire the question arrives slightly reworded, and memorisation collapses while the reason doesn't."

Question 2

Mid rapid-fire you realise you gave a wrong answer. What do you do?

Accepted Answer

Short answer: correct it yourself, immediately. That isn't a negative — it's one of the strongest signals there is. How: "Sorry, let me go back to my earlier answer — I said quicksort's worst case was O(n log n), it's actually O(n²). It happens when the pivot always lands at the extreme, for example choosing the first element on an already sorted array." One sentence of correction, one of reason — that's enough. Why it's a strong signal: what the interviewer sees is that you track your own answers, recognise the error and don't hide it. That is the behaviour that matters in real work too: the engineer who checks their code before sending it, not after review. What not to do: Stay quiet and hope they didn't notice — they usually did and wrote it down; later answers get doubted too Hide the error as a "clarification" — "well, what I actually meant was..." reads worse than a correction Over-apologise — one "sorry, let me correct that" suffices Timing: say it right after the current question finishes; don't wait for the end of the round. The sooner, the more natural it reads. One more nuance: sometimes you aren't sure it was wrong. Then be honest: "I'm not fully confident about my earlier answer — I'd want to check, but thinking about it now I believe..." That is honest and shows you know the boundaries of your own knowledge — one of the markers of seniority.

Question 3

The interviewer asks "would you choose an array or a linked list?". How do you answer?

Accepted Answer

This is a trap in question form: they aren't waiting for a name, they're waiting for a conditional choice. The right opening: "It depends — which operation dominates?" Then unpack both cases briefly. I pick an array: when I need indexed access (O(1)), or when I'll iterate the elements sequentially — cache friendliness makes a large practical difference. In real code this is the default. I pick a linked list: when there is frequent insertion/removal in the middle and I already hold the node — that condition matters: if I have to search for the node, the O(n) search makes the O(1) removal pointless. Also when the size varies wildly and I want to avoid large array copies. The strongest sentence — always add it, because most candidates recite the textbook answer and stop: "In practice linked lists are used far less than you'd expect. The O(1) removal looks attractive in theory, but in real measurements small and medium arrays beat linked lists on cache locality. So I start with an array and only switch after measuring." Add a concrete example: "An LRU cache is where a linked list genuinely earns its place — the hash map hands you a direct pointer to the node, so removal really is O(1). That's the classic case where the condition holds." This answer shows three things: you know the theory, you know the practice, and you don't apply the theory blindly.

Question 4

How should you prepare for "what's the complexity of this?" questions — must you memorise everything?

Accepted Answer

Short answer: no — being able to derive it beats memorising it, because memorisation collapses on an unfamiliar structure and derivation doesn't. What to do instead: remember a one-sentence "mechanism" per structure, and the complexity falls out of it: Hash map: the key becomes an index directly → no search → O(1) Balanced tree: half is discarded each step → height log n → O(log n) Heap: an element sifts up or down by the tree height → O(log n); the root is always in hand → peek O(1) Array: elements are contiguous → the address is computed → indexing O(1); removing from the middle shifts everything → O(n) Linked list: nodes point at each other → k steps to reach the k-th → O(n); holding the node, you just rewire pointers → O(1) Binary search: half is discarded each step → O(log n) Six mechanisms answer dozens of complexity questions. Three points that need special care — knowing them shows precision: Average versus worst case: a hash map is O(1) average and O(n) worst; quicksort is O(n log n) average and O(n²) worst. Adding the words "on average" sharpens the answer Amortised: appending to a dynamic array is normally O(1) but O(n) at a resize — since the size doubles, it averages to O(1) Memory is complexity too: stating the time and forgetting the space is half an answer. Don't forget to count recursion's stack memory Interview behaviour: whenever you give the figure, add the reason in one line — "O(log n), because each step halves the search space." That is the sentence that separates recall from understanding, and it is exactly what interviewers listen for.

Question 5

The interviewer asks about a structure you don't know (a B-tree or a bloom filter, say). What do you do?

Accepted Answer

This can happen in any interview, and how you shape the answer matters more than the knowledge. Step 1 — be honest, but don't stop: "I don't know that one in depth." One sentence, no excuses. But don't end there. Step 2 — give precisely the part you do know: often the name and context tell you something. "What I know about B-trees: they're used for database indexes, they're multi-way trees, and the point is reducing disk reads. I couldn't explain the invariants or the balancing rules." That isn't invention — it is knowledge with a clearly drawn boundary. Step 3 — offer a reasoned guess, labelled as one: "From the name and where it's used, I'd guess each node holds many keys so that one node fits a disk block and the tree stays shallow — but that's a guess." Interviewers value that kind of reasoning highly, because it is exactly how you think when you meet an unfamiliar system at work. Step 4 — connect it: tie it to something you do know. "Conceptually I read it as a balanced tree optimised for disk — I've only worked with in-memory structures so far." What not to do: assemble an answer out of the parts of the name. "A bloom filter, so it filters something..." — that is spotted instantly. The important perspective: not knowing one thing doesn't end an interview. Inventing can, because afterwards the reliability of all your answers is in question. Being able to say "I don't know" is a mark of professionalism — at work too, an engineer who admits the gap is worth far more than one who fills it in.

Question — data structures	Model answer (20-30 seconds)
Difference between an array and a linked list?	An array keeps elements in contiguous memory — indexed access is `O(1)` but inserting/removing in the middle is `O(n)` because elements shift. In a linked list each node points to the next — removal is `O(1)` when you hold the node, but indexed access is `O(n)`. In practice arrays are often faster because they are cache-friendly.
How does a hash map work?	The key goes through a hash function, the result maps to a bucket index in an array, and the value is stored there. That is what makes lookup `O(1)` on average. It's ideal for finding a user by ID — but since it keeps no order, "the smallest ID" has no answer better than `O(n)`.
What is a hash collision and how is it resolved?	Two different keys landing in the same bucket — unavoidable, since the number of buckets is finite. Two main fixes: chaining (a list or tree inside the bucket) and open addressing (probe for the next free slot). With many collisions `O(1)` degrades toward `O(n)`, which is why modern implementations track the load factor and resize.
Difference between a stack and a queue?	A stack is LIFO — last in, first out; undo, bracket matching, an iterative rewrite of recursion. A queue is FIFO — first in, first out; task queues, BFS. Both are `O(1)` to add and remove; the only difference is which end you remove from.
What is a heap and what is it for?	A tree-shaped structure whose root is always the minimum (or maximum); insert and extract are `O(log n)`, peeking is `O(1)`. It is used as a priority queue: top-K, Dijkstra, task schedulers. An important nuance: a heap is not a sorted list — iterating it does not give sorted order.
When do you choose a set over an array?	When the question "does this value exist?" repeats. In an array that check is `O(n)`, in a set `O(1)`. The classic case is finding a duplicate: check each element against the set, `O(n)` overall instead of a nested-loop `O(n²)`. The trade-off: `O(n)` extra memory and the loss of ordering.
What is a binary search tree and why must it be balanced?	A tree where each node has smaller values on the left and larger on the right; a search discards half at each step — `O(log n)`. But inserting sorted data turns the tree into a chain and it becomes `O(n)`. That's why self-balancing variants (AVL, red-black) are used in practice — `TreeMap` and `SplayTreeMap` are exactly those.
When do you pick a tree map over a hash map?	When you need order. A hash map gives `O(1)` but is useless for range queries, min/max, "nearest value" and ordered iteration. A tree map is `O(log n)` but supports all of them. Example: "who is above this user" on a leaderboard demands a tree map.
Why is appending to a dynamic array called "amortised O(1)"?	Normally the append is `O(1)`, but when the array fills, a new array twice the size is allocated and everything is copied — that single operation is `O(n)`. Since the size doubles each time, those copies get rarer and rarer, so `n` appends cost `O(n)` in total, i.e. `O(1)` per operation on average.
What is a trie?	A prefix tree: each node is a character and the path from the root spells a prefix. Lookup depends on the prefix length, not on how many words are stored. Ideal for autocomplete and dictionary checks; in exchange it is memory hungry, so on a small dictionary a plain filter is more practical.
Difference between stack memory and heap memory?	The stack holds call frames and local variables; allocation is very fast and it is cleaned up automatically when the function returns, but its size is limited — deep recursion causes a stack overflow. The heap is for dynamic objects: allocation is more expensive, lifetimes are longer, and cleanup is either GC or manual. Don't confuse it with the "heap" data structure — same name, different thing.

Question — algorithms and complexity	Model answer (20-30 seconds)
What is Big O and why the worst case?	Big O describes how the work grows as the input grows — it drops constants and lower-order terms because they stop mattering at scale. The worst case is used because you need a guarantee: "fast on average" doesn't explain a service falling over on a ten-million-item input. Example: quicksort is `O(n log n)` on average but `O(n²)` at worst — which is exactly what makes it risky in a real-time system.
When is `O(n log n)` unavoidable?	When you sort by comparing elements only to each other. `n` elements have `n!` orderings and a binary decision tree must be at least `log₂(n!) ≈ n log n` tall. That is an information-theoretic bound. To get past it you must stop comparing: counting sort is `O(n + k)`, but it requires the values to lie in a narrow range.
BFS or DFS — which, and why?	They are the same algorithm; BFS uses a queue and DFS a stack. If the question is "minimum number of steps" or "nearest", BFS — it goes layer by layer, so the first arrival is the shortest. "Does it exist", "how many components", "is there a cycle", "produce an ordering" — DFS. Both are `O(V + E)`.
Why is quicksort usually faster than merge sort in practice?	Both are `O(n log n)`, but quicksort works in place with sequential memory access, using the CPU cache well. Merge sort writes into an auxiliary array at every level. Same Big O, different constant factor. Merge sort wins when stability is required, on linked lists, and in external sorting.
What is stability in sorting?	Elements with equal keys keep their original relative order. The practical consequence: sort by name then by department and names stay alphabetical within each department. Stable: merge sort, insertion sort, TimSort. Not stable: quicksort, heap sort. Dart's `List.sort` gives no stability guarantee — a real source of bugs.
Why does binary search require sorted input?	Because the decision to discard half rests on order: if `a[mid]` is below the target, you know everything to its left is too. Without order that inference is invalid. More generally, the real precondition is monotonicity — which is why binary search also works with no array at all, directly over the range of answers.
When do you choose recursion over iteration?	When the problem itself is recursive — tree traversal, backtracking, divide and conquer — recursion makes the code far more readable. I choose iteration when the depth can grow, because each recursive call consumes a stack frame and 10⁵ deep means a stack overflow. Some languages have tail-call optimisation, but in JavaScript you can't rely on it in practice.
How do you turn a nested loop (`O(n²)`) into `O(n)`?	I look at what the inner loop does: usually a search for "does this value exist" or "find the matching pair". Making that search `O(1)` with a hash map turns the whole thing into `O(n)`. Two sum is the classic case. On sorted data, two pointers replace the nested loop — `O(n)`, and with `O(1)` memory.
What is memoization in one sentence?	Caching the result of a function so the same arguments are never recomputed. The classic case: naive recursive Fibonacci is `O(2ⁿ)` because it recomputes the same subproblems repeatedly; memoization brings it to `O(n)`. It is the top-down form of dynamic programming.
What counts as `O(1)` memory?	Extra memory that does NOT depend on the input size — a few variables, pointers, counters. The input itself doesn't count. That's why two pointers is `O(1)` and a hash map is `O(n)`. Note that recursion consumes memory too — a recursion `O(log n)` deep is `O(log n)` memory, not `O(1)`, and mentioning that shows precision.
Why does Dijkstra fail with negative weights?	The moment Dijkstra pops a node it declares its distance final. That is only safe if edges can only lengthen a path. A negative edge lets a longer path found later lower the distance, but the node is already closed. The result is silently wrong — nothing throws. For that case you use Bellman-Ford at `O(V × E)`.

Rapid-fire theory questions