Coding Interview Question Bank

Pattern: Two pointers·Complexity: O(n) time, O(1) space

Start pointers at both ends of the sorted array. If the sum is too small, advance the left pointer; too large, retreat the right. Sortedness guarantees you never skip a valid pair — that invariant is what interviewers want you to state out loud.

Pattern: Hash map / counting·Complexity: O(n) time, O(1) space for a fixed alphabet

Count character frequencies of the first string, decrement while scanning the second, and check all counts return to zero. Mention the follow-up before being asked: for full Unicode, a fixed 26-slot array no longer works — use a hash map.

Pattern: Floyd's slow/fast pointers·Complexity: O(n) time, O(1) space

Advance one pointer by one node and another by two; if they ever meet, a cycle exists. Be ready for the classic follow-up — finding the cycle entry: reset one pointer to head and advance both by one until they meet again.

Pattern: Boyer–Moore voting·Complexity: O(n) time, O(1) space

Keep a candidate and a counter: increment on match, decrement on mismatch, replace the candidate when the counter hits zero. Because the majority element appears more than n/2 times, it always survives. Explaining WHY it survives is the interview.

Pattern: One pass, running minimum·Complexity: O(n) time, O(1) space

Track the minimum price seen so far and the best profit if selling today. One scan, two variables. It is the smallest instance of the "carry the best prefix state" idea that later shows up in Kadane's algorithm — naming that connection scores points.

Pattern: Sort + linear sweep·Complexity: O(n log n) time, O(n) space

Sort intervals by start, then sweep: if the current interval starts after the last merged one ends, append it; otherwise extend the merged end to the max of both. Sorting is doing the real work — say so, and get the comparator edge cases (touching intervals) right.

Pattern: Hash set + sequence starts·Complexity: O(n) time, O(n) space

Put every number in a set; only start counting from numbers whose predecessor is absent (sequence starts), then walk forward. Each element is visited at most twice, which is how you defend the O(n) claim against the "but there's a nested loop" objection.

Pattern: Prefix/suffix products·Complexity: O(n) time, O(1) extra space beyond the output

Two passes without division: first fill each slot with the product of everything to its left, then sweep from the right multiplying in the product of everything to the right. Division-based answers fail the zero cases — interviewers usually ban it explicitly.

Pattern: Auxiliary stack invariant·Complexity: O(1) per operation, O(n) space

Alongside the value stack, keep a min stack whose top is always the minimum of everything below it — push min(new, current top), pop in lockstep. This is a design question: the invariant, not code volume, is what you are being graded on.

Pattern: Hash map + doubly linked list·Complexity: O(1) per get/put, O(capacity) space

A hash map gives O(1) lookup into nodes of a doubly linked list ordered by recency; move a node to the head on access, evict from the tail on overflow. Sentinel head/tail nodes remove every null-check edge case — mention them before you start coding.

Pattern: Grid BFS/DFS flood fill·Complexity: O(rows × cols) time

Scan the grid; each unvisited land cell starts a flood fill (DFS or BFS) that marks the whole island visited, and you count the starts. State your visited-marking strategy (in-place sink vs separate set) and the recursion-depth risk on huge grids — that is the senior signal.

Pattern: Topological sort / cycle detection·Complexity: O(V + E) time

Model prerequisites as a directed graph; the question 'can you finish' is exactly 'is the graph acyclic'. Kahn's algorithm (repeatedly remove zero-in-degree nodes) or DFS three-coloring both work — pick one and narrate why a leftover node means a cycle.

Pattern: BFS with level snapshots·Complexity: O(n) time, O(width) space

BFS with a queue, but snapshot the queue length at each round so you emit one list per level. That length-snapshot trick is the reusable core — zigzag traversal and right-side view are the same loop with a different collection step.

Pattern: Bounds propagation / inorder·Complexity: O(n) time, O(height) space

Recurse with an allowed (min, max) window that tightens at each step — or do an inorder traversal and check it is strictly increasing. The classic trap is only comparing children to their parent; construct the counterexample yourself before the interviewer does.

Pattern: Two-way hash mapping (bijection)·Complexity: O(n) time, O(n) space

Map pattern characters to words AND words back to characters — one direction alone accepts pattern "ab" for "dog dog". Checking the bijection both ways is the entire trick; say the word "bijection" and handle the length-mismatch case before coding.

Pattern: Cycle detection on a hidden sequence·Complexity: O(log n) per step; O(1) space with Floyd

Repeatedly replacing a number with the sum of squared digits either reaches 1 or enters a loop — so this is Linked List Cycle in disguise. Detect the loop with a seen-set, or impress with Floyd's slow/fast pointers for O(1) space. Naming the reduction to cycle detection is the senior move.

Pattern: Greedy with a proof obligation·Complexity: O(n) time, O(1) space

If total gas ≥ total cost, an answer exists and it is unique. Sweep once tracking a running tank; whenever it goes negative, no station in the failed stretch can be the start — restart from the next station. The interview is the justification of that skip, not the loop itself.

Pattern: Greedy / implicit BFS layers·Complexity: O(n) time, O(1) space

Treat indices reachable within k jumps as a BFS layer: track the current layer's right edge and the farthest reach seen; when you walk past the edge, increment jumps and extend the edge to that farthest reach. Framing it as BFS-without-a-queue explains WHY greedy is optimal here.

Pattern: Three-phase linear merge·Complexity: O(n) time, O(n) space

Emit intervals that end before the new one starts, then absorb every overlapping interval into the new one (min start, max end), then emit the rest. The sorted input means one pass with no re-sort — contrast that with Merge Intervals if asked why this is easier.

Pattern: In-place matrix transform·Complexity: O(n²) time, O(1) space

Rotate 90° clockwise = transpose, then reverse each row. Two clean passes with O(1) extra space beats hand-deriving the four-way cycle swap under pressure — but be ready to explain the coordinate mapping (i,j) → (j, n−1−i) if the interviewer pushes past the trick.

Pattern: In-place marking with borrowed storage·Complexity: O(m×n) time, O(1) space

Use the first row and first column as the flag storage for which rows/columns must zero out, with two booleans remembering their own state. Walk the space ladder out loud — O(mn) copy → O(m+n) sets → O(1) borrowed-storage — because the ladder itself is what is being tested.

Pattern: Sorting / counting buckets·Complexity: O(n log n) sorted, O(n) with buckets

Sort descending and find the largest i where citations[i] ≥ i+1 — or skip sorting with counting buckets capped at n for O(n). State the definition precisely before coding; most failures on this problem are misreading "h papers with at least h citations", not the algorithm.

Pattern: Topological sort, order emitted·Complexity: O(V + E) time

Same graph as Course Schedule, but now Kahn's algorithm earns its keep: the order in which zero-in-degree nodes leave the queue IS a valid course order. If the emitted order is shorter than the course count, a cycle exists — return empty. Mention DFS post-order reversed as the alternative.

Pattern: Sliding window with a satisfaction counter·Complexity: O(n) time, O(alphabet) space

Expand the right edge until the window covers every required character (track a "formed vs required" counter, not a full map comparison per step), then contract the left edge to the minimum while still valid, recording the best. The formed-counter optimization is what keeps it O(n) — explain it explicitly.

Pattern: Two pointers over running maxima·Complexity: O(n) time, O(1) space

Water above each bar is min(max-left, max-right) − height. Two pointers moving inward from both ends let you resolve whichever side has the lower running max, because that side's bound is already final. Walk through why that certainty holds — it is the entire question.