1.6 ★ core [I] 15 interview Q's

Algorithm categories — recognize the pattern

Interviews test pattern recognition: sorting tradeoffs, binary search, two pointers/sliding window, recursion, divide-and-conquer/greedy/DP. Aim for recognition speed.

Interviews and real debugging rarely test whether you can invent an algorithm — they test whether you recognize the pattern fast. Most problems are a known pattern in disguise, and the senior skill is reading the cue (“sorted + find”, “contiguous subarray”, “overlapping subproblems”) and reaching for the matching tool before writing a line. This chapter is a catalog of the handful of patterns that cover most problems, and the cues that trigger each one.

Sorting and binary search

Sorting is the foundation many patterns sit on, and its tradeoffs are worth knowing cold. Quicksort averages O(n log n), sorts in place (O(log n) stack), but degrades to O(n^2) on bad pivots. Mergesort is a steady O(n log n) and stable, but needs O(n) scratch space. Heapsort is O(n log n) in place but not stable. This is why standard libraries ship hybrids — Timsort (Python, Java objects) blends merge and insertion sort to exploit partially-ordered real data; introsort (C++ std::sort) starts as quicksort and falls back to heapsort if recursion runs deep, dodging the O(n²) worst case. And a hard floor: any comparison sort is bounded at O(n log n); you only beat it by not comparing (counting/radix sort on bounded integers).

Sort	Time (avg / worst)	Space	Stable?	Use when
Quicksort	`O(n log n)` / `O(n²)`	`O(log n)`	no	general in-memory, good cache behavior
Mergesort	`O(n log n)` / `O(n log n)`	`O(n)`	yes	stability needed; linked lists; external sort
Heapsort	`O(n log n)` / `O(n log n)`	`O(1)`	no	hard worst-case bound + no extra space
Timsort (hybrid)	`O(n log n)` / `O(n log n)`	`O(n)`	yes	real-world partially-sorted data (libs default)
Counting / radix	`O(n + k)`	`O(n + k)`	yes	bounded integer/keys — beats the comparison floor

Comparison sorts floor at O(n log n); only non-comparison sorts (counting/radix) break it.

Once data is sorted, binary search finds anything in O(log n) by halving the range each step. The cue to recognize: “sorted” + “find” — including subtler forms like “find the first value ≥ X”, searching a rotated array, or binary-searching over the answer space (“smallest capacity that ships in D days”).

Two pointers, sliding window, and hashing-as-technique

Two pointers walks two indices through an array — often from both ends inward — to collapse an O(n^2) nested scan into one O(n) pass. The classic cue is a sorted array plus a pair/triplet condition (pair-sum, container-with-most-water, 3-sum).

Sliding window is two pointers specialized to a contiguous subarray or substring under a constraint (“longest substring with no repeats,” “smallest subarray summing to ≥ K”). You grow the right edge to include, shrink the left to restore the constraint — every element enters and leaves the window once, so it’s O(n).

FIG 1 · sliding window Grow the right edge to add elements; when the constraint breaks, shrink the left. Each index is touched at most twice → O(n).

Hashing as a technique is the swiss-army move: a hash map turns “have I seen this?” or “what’s the count/complement?” from O(n) re-scans into O(1) lookups — frequency maps, dedup, and caching/memoizing results. When a brute force is O(n²) because of a repeated inner search, a hash map is usually the first thing to try.

Two-sum: brute force → hashing

“Find two numbers that sum to a target.” The brute force checks every pair — O(n^2). The pattern cue (lookup a complement) says reach for a hash map:

function twoSum(nums, target) {
  const seen = new Map();              // value → index
  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i];     // the complement we want
    if (seen.has(need)) return [seen.get(need), i];  // O(1) lookup
    seen.set(nums[i], i);
  }
  return null;                         // O(n) total, one pass
}

If the array were sorted, the same problem flips to a two-pointer solution (O(n) time, O(1) space): start a pointer at each end, move the left up when the sum is too small and the right down when too big. The input’s shape selects the pattern.

Recursion and the algorithmic strategies

Recursion solves a problem in terms of smaller copies of itself; every recursion needs a base case to stop, and each call consumes a stack frame — deep or unbounded recursion overflows the stack (convert to iteration or an explicit stack when depth can be large; JS engines blow up around a few thousand frames).

Three higher-level strategies are worth recognizing on sight:

Divide and conquer splits a problem into independent subproblems, solves each, and combines (mergesort, quicksort, binary search).
Greedy makes the locally optimal choice at each step and never reconsiders — fast and correct only when the problem has the right structure (interval scheduling, Huffman coding, Dijkstra). Prove it applies before trusting it.
Dynamic programming applies when subproblems overlap and there’s optimal substructure. You either memoize (top-down recursion + cache) or tabulate (bottom-up table), trading recomputation for memory.

DP: from exponential recursion to linear

Naive recursive Fibonacci recomputes the same subproblems exponentially — O(2ⁿ). The subproblems overlap, which is the DP trigger. Memoization caches each result so each n is computed once:

// (a) exponential — recomputes fib(n-2) etc. over and over: O(2^n)
function fibSlow(n) {
  return n < 2 ? n : fibSlow(n - 1) + fibSlow(n - 2);
}

// (b) memoized (top-down DP): each subproblem solved once → O(n) time, O(n) space
function fib(n, memo = new Map()) {
  if (n < 2) return n;
  if (memo.has(n)) return memo.get(n);        // overlapping subproblem hit
  const r = fib(n - 1, memo) + fib(n - 2, memo);
  memo.set(n, r);
  return r;
}

// (c) tabulated (bottom-up DP): same O(n) time, O(1) space — no recursion stack
function fibTab(n) {
  let a = 0, b = 1;
  for (let i = 0; i < n; i++) [a, b] = [b, a + b];
  return a;
}

The leap from O(2ⁿ) to O(n) is the entire point of DP: spend memory to stop recomputing overlapping subproblems. Tabulation additionally drops the recursion stack — handy when n is large enough to overflow it.

Pattern	Cue / when it applies	Typical Big-O
Binary search	data is sorted and you need to find something	`O(log n)`
Two pointers	sorted array + pair/triplet condition	`O(n)`
Sliding window	contiguous subarray/substring under a constraint	`O(n)`
Hashing	“seen it?”, complement, frequency, dedup, cache	`O(n)` avg
Divide & conquer	splits into independent subproblems + combine	often `O(n log n)`
Greedy	local optima provably build a global optimum	often `O(n log n)`
Dynamic programming	overlapping subproblems + optimal substructure	states × work/state

Read the cue, name the pattern — recognition speed beats memorizing solutions.

A regex that took down the internet Cloudflare

On 2 July 2019 Cloudflare suffered a global outage — HTTP 502s across a huge fraction of the web — from a single new WAF rule containing a regular expression. The pattern included .*(?:.*=.*), which on certain inputs triggers catastrophic backtracking: the regex engine explores an exponential number of ways to match, turning what looks like a linear scan into O(2ⁿ). CPU on every machine in the fleet spiked to 100%, and the proxy that serves all traffic stalled.

The lesson is pure algorithmic-complexity: a naive backtracking regex engine has an exponential worst case, and user- or rule-supplied patterns are an input you don’t control. The same recognition skill that picks “two pointers” for a sorted-pair problem is what flags “this regex can backtrack exponentially” in review. Modern fixes use linear-time engines (RE2, Rust’s regex) that compile to an automaton and guarantee O(n) — refusing the exponential constructs entirely.

read the writeup ↗ blog.cloudflare.com

Key points

Sort tradeoffs: quicksort (in place, bad worst case), mergesort (stable, O(n) space), heapsort; libs use hybrids like Timsort/introsort. Comparison sorts floor at O(n log n).
“Sorted + find” → binary search (O(log n)), including binary-searching the answer space.
Two pointers and sliding window turn O(n²) scans into O(n) passes.
Hashing is the technique for “seen it?”, complements, frequencies, dedup, and caching.
Recursion needs a base case; deep recursion overflows the stack — tabulation avoids it.
Divide & conquer (split + combine), greedy (only when locally→globally optimal), DP (overlapping subproblems + optimal substructure; memoize vs tabulate).
The goal is recognizing the pattern from the cue, not memorizing answers — and spotting exponential traps (backtracking regex) in review.

01 Learning objectives

0 / 6 done

02 Curated reading

NeetCode — Roadmap
essential 30m — Work problems by pattern, the way the source recommends.
Striver's A2Z DSA Sheet
optional 30m — Alternative pattern-based problem set.

03 Knowledge check

knowledge check4 questions · pass ≥ 70%

01easy
“The array is sorted and I need to find a value” cues which technique?
02medium
“Longest substring without repeating characters” is a classic case of:
03medium
Comparison-based sorts are bounded below by:
04hard
DP applies when a problem has overlapping subproblems AND…

04 Interview questions

browse all ↗

What gets asked on this topic — tap a card for how to approach it, the follow-ups, and the trap. Company tags are best-effort & sourced.

Commonly asked mid concept common Compare quicksort and mergesort. Why is comparison sorting bounded at O(n log n)?
Quicksort partitions around a pivot in place — average O(n log n), O(log n) stack space, but O(n^2) worst case on bad pivots and not stable. Mergesort splits and merges — guaranteed O(n log n) and stable, but needs O(n) extra space. Any comparison-based sort is bounded below by O(n log n) because there are n! possible orderings and each comparison yields one bit, so you need at least log2(n!) ~ n log n comparisons to distinguish them.
Follow-ups they push on
- How do non-comparison sorts like counting/radix beat O(n log n)?
- Why does Timsort (Python/Java) blend mergesort and insertion sort?
Red flag Calling quicksort O(n log n) worst case, or claiming any sort whatsoever beats O(n log n) (only non-comparison ones can).
source: Tech Interview Handbook — Algorithms / Sorting ↗
AmazonMetaGoogleMicrosoftBloomberg mid coding very common What cues in a problem tell you to reach for binary search? Search a rotated sorted array as an example.
The cue is 'sorted (or monotonic) + find', or a search space you can halve by a yes/no test — binary search gives O(log n). In a rotated sorted array, at each midpoint one half is still sorted; check whether the target lies within that sorted half to decide which side to discard, keeping it O(log n). Binary search also hides in 'find minimum capacity/threshold' problems via binary-search-on-the-answer.
Follow-ups they push on
- Find the minimum in a rotated sorted array.
- How do you binary-search on the answer?
Red flag Off-by-one and infinite loops from sloppy mid/low/high updates, or assuming the array must be fully sorted to apply it.
source: LeetCode 33 — Search in Rotated Sorted Array (company tags) ↗
Commonly asked mid concept common When do you use two pointers vs a sliding window? Give the canonical cue for each.
Two pointers fits sorted arrays and pair/triplet problems: move a left and right pointer inward based on a comparison (e.g. pair-sum, removing duplicates). Sliding window fits 'longest/shortest contiguous subarray or substring satisfying a constraint': grow the right edge and shrink the left when the constraint breaks. Both turn an O(n^2) brute force into O(n) by never resetting the pointers backwards.
Follow-ups they push on
- What signals a fixed-size window vs a variable-size one?
Red flag Resetting the inner pointer to the window start on each step, which silently reintroduces O(n^2) behaviour.
source: DEV — Two Pointers & Sliding Window ↗
AmazonMetaGoogleMicrosoftBloombergApple mid coding very common Find the length of the longest substring without repeating characters.
Slide a window with two pointers, tracking the characters currently inside in a hash set/map; when the right pointer hits a duplicate, advance the left pointer (removing characters) until the window is valid again, recording the max length along the way. Each character enters and leaves the window at most once, so it's O(n) time, O(min(n, alphabet)) space. The classic sliding-window-plus-hashing problem.
Follow-ups they push on
- Generalize to at most k distinct characters.
Red flag Restarting the scan from the duplicate instead of moving the left pointer, degrading to O(n^2).
source: LeetCode 3 — Longest Substring Without Repeating Characters (company tags) ↗
Commonly asked mid concept common How do you recognize a dynamic programming problem, and what's the difference between memoization and tabulation?
DP applies when a problem has overlapping subproblems (the same smaller problem recurs) and optimal substructure (the best answer is built from best sub-answers) — counting paths, min cost, longest subsequence are typical. Memoization is top-down: write the natural recursion and cache results. Tabulation is bottom-up: fill a table in dependency order, avoiding recursion overhead. Both cut exponential brute force to polynomial; choose based on which is clearer.
Follow-ups they push on
- When does tabulation let you shrink space to O(1) rows?
Red flag Reaching for greedy on a problem that needs DP (greedy gives a locally optimal but globally wrong answer).
source: NeetCode — Roadmap ↗
AmazonGoogleMeta mid coding common Given coin denominations and an amount, return the fewest coins to make that amount.
This is bottom-up DP: dp[a] = fewest coins to make amount a, computed as 1 + min over coins c of dp[a - c], with dp[0] = 0 and unreachable amounts marked infinity. Answer is dp[amount] or -1 if still infinity. O(amount * numCoins) time, O(amount) space. The interviewer is watching you state the subproblem and transition clearly — and notice that greedy (largest coin first) fails for denominations like {1, 3, 4}.
Follow-ups they push on
- Why does the greedy 'largest coin first' approach fail here?
- Count the number of ways instead of the minimum.
Red flag Using greedy largest-coin-first, which is wrong for arbitrary denominations.
source: LeetCode 322 — Coin Change (company tags) ↗
Commonly asked junior concept occasional Recursion vs iteration: what are a base case and the call stack, and when does recursion risk a stack overflow?
Recursion solves a problem by calling itself on smaller inputs until a base case stops the descent; each call pushes a frame onto the call stack and pops it on return. Without a correct base case (or with too-deep recursion) the stack grows until it overflows. Deep recursion on large inputs should be rewritten iteratively (or made tail-recursive where the language optimizes it) to use O(1) instead of O(depth) stack space.
Follow-ups they push on
- How would you convert a deep DFS recursion into an iterative one?
Red flag Omitting or mis-ordering the base case (infinite recursion), or ignoring the O(depth) stack cost on large inputs.
source: Tech Interview Handbook — Algorithms cheatsheet ↗
Commonly asked senior concept occasional Explain greedy vs divide-and-conquer vs dynamic programming. How do you know greedy is safe?
Divide-and-conquer splits into independent subproblems and combines results (mergesort, binary search). DP is for overlapping subproblems with optimal substructure, caching to avoid recomputation. Greedy makes the locally optimal choice at each step and never revisits it — fast and simple, but only correct when the problem has the greedy-choice property (e.g. interval scheduling, Dijkstra, Huffman). You justify greedy with an exchange argument or by proving the greedy choice is always part of some optimal solution; otherwise fall back to DP.
Follow-ups they push on
- Name a problem where greedy looks right but fails, and DP is needed.
Red flag Asserting a greedy strategy is correct without an exchange argument, then being blindsided by a counterexample.
source: NeetCode — Roadmap ↗
AmazonGoogleAdobe junior coding common Climbing stairs: you can take 1 or 2 steps at a time — how many ways to reach step n? Why is this Fibonacci?
The ways to reach step n equal the ways to reach n-1 (then a 1-step) plus the ways to reach n-2 (then a 2-step): ways(n) = ways(n-1) + ways(n-2) — the Fibonacci recurrence. Bottom-up DP keeping just the last two values gives O(n) time and O(1) space. Recognizing that the final move splits the problem into independent subproblems is the DP insight; the naive recursion without memoization is exponential.
What a strong answer covers
- ways(n) = ways(n-1) + ways(n-2) ⇒ Fibonacci shape.
- Subproblems overlap ⇒ DP, not naive exponential recursion.
- Rolling two variables ⇒ O(n) time, O(1) space.
- Base cases: ways(0)=1, ways(1)=1.
Follow-ups they push on
- Generalize to taking 1, 2, or 3 steps.
- What if each step has a cost and you minimize total cost (min cost climbing)?
Red flag Solving with naive O(2^n) recursion, or botching the base cases so the count is off by one.
source: LeetCode 70 — Climbing Stairs (company tags) ↗
AmazonGoogleMicrosoft mid coding common House Robber: maximize the sum of non-adjacent house values along a street.
At each house you either skip it (carry forward the best so far) or rob it (its value plus the best up to two houses back): dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Keep just the two previous results for O(n) time, O(1) space. The greedy 'rob every other house' fails — the optimal choice depends on values, which is the cue for DP over greedy.
What a strong answer covers
- Transition: dp[i] = max(dp[i-1], dp[i-2] + nums[i]) (skip vs rob).
- Two rolling variables ⇒ O(n) time, O(1) space.
- Greedy 'every other house' is wrong; the answer is value-dependent.
- Classic optimal-substructure + overlapping-subproblems DP.
Follow-ups they push on
- What changes if the houses are arranged in a circle (House Robber II)?
- Why does a greedy alternating strategy fail here?
Red flag Assuming the answer is just the larger of the even-index vs odd-index sums, which a counterexample breaks.
source: LeetCode 198 — House Robber (company tags) ↗
AmazonMetaGoogleBloomberg mid coding common Generate all subsets (the power set) of a set of distinct integers.
Use backtracking: at each index decide to include or exclude that element, recursing on the rest and recording the running subset at every node of the decision tree. There are 2^n subsets, so it's O(n·2^n) time (n to copy each subset) — inherent to the output size. An iterative alternative builds subsets by, for each new element, appending it to every subset seen so far. Passing a start index prevents revisiting earlier elements and generating duplicates.
What a strong answer covers
- Include/exclude decision per element ⇒ binary choice tree of 2^n leaves.
- Record the partial subset at every recursion node.
- O(n·2^n) — bounded by the output size itself.
- A start index avoids re-choosing earlier elements (no dup subsets).
Follow-ups they push on
- How do you handle duplicate input values (Subsets II)?
- How does this template extend to permutations and combinations?
Red flag Adding the same combination twice by recursing from index 0 instead of advancing a `start` pointer.
source: LeetCode 78 — Subsets (company tags) ↗
★ must-know Commonly asked mid concept common What's the general template for backtracking problems, and how do you prune to avoid exploring dead ends?
Backtracking is DFS over a decision tree: choose an option, explore by recursing, then un-choose (undo the change) before trying the next option. You hit a base case when a full candidate is built (record it) and prune by checking constraints *before* recursing — abandoning a branch the moment it can't lead to a valid solution. Pruning (e.g. skipping a queen placement under attack in N-Queens, or stopping when a partial sum exceeds the target) is what turns brute-force enumeration into something tractable.
What a strong answer covers
- Pattern: choose → explore → un-choose (restore state on the way out).
- Base case records a complete candidate.
- Prune early: reject a branch before recursing when it can't succeed.
- Used for permutations, combinations, N-Queens, Sudoku, word search.
Quick self-check
What is the defining structure of a backtracking algorithm?
Follow-ups they push on
- How does N-Queens prune attacked positions?
- Why must you undo the choice after recursing, not before?
Red flag Forgetting to undo the choice on the way back (state leaks across branches), or pruning only after fully building candidates.
source: Tech Interview Handbook — Recursion / Backtracking ↗
AmazonGoogleMeta senior coding occasional What is 'binary search on the answer', and when do you apply it? (e.g. minimum capacity / Koko eating bananas)
When the input isn't sorted but the answer space is monotonic — a candidate value either works or doesn't, and 'works' is monotone (if capacity X works, every larger capacity also works) — you binary-search over the range of possible answers, using a feasibility check as the comparison. Example: find the minimum eating speed so Koko finishes in H hours — binary-search the speed and test 'can she finish at speed k?' in O(n) each, giving O(n log(max)) overall. The trick is spotting the monotone yes/no boundary you can bisect.
What a strong answer covers
- Search the answer range, not the array, when answers are monotone.
- Need a feasibility test: 'does candidate value X satisfy the constraint?'
- Bisect toward the boundary between feasible and infeasible.
- Cost = O(check · log(range)), e.g. O(n log(max)).
Follow-ups they push on
- How do you prove the feasibility predicate is monotonic?
- Apply it to 'minimum days to ship all packages within D days'.
Red flag Applying it when the feasibility predicate isn't monotonic, so bisection converges to a wrong boundary.
source: LeetCode 875 — Koko Eating Bananas (company tags) ↗
★ must-know AmazonMicrosoftGoogleBloombergApple mid coding very common Find the contiguous subarray with the largest sum (Maximum Subarray / Kadane's algorithm).
Kadane's algorithm: scan once, maintaining curr = max(x, curr + x) (either start fresh at x or extend the running subarray) and tracking the best curr seen. O(n) time, O(1) space. The key decision at each element — extend the previous subarray or restart — is a one-line DP. Watch the all-negative case: initialize the answer to the first element (or -∞), not 0, so you don't wrongly return 0 for an empty subarray.
What a strong answer covers
- Per element: curr = max(x, curr + x) — extend or restart.
- Track the maximum curr; O(n) time, O(1) space.
- It's a one-variable DP (running best ending here).
- All-negative inputs: init answer to first element, never 0.
Quick self-check
Why initialize Kadane's answer to the first element (or -∞) rather than 0?
Follow-ups they push on
- How would you also return the start/end indices of the subarray?
- What changes for the maximum *product* subarray?
Red flag Initializing the max to 0, which returns 0 for an all-negative array instead of the largest (least negative) element.
source: LeetCode 53 — Maximum Subarray (company tags) ↗
AmazonMetaGoogleMicrosoftApple mid coding very common Compute the product of all elements except self, without using division and in O(n).
Use prefix and suffix products: first pass fills each position with the product of everything to its left; second pass multiplies in the product of everything to its right (tracked in a running variable). O(n) time, O(1) extra space if the output array doesn't count. Division would be the obvious trick but is explicitly banned — and it breaks on zeros anyway, which is exactly why the prefix/suffix approach is the expected answer.
What a strong answer covers
- Left-products pass, then a right-products running multiply.
- O(n) time, O(1) extra space (output aside).
- Avoids division — which the problem bans and which fails on zeros.
- Each output = (product of all left) × (product of all right).
Follow-ups they push on
- Why is the division approach fragile when the array contains a zero?
- How do you keep it O(1) extra space (reusing the output array)?
Red flag Using division (banned, and breaks with one or more zeros) instead of prefix/suffix products.
source: LeetCode 238 — Product of Array Except Self (company tags) ↗