Question 1

A robot moves up, down, left or right across a grid of open and blocked cells, every move costing the same. Find the fewest moves from start to exit. Which technique?

Accepted Answer

Breadth-first search — it expands in rings of equal distance, so the exit is met at its true minimum. Equal move costs is the cue: BFS reaches nodes in order of distance from the start, so the first arrival at the exit is provably minimal. A grid is a graph in costume — cells are nodes, adjacency is edges — which is how BFS solves problems with no picture of a graph anywhere. Dijkstra would also be correct, but using it here invites the “why are you paying for the log factor?” follow-up.

Question 2

Same grid, but entering a cell now costs between 1 and 9 units and you want the cheapest route. What changes?

Accepted Answer

Switch to Dijkstra — cheapest is no longer the same as fewest, so the frontier must be ordered by cost. The unweighted-versus-weighted split is the first question to ask out loud, because it decides between a queue and a priority queue. Dijkstra keeps the frontier ordered by tentative cost so that the node it settles next is genuinely the cheapest reachable one. The price is a log factor per operation, which is exactly what BFS was saving you when all the weights were equal.

Question 3

Now some cells refund energy, so a move can carry a negative cost. Does Dijkstra still work?

Accepted Answer

No — it treats a popped node as final, which a later negative edge can invalidate; use Bellman-Ford. Dijkstra rests on one assumption: once a node is popped with the smallest tentative distance, nothing cheaper can reach it, because every remaining edge only adds cost. A negative edge breaks that assumption, so a settled value can turn out to be wrong. Bellman-Ford relaxes every edge V−1 times instead, at O(V·E), and reports a negative cycle when one exists — the case where shortest paths genuinely stop existing.

Question 4

Given a sorted array and a target, decide whether two entries sum to it, using O(1) extra space. Which technique?

Accepted Answer

Two pointers from both ends — raise the left one when the sum is too small, lower the right when too big. “Sorted array” in the givens is a purchase the setter made on your behalf, and the expected way to spend it is binary search or two pointers. Here each comparison eliminates an entire element: if the largest available partner is still too small, the small end can never participate. That is one pass, O(n) time, and no extra memory at all.

Question 5

Same question, but the array is unsorted and you must report the two original indices. Which technique?

Accepted Answer

One pass with a hash map from value to index, checking for the complement before inserting each entry. With no order to exploit, cheap lookup has to come from hashing rather than from position. Walking once and asking “have I already seen target − x?” answers in O(n) time, and storing the index alongside the value keeps the original positions intact. The trade is explicit: linear time bought with linear memory, which is the standard exchange when the input has no structure.

Question 6

Find the longest stretch of a string containing at most k distinct characters. Which technique?

Accepted Answer

A sliding window with a count map, growing on the right and shrinking on the left when the limit breaks. The words “longest”, “window” and “at most k” together name the family before any code is written. Both edges only ever move right, so the total pointer movement is bounded by 2n and the scan is linear despite the nested loops. The count map is what makes the constraint checkable in O(1) as the window changes shape.

Question 7

Courses have prerequisites, and you must produce an order in which every course follows all of its prerequisites. Which technique?

Accepted Answer

Topological sort — repeatedly place a course whose remaining prerequisites have all been placed. “Prerequisites”, “dependencies” and “must come before” all name the same family, and its twin question — “is it even possible?” — is cycle detection. Kahn’s algorithm keeps a count of unplaced prerequisites per course and a queue of the courses whose count has reached zero. Each placement decrements its dependents, which is what promotes the next batch into the ready queue.

Question 8

Pairs of duplicate accounts arrive one at a time, and after each pair you must report how many distinct people remain. Which technique?

Accepted Answer

Union-find — each pair is one union, and a running component count answers every query immediately. Connectivity that grows over time, with queries interleaved, is union-find’s home ground; a fixed graph queried once is where DFS or BFS wins instead. Union by size with path compression makes each union and find effectively constant, so the whole stream costs near-linear time. The component count needs no extra machinery — it starts at n and drops by one on each union that actually merges two different groups.

Question 9

Numbers arrive in a stream too large to store, and you must keep the 100 largest seen so far. Which structure?

Accepted Answer

A min-heap capped at 100 — push each arrival, then drop the smallest whenever the size exceeds 100. A min-heap of size k keeps its smallest element at the root, which is exactly the one to evict when a larger value arrives. Each arrival costs O(log k), and the memory stays O(k) no matter how long the stream runs. “Top k” and “k-th largest” should trigger the word heap within seconds; quickselect is the alternative when the whole array is already in memory.

Question 10

A problem gives n ≤ 18 items and asks for the best subset under an awkward constraint. What is the bound telling you?

Accepted Answer

That an exponential search over all 2ⁿ subsets is intended, most likely as bitmask dynamic programming. The constraint is the complexity budget, and the budget names the family. 2¹⁸ is about 260,000, so enumerating every subset is trivially affordable, while 18 is far too small to force a polynomial trick. Hunting for a clever polynomial answer here spends interview time the setter never asked for.

Question 11

A problem gives n up to 1,000,000 with a two-second limit. Which families are still on the table?

Accepted Answer

One-pass scans, two pointers, hashing, counting and n log n sorting — nothing quadratic. At a million, an n log n solution is about 20 million operations and a quadratic one is a trillion — one finishes instantly and the other never finishes at all. So the constraint has already eliminated the nested-loop family before you have read the story. Checking the bound first, and naming the families it permits, is the highest-value thirty seconds in the whole problem.

Question 12

How many distinct ways can you climb n stairs taking 1, 2 or 3 steps at a time? Which technique?

Accepted Answer

Dynamic programming — the count for a stair is the sum of the counts for the three stairs below it. “Count the ways” is dynamic programming’s calling card, and the state here is one number: which stair you are standing on. Ways(i) = Ways(i−1) + Ways(i−2) + Ways(i−3) with base cases at the bottom gives O(n) time, and keeping only three values makes it O(1) space. The naive recursion computes the same states exponentially often, which is precisely the overlap that makes caching pay.

Question 13

Find the smallest ship capacity that lets a fixed list of packages ship within D days. Which technique, and what must hold for it to be valid?

Accepted Answer

Binary search over the capacity, valid because feasibility is monotone — any larger capacity also works. Binary search does not need a sorted array; it needs a monotone predicate, a boundary where “no” turns into “yes” and never turns back. Feasible(c) is monotone here because extra capacity never forces extra days, so the boundary is found in about log(total weight) checks, each one a linear greedy simulation. Saying that monotonicity out loud is the part that shows you did not simply pattern-match on the word “smallest”.

Question 14

Given a list of meeting intervals, merge every group of intervals that overlaps. Which technique?

Accepted Answer

Sort by start time, then sweep once, extending the current interval whenever the next begins inside it. Sorting by start time buys the invariant that makes one pass sufficient: once you are past an interval’s start, nothing later can begin earlier. Overlap then reduces to comparing the current merged interval’s end against the next interval’s start. Total cost is O(n log n), dominated by the sort — the standard payoff of sorting first, a global relation collapsed into a local one.

Question 15

You need the k-th largest value of an in-memory array exactly once. What is the ranking of the reasonable answers?

Accepted Answer

Quickselect at O(n) expected, then a heap of size k at O(n log k), then a full sort at O(n log n). Three answers are all correct here, and naming the ranking beats jumping straight to any one of them. Quickselect partitions like quicksort but recurses only into the side holding the k-th position, which is O(n) expected and O(n²) against bad pivots unless they are randomised. The heap wins when the data does not fit in memory, and the full sort wins when the order will be needed afterwards anyway.

Question 16

A candidate solves “fewest moves through a maze” with depth-first search and returns a path 40% longer than optimal. What is the diagnosis?

Accepted Answer

DFS returns the first path it finds, and first is not shortest — the family was chosen wrongly. This is a family error rather than an implementation error, so no amount of debugging fixes it. DFS commits to one branch and unwinds only when it is stuck, so the first route reaching the exit bears no relation to the minimum. BFS expands strictly by distance, which is why its first arrival is provably shortest — swapping the stack for a queue is the entire repair.

Question 17

The prerequisite graph turns out to contain a cycle. What does the topological sort do about it?

Accepted Answer

It stops with fewer courses placed than exist, and that shortfall is the proof of a cycle. A course inside a cycle keeps a non-zero prerequisite count forever, so it never becomes ready and never enters the queue. The run therefore ends with the queue empty and fewer than n courses placed, and comparing that count against n is the cycle check. “Is it even possible?” and “in what order?” are answered by one run, which is why those two questions almost always arrive together.

Question 18

A friend asks how you work out which algorithm a problem wants. Talk them through your first sixty seconds.

Accepted Answer

I read the constraints before the story, because the constraint is the complexity budget and the budget names the families. If n is about twenty I am allowed to be exponential, so I start thinking about subsets and backtracking. If n is a million, quadratic is already dead and I am looking for a single pass, two pointers, hashing or a sort. Then I read the givens and ask what has been paid for: if the input is sorted, the setter bought that for me and expects binary search or two pointers, and an O(n) scan of sorted data usually means I have missed the intended answer. Then the verbs — shortest or fewest moves means BFS, and Dijkstra the moment the moves have different costs; prerequisites means topological sort; count the ways or longest subsequence means dynamic programming; top k means a heap. If the words are neutral I look at the shape instead: a grid is a graph in costume, and any description of states you can be in and moves you can make is a graph whose nodes are states. Finally I do the smallest example by hand and watch which technique my hand wants to use, then say the hypothesis out loud with its complexity and sanity-check it against the budget before I write anything.. A strong answer is a procedure rather than a list of algorithms, and it ends with a hypothesis carrying a complexity that is checked against the constraint before any code is written. The tell is that constraints are read first, not last.

Which algorithm does this problem want? — every question, written out