Algorithms Interview Questions

A curated set of algorithms interview questions, ordered roughly from fundamentals to more advanced — the kind you'll actually be asked in real screens and on-sites.

Recursion and Big-O basics#

Q: When would you choose recursion over an iterative loop, and what's the trade-off? Recursion shines when a problem's structure is naturally self-similar — trees, divide and conquer algorithms, or anything already defined recursively (like factorial) — since the recursive solution often reads far more clearly than an equivalent loop. The trade-offs are real, though: every recursive call adds a frame to the call stack, so Python's default recursion limit (around 1,000 calls) can be hit by recursion whose depth scales with a large input, and each call carries function-call overhead a plain loop doesn't pay. A reasonable rule of thumb is to reach for recursion when recursion depth stays small (like O(log n)) and prefer iteration when depth would scale linearly with a potentially huge input.

Q: How do you determine the Big-O of a recursive function without memorizing formal derivation rules? Ask two questions: how many recursive calls does each invocation make, and how much does the input shrink on each call? A single call per invocation that shrinks the input by a constant amount (like factorial) gives O(n); shrinking by half instead (like binary search) gives O(log n). Multiple calls per invocation combined with shrinking by only a constant amount causes the total call count to multiply out across depth — naive Fibonacci's two calls per invocation across n levels of depth is exactly why it costs O(2ⁿ). The key discriminator is whether the input shrinks fast enough (by a fraction) to keep the recursion tree shallow despite branching.

Sorting and searching#

Q: How would you choose between merge sort and quicksort for a real project — and what would you actually use in practice? Quicksort is typically faster in practice thanks to better cache locality and in-place partitioning (O(log n) space), but its worst case is O(n²) on unlucky pivot choices, mitigated in practice with random or median-of-three pivot selection. Merge sort guarantees O(n log n) in every case and is stable, at the cost of O(n) extra space for merging. In real production code, though, the right answer is almost always neither — reach for the language's built-in sort (Python's sorted(), powered by Timsort), which is stable, guarantees O(n log n) worst case, and is far more optimized than a hand-rolled version would be.

Q: Walk through solving "search in a rotated sorted array" in O(log n). A rotated sorted array isn't globally sorted, but at least one of the two halves around any midpoint always is. Run a modified binary search: at each step, check which half (left or right of the midpoint) is properly sorted, then check whether the target's value could fall within that sorted half's range — if so, search there; if not, the target must be in the other half, if it's present at all. This still halves the search space at every step, preserving O(log n) despite the array not being fully sorted.

Patterns: two pointers, sliding window, and divide and conquer#

Q: How do two pointers and sliding window turn an O(n²) brute-force approach into O(n)? Brute force for problems like "find a pair summing to a target" or "find the best window of data" typically checks every pair or every window independently from scratch, which is quadratic. Two pointers narrow the search space monotonically without ever revisiting earlier ground (as in two sum on a sorted array), and sliding window reuses the previous window's already-computed state, incrementally adjusting only for what changed at the window's edges rather than recomputing everything. Both techniques are, at their core, disciplined ways of never asking the same question about the same data twice.

Q: What's the fundamental difference between divide and conquer and dynamic programming? Both break a problem into smaller subproblems, but divide and conquer assumes those subproblems are independent — solving one half of the data never depends on solving the other half, so there's nothing to gain by remembering earlier work (merge sort and binary search are the classic examples). Dynamic programming is needed specifically when subproblems overlap — the same smaller subproblem gets asked for repeatedly — in which case caching each subproblem's answer the first time it's computed (memoization or tabulation) avoids exponential, redundant recomputation.

Dynamic programming and greedy#

Q: How do you recognize that a problem calls for dynamic programming, and how do top-down and bottom-up approaches differ? Look for two signals: overlapping subproblems (a naive recursive solution keeps re-solving the same smaller inputs) and optimal substructure (the best overall answer can be assembled directly from the best answers to subproblems). Top-down memoization mirrors the problem's natural recursive definition and caches results the first time each unique subproblem is computed, only ever computing subproblems actually needed for the given input — but it risks Python's recursion depth limit on large inputs. Bottom-up tabulation builds the answer iteratively from the base cases upward with no recursion at all, avoiding stack-depth concerns and usually running a bit faster due to no per-call overhead, though it may compute some subproblems that top-down would have skipped.

Q: When does a greedy algorithm fail to produce the optimal answer, and how would you demonstrate that to an interviewer? Greedy fails whenever the locally best-looking choice at one step can foreclose a better combination of choices later, and the problem lacks a provable "greedy choice property." The classic demonstration is coin change with denominations [1, 3, 4] and target 6: greedy always grabs the largest coin that fits, taking 4 then two 1s for three coins total, while the true optimum is two 3-coins for just two coins. Showing a concrete counterexample like this is far more convincing — and faster to construct — than trying to argue abstractly about whether a greedy rule is correct.

Graphs#

Q: When would you use BFS, Dijkstra's algorithm, or Bellman-Ford for a shortest-path problem? Use BFS when the graph is unweighted (every edge counts equally) and you need the fewest hops — it explores level by level, so the first time it reaches a target, that's necessarily via the fewest edges. Use Dijkstra's algorithm when edges have weights, as long as none of those weights are negative — it's the standard, efficient choice (O((V+E) log V) with a heap) for the vast majority of real-world weighted graphs like road networks or flight costs. Use Bellman-Ford specifically when negative edge weights are possible (it also detects negative-weight cycles, which make "shortest path" ill-defined) — it's correct in that case, but meaningfully slower, at O(V × E).

Q: What problem does Union-Find solve, and why is it faster than re-running BFS or DFS every time? Union-Find answers "are these two nodes connected?" and "merge these two groups" efficiently as a graph's edges are added incrementally over time, without re-traversing the whole structure from scratch on every query. With path compression (flattening lookup chains during find) and union by rank (always attaching the shorter tree under the taller one), both operations run in amortized nearly-O(1) time — formally O(α(n)), the inverse Ackermann function, which is effectively a small constant for any realistic input. Re-running a full BFS/DFS for every connectivity check instead would cost O(V + E) each time, which adds up quickly if connectivity needs to be checked repeatedly as the graph grows.