Common interview follow-up chains — every question, written out
Answer, then "what if it is weighted?", then "what if it does not fit in memory?" — rehearsing the escalation.
A BFS run states that its queue never holds two nodes more than one level apart. What does that guarantee buy?
Trace prediction
First arrival is shortest arrival, so a distance written on discovery is never revised
The queue is a frontier ordered by distance, so nothing at distance d+1 is dequeued before everything at distance d has been. That is why the first path to reach a node is the shortest one, and why the distance can be written down on discovery and never touched again. The whole argument rests on every edge costing the same, which is the crack the next question opens.
See it run — The invariant panel states the layer property, before a single node beyond the start has been explored.
Now the edges carry positive weights. Why does BFS break, and what replaces it?
Comparison
Fewest edges is no longer cheapest, so the frontier must be ordered by distance — Dijkstra
BFS is correct because a plain queue happens to order the frontier by distance when every edge costs one. Give edges different weights and a longer path can be cheaper, so the queue has to become a priority queue keyed on tentative distance — which is Dijkstra. The invariant survives in a stronger form: the smallest tentative distance is always safe to settle, because every remaining edge only adds.
See it run — The replacement invariant, stated as A settles: distances leave the heap in non-decreasing order.
And if some of those weights are negative — say the graph models trades with rebates?
Edge case reasoning
Settle-and-forget stops being safe; use Bellman–Ford, which also detects negative cycles
Dijkstra settles a node the moment it leaves the heap and never looks at it again, which is only safe when no future path can be cheaper — and one negative edge destroys that. Bellman–Ford gives up the ordering and relaxes every edge V−1 times at O(V·E), and a V-th pass that still improves something proves a negative cycle exists. If the graph happens to be a DAG, topological order gives a linear-time alternative that handles negatives without complaint.
Return the k largest values from an array of n, with k far smaller than n. Where do you start?
Trade-off & selection
A min-heap capped at k, pushing and evicting — O(n log k) time and O(k) space
A min-heap capped at k holds the best k seen so far, so each new element is either rejected by one comparison against the root or pushed at log k. That is O(n log k), which for k far below n is close to a single linear pass. Quickselect reaches expected O(n) when the array may be reordered, and mentioning it in the same breath is what makes the answer look chosen rather than recalled.
Now the values arrive as an unbounded stream, and the top k must be available at any moment.
Trade-off & selection
The same size-k min-heap, which never grows — memory is O(k) however long the stream runs
This is the case a bounded heap was built for: its size is fixed by k rather than by how much data has gone past. Each arrival is one comparison against the root and, at worst, one sift of log k. The answer is available at every moment because the heap always holds exactly the best k seen so far, and stating that invariant is the strongest part of the answer.
And if that stream is split across a hundred machines?
Trade-off & selection
Each machine keeps its own top k, and one merge over the hundred lists gives the global answer
The global top k must lie inside the union of the per-machine top k lists, because a value missing from its own machine’s top k already has k values above it on that machine alone. So each shard ships k values, the coordinator merges 100k of them, and network cost is bounded by k rather than by the stream. Saying why the union is sufficient is the part being graded — the merge itself is routine.
Sort ten million integers that fit comfortably in memory. What do you reach for, and what does it cost?
Complexity derivation
The library sort — O(n log n) comparisons, with the constant decided by the implementation
At this size the interesting answer is "the library sort", and the interesting follow-up is why: it is a hybrid with a small-range cutoff and a worst-case fallback that hand-written code seldom matches. Counting or radix sort can beat it, but only once you can state the key range, which is the precondition to say out loud rather than assume. All of it rests on the data fitting in memory, which is the assumption the next question takes away.
Now there are ten billion integers and they do not fit in memory. What changes?
Trade-off & selection
External merge sort: sort memory-sized chunks, spill them as runs, then k-way merge the runs
Merge sort only ever reads its inputs front to back, which is the access pattern external storage is built for, and Prism draws exactly that: one merge consuming two ordered runs through a single buffer. The standard shape is sort the chunks that fit, spill each as a sorted run, then merge the runs with one buffered reader apiece. How many runs can be merged at once is set by how many read buffers memory holds, which is the number to quote when asked how many passes it takes.
See it run — One merge consuming two ordered runs through a single buffer — the external algorithm in miniature.
Same ten billion values, but now the only question is whether any of them repeats.
Edge case reasoning
Hash each value into one of many files, then check each file alone — equal values land together
Hash partitioning is the general move for problems too large for memory: send each value to a file chosen by its hash, and any two equal values are guaranteed into the same file. Each file then fits in memory and gets the ordinary hash-set treatment, so the whole thing costs two passes rather than a full external sort. If the values are integers from a range of a few billion, a bitset over the range is cheaper still — four billion bits is half a gigabyte.
The classic opener: find two numbers in an unsorted array that add to a target. Your first answer?
Comparison
One pass with a hash map, checking for target − x before inserting x — O(n) time and space
The hash map turns "is there a partner?" into a lookup, and doing the lookup before the insert is what stops a value pairing with itself. The cost is one pass and O(n) memory, which is the expected first answer rather than the final one. Stating both time and space unprompted is what invites the follow-up instead of waiting for it.
Now you are told the array is sorted and that you may not allocate. What is the answer?
Trade-off & selection
Two pointers from both ends: too large a sum moves the right in, too small moves the left out
At the ends of a sorted array the current pair always involves an extreme, so a sum that is too large condemns the right element against every remaining partner and it can be dropped outright. Each step eliminates one element permanently, making the walk O(n) with two integers of state. The sortedness is doing all the work, and saying so matters, because the same argument powers three-sum and the container-of-water problem.
Extend it once more: three numbers summing to the target. What does it cost, and can it be beaten?
Complexity derivation
Fix one element and two-pointer the rest — O(n²) after the sort, with no better bound known
Sorting first lets each fixed element reduce the problem to the two-pointer version, giving n outer iterations of an O(n) walk, with the sort disappearing into that quadratic total. Beating n² for three-sum is a long-standing open problem, so "I do not think you can do better here" is both correct and expected. The other half of a full answer is skipping duplicate values at each level, without which the same triple is reported repeatedly.
Detect whether an undirected graph contains a cycle. What is the cheapest reliable test?
Code diagnosis
Union the endpoints of each edge; an edge whose ends already share a root closes a cycle
Union-find processes edges one at a time and answers "are these already connected?" in near-constant time, so the first edge whose endpoints share a root is a cycle. It is also what Kruskal uses, which is why the rejection is visible in Prism’s minimum-spanning-tree run. DFS works too and is O(V + E), but only when the edge back to the parent is excluded — the classic off-by-one of undirected cycle detection.
See it run — An edge rejected outright — union-find found its two ends already in the same component.
Now the graph is directed. Why does the undirected test stop working?
Edge case reasoning
A node can be revisited without a cycle; what counts is whether it is on the current recursion stack
In a directed graph two paths can converge on the same node without any cycle existing, so "already visited" is not evidence of one. The working test is three-colour DFS: a node currently being explored is grey, and an edge into a grey node is a back edge and therefore a cycle. Kahn’s algorithm answers the same question from the other side — if a topological order cannot consume every node, whatever is left forms a cycle.
A sorted array has been rotated at an unknown point. Can binary search still find a value in it?
Invariant identification
Yes — at every probe at least one side is properly sorted, and that side can be tested and discarded
Compare `a[mid]` with `a[lo]`: if the midpoint is larger then the left half is unrotated, and otherwise the right half is. That gives one side whose range the target can be checked against, so a probe still discards half the array and the search stays O(log n). The invariant that survives rotation is weaker than full sortedness but strong enough to halve, which is the transferable lesson.
And if that rotated array may also contain duplicate values?
Edge case reasoning
The worst case degrades to O(n): when the low, mid and high values tie, neither side is decidable
The usual fix is to advance the low index and retreat the high index by one whenever all three values tie, which keeps the search correct while admitting a linear worst case on input like all-equal keys. The interesting part is that the bound is genuinely unrecoverable rather than merely unimplemented: the information needed to choose a side is absent. Saying "still correct, no longer logarithmic, and here is why" is a far stronger answer than patching it quietly.
What is an interviewer actually testing when they say "and what if it does not fit in memory?"
Trade-off & selection
Whether your first solution was chosen for reasons that still hold once a constraint moves
Every escalation removes an assumption the first answer quietly leaned on — that the data fits, that edges cost the same, that the input may be reordered. A candidate who named those assumptions while giving the first answer can adapt in a sentence; one who recalled a solution has to start over. That is why the protocol is to state constraints out loud early: the follow-up then reads as a continuation rather than an ambush.
You have given a solution and the interviewer says "now suppose the data is a hundred times bigger". Talk through how you would respond.
Explain it plainly
The first thing I would do is not answer yet. I would go back over what I just built and say out loud what it was assuming — this version holds the whole array in memory, it assumes I can reorder the input, and it assumes a lookup in the hash map is basically free. Then I would ask which of those the new size actually breaks. If a hundred times bigger still fits in memory, honestly nothing changes and I should say so rather than inventing complexity to look thorough. If it does not fit, then the assumption that broke is the one about holding everything at once, and that points at a specific family of fixes: process the data in chunks that do fit, and use an algorithm that only ever reads front to back, because random access across something that lives on disk is what kills you. So I would move from an in-memory sort to an external merge sort, or from a hash set to hashing values into files so that equal things land in the same file. I would also say what I am giving up — more passes over the data, and a lot more I/O — and I would ask what the actual budget is, because whether this needs to run in a second or overnight changes which of those I would pick.
The test is whether you treat the follow-up as a new problem or as an edit to the old one. A strong answer goes back to the assumptions the first solution made, names which one the new constraint breaks, and only then reaches for a different tool.