Theory then practice
Prerequisites: Arrays, maps, queues and graph representations.
Describe growth, assumptions and memory costs before optimizing.
Derive pointer movement from a maintained invariant.
Match the traversal algorithm to the meaning of an edge.
Choose a technique by subproblem structure rather than memorizing names.
Avoid quadratic rescans by reusing what earlier comparisons already proved.
Try answering aloud before opening an answer. Reading an answer is exposure, not proof of independent mastery. Save reflections in your mistake notebook.
Beginner
Big O is an asymptotic upper bound, Ω a lower bound and Θ a tight bound in a stated cost model. Specify worst case, expected or amortized separately; the notation alone does not choose a case.
Example: A complete array scan is Θ(n) even though O(n²) is also a loose upper bound.
Common mistake: Big O is not a stopwatch measurement or automatically the worst case.
Follow-up: Why can an O(n²) algorithm win for tiny inputs?
Beginner
Add consecutive costs and multiply nested costs only after checking their bounds. A dependent inner bound may form a sum; two pointers that only advance can still take linear total work.
Example: A loop over n customers containing a loop over m orders costs O(nm).
Common mistake: Two syntactically nested loops are not automatically O(n²).
Follow-up: Analyze a pointer that advances across the input only once.
Beginner
Keep the possible answer inside a clearly defined interval, compare its middle and discard an impossible half. State whether endpoints are inclusive; compute mid as low + (high - low) / 2.
Example: Find the first value at least a target using a half-open interval.
Common mistake: Returning any matching duplicate does not implement lower bound.
Follow-up: How would you search a monotone feasibility function?
Beginner
Exploit an invariant that tells you which pointer can move without losing a solution. In a sorted pair-sum search, a sum too small means the left value must increase.
Example: Find a pair summing to a target in a sorted array.
Common mistake: Sorting changes original indices unless you preserve them explicitly.
Follow-up: What if the input is unsorted and original indices are required?
Beginner
Sort intervals by start. Walk them while keeping a current merged interval: if the next start is at most the current end, extend the end to the maximum of both ends; otherwise emit the current interval and start a new one. Sorting makes every possible overlap adjacent, so a single pass suffices.
Example: [[1,3],[2,6],[8,10],[9,12]] becomes [[1,6],[8,12]].
Common mistake: Forgetting to take the maximum end; [1,10] followed by [2,3] must stay [1,10], not shrink to [1,3].
Follow-up: How would you insert one new interval into an already merged, sorted list without resorting?
Intermediate
Maintain a contiguous interval and an invariant that can be updated incrementally. The condition must tell you how shrinking affects validity; arbitrary negative values break some sum-based shrink rules.
Example: Longest substring without repeated characters uses last-seen positions.
Common mistake: The positive-only minimum-sum window algorithm is incorrect with unrestricted negatives.
Follow-up: Which data structure supports signed prefix sums instead?
Intermediate
Store cumulative totals so a range sum becomes the difference of two prefix totals. For target-sum subarray counting, a frequency map of earlier prefixes avoids enumerating every range.
Example: Initialize frequency of prefix zero to one so ranges starting at index zero count.
Common mistake: A set loses multiplicities when equal prefix totals occur repeatedly.
Follow-up: How do you handle many updates as well as queries?
Intermediate
Merge sort gives predictable n log n work and can be stable. Quicksort partitions in place but depends on pivot quality; heapsort gives worst-case n log n without linear merge workspace.
Example: Choose a stable merge implementation when equal-key records must retain input order.
Common mistake: Do not claim every library sort uses the same algorithm or workspace.
Follow-up: When can counting sort beat comparison sorting?
Intermediate
BFS finds minimum edge count from a source in an unweighted graph. DFS is useful for dependency structure, cycle reasoning and exhaustive exploration; both need visited tracking on general graphs.
Example: Use BFS to find the fewest moves in an unweighted maze.
Common mistake: Marking visited only on dequeue can enqueue duplicates unnecessarily.
Follow-up: Why does BFS fail as a shortest-path method for arbitrary weighted edges?
Advanced
Repeatedly settle the unsettled vertex with smallest tentative distance and relax outgoing edges. Nonnegative weights make the settled distance final; negative edges invalidate that argument.
Example: Find cheapest routes with nonnegative fares and a min-priority queue.
Common mistake: A visited flag alone cannot fix Dijkstra for negative edges.
Follow-up: Which algorithm would you choose with negative edges?
Intermediate
In Kahn's algorithm, enqueue zero-indegree vertices, remove them and decrement successors. If fewer than V vertices are emitted, a directed cycle prevents a full ordering.
Example: Order build steps while allowing independent steps to run together.
Common mistake: A valid ordering is not necessarily unique.
Follow-up: How would you report an actual cycle rather than only its presence?
Intermediate
Define states whose optimal values depend on smaller states, with overlapping subproblems and a valid recurrence. State the base cases and evaluation order before optimizing storage.
Example: For climbing stairs, ways(i) = ways(i-1) + ways(i-2) with defined starting cases.
Common mistake: Memoizing an incorrect state definition does not make the recurrence correct.
Follow-up: Which states can be discarded after processing?
Advanced
A one-dimensional DP must read values from the previous item iteration. Descending capacity prevents the current item from being reused during its own update.
Example: At capacity ten, one item of weight five can be selected only once.
Common mistake: Ascending capacity solves an unbounded reuse variant instead.
Follow-up: Why is this called pseudopolynomial time?
Advanced
At each position choose include or exclude, maintaining a partial choice and undoing it afterward. There are 2^n subsets; copying each output contributes up to n work.
Example: Generate all subsets, including the empty subset.
Common mistake: Reporting O(2^n) alone ignores materializing the elements of every subset.
Follow-up: How would duplicate inputs change generation?
Advanced
Prove that a locally chosen step can be part of an optimal solution, often by exchange argument, then show the remaining problem has the same structure.
Example: For maximum nonoverlapping intervals, choose the earliest finishing interval next.
Common mistake: A greedy rule that works for unweighted intervals need not solve weighted scheduling.
Follow-up: Give a counterexample to selecting the shortest interval.
Advanced
KMP precomputes a prefix function: for each pattern prefix, the longest proper prefix that is also a suffix. On a mismatch, the matcher falls back to that border instead of restarting, so text characters are never re-examined. The pointer into the pattern increases at most once per text character, which bounds total fallbacks.
Example: Pattern ababc has borders [0,0,1,2,0]; after matching abab and failing on c, matching resumes at position 2.
Common mistake: Claiming the nested while loop makes it O(n·m); the amortized argument shows total fallback work is O(n).
Follow-up: How would you find all occurrences, including overlapping ones?
Advanced
Amortized cost is the average over a worst-case sequence of operations, not an expectation over random inputs. When a dynamic array doubles from capacity c to 2c, it copies c elements, but that happens only after c cheap appends. Over n appends total copies are below 2n, so each append is O(1) amortized even though a single append can cost O(n).
Example: Appending 1,024 items with doubling from capacity 1 copies 1 + 2 + ... + 512 = 1,023 elements in total.
Common mistake: Confusing amortized with average-case; amortized bounds hold for every sequence, while a latency-sensitive single call can still pay O(n).
Follow-up: Why does growing by a fixed 100 elements instead of doubling make appends O(n) amortized?
Intermediate
Write the recurrence and count both work per level and depth. Include stack frames in auxiliary space even when no explicit collection is allocated.
Example: Merge sort uses T(n) = 2T(n/2) + O(n), giving logarithmically many linear-work levels.
Common mistake: Depth O(log n) does not mean the whole algorithm is O(log n).
Follow-up: What changes if each recursive call copies its input slice?
Intermediate
XOR every element. XOR is associative and commutative, x ^ x = 0 and x ^ 0 = x, so paired values cancel and the unique value remains. This uses constant extra space, unlike a hash-set count, and a single pass.
Example: [4, 1, 2, 1, 2] → 4 ^ 1 ^ 2 ^ 1 ^ 2 = 4.
Common mistake: Applying the same trick when others appear three times; that variant needs per-bit counts modulo three.
Follow-up: If two distinct values appear once, how can x & -x split the array into two groups?
Intermediate
Quickselect partitions around a pivot like quicksort but recurses only into the side containing the target rank. With a random pivot the expected work is n + n/2 + n/4 ... = O(n). Alternatively, a min-heap of size k gives O(n log k), which is better for streams or when k is small.
Example: For k = 1 in a million-element array, quickselect touches about two million elements on average; a full sort costs about twenty million comparisons.
Common mistake: Using the first element as pivot on sorted input degrades quickselect to O(n²); randomize or use median-of-medians.
Follow-up: When would you prefer the heap approach despite its log k factor?