25 essential coding interview questions. Each question includes a full Python solution with step-by-step explanation and complexity analysis.
BFS/DFS, multi-source BFS, cycle detection, and flood-fill on graphs and grids.
Use BFS with a hash map from original node → clone. The map prevents revisiting nodes and stores the clone reference simultaneously.
Key insight: The hash map does double duty — visited check AND original→clone mapping. Without it, cycles cause infinite recursion.
clones), we create its clone and enqueue it. Either way, we append the neighbor's clone to the current node's clone's neighbor list. When BFS ends, every reachable node has been cloned with correct edges.Build a directed prerequisite graph. Use Kahn's BFS topological sort — if all n nodes are processed, no cycle exists (can finish all courses).
Key insight: If processed count == numCourses after BFS, no cycle. Any unprocessed node is part of a cycle.
Seed a BFS queue with all 0-cells at once. Propagate distances outward — the first time BFS reaches a 1-cell is its shortest distance.
Key insight: Multi-source BFS from all zeros simultaneously. BFS's layer-by-layer expansion guarantees the first visit = shortest path.
(nr, nc), its distance is dist[r][c] + 1. Since BFS processes nodes in order of increasing distance, the first time we set dist[nr][nc] is optimal — we only update if we find a shorter path.For each unvisited '1', increment the count and DFS to flood-fill the entire island, marking cells as visited.
Key insight: Modify the grid in-place (set '1' → '0') as the visited marker. No extra space needed.
'1', we found a new island — increment count, then call DFS to sink all connected land. DFS marks cells '0' in-place so they won't be counted again. After DFS returns, the entire island is consumed. We continue scanning for the next unvisited island.Multi-source BFS from all rotten oranges. Each BFS level = 1 minute. Track fresh count — if any fresh remain after BFS, return -1.
Key insight: BFS models simultaneous spread — all sources expand in the same round. Count fresh oranges upfront and decrement during BFS.
t + 1. We track max_time (the last infection timestamp) and fresh (decrement on each infection). If fresh == 0 after BFS, all oranges rotted — return max_time.Interval merging, two-pointer k-sum, prefix products, backtracking, and greedy overlap detection.
Single linear pass: collect intervals before the new one, merge all overlapping ones, then collect those after.
Key insight: Three phases in one pass. Once the new interval is flushed, all remaining intervals are untouched — just extend with a slice.
Sort + for each element use a two-pointer search for a pair summing to its negation. Skip duplicates at every level.
Key insight: Sorting makes duplicate-skipping trivial. Two pointers give O(n) inner loop, giving O(n²) overall.
nums[i], then find pairs summing to -nums[i] using two pointers converging from both ends. If sum is too small, advance left; too large, retreat right; equal, record and skip duplicates. The duplicate-skipping after finding a valid triplet ensures unique results.Two passes: left→right builds prefix products into output. Right→left multiplies by running suffix. No division, O(1) extra space.
Key insight: result[i] = prefix[i] × suffix[i]. Second pass uses a running variable — no separate suffix array needed.
result[i] holds the product of everything to the left of index i (prefix). Pass 2 multiplies each position by the running suffix (product of everything to the right). The final result[i] = left-product × right-product = product of all except nums[i].Backtracking: pick from start index onward (allowing reuse), recurse, undo. Prune when sum exceeds target.
Key insight: Passing start (not start+1) allows reuse of the same candidate. The start index prevents reversed duplicates like [2,3] vs [3,2].
start onwards. We append the candidate, recurse to try combinations for the reduced remainder, then pop it (undo). Using i (not i+1) in the recursive call allows reusing the same element. Candidates equal to remaining are valid; those larger are skipped (pruning).Sort by start time, then one pass: if current interval overlaps the last merged one, extend it. Otherwise push as new.
Key insight: Sorting guarantees overlapping intervals are adjacent. One comparison per interval is sufficient — no look-back needed.
merged[-1] (the last merged entry). If start <= merged[-1][1], they overlap — we take the max of the two ends. Otherwise, append the current interval as a new group.Postfix evaluation, O(1) minimum retrieval, and two-pointer rain water.
Push numbers onto a stack. On operator: pop two operands (order matters!), apply op, push result.
Key insight: b = pop(), a = pop() → compute a op b. Reversing a and b gives wrong results for subtraction/division.
int(a / b) (not a // b) correctly truncates toward zero for negative numbers.Store (value, current_min) pairs. Each push records the minimum at that point in time.
Key insight: Each entry snapshots the minimum including itself. When it's popped, the previous minimum is restored at the new top.
push stores a pair: the value and the running minimum at that stack depth (the smaller of the new value and the current stack top's min). getMin() just peeks stack[-1][1]. When we pop, the previous minimum is automatically restored because it was saved in the new top entry.Two pointers: always process the shorter boundary. Water = shorter boundary height − current bar height.
Key insight: Process the shorter side because you know its limiting wall. The taller opposite side can only be ≥ our current max — so the water calculation is guaranteed safe.
height[left] <= height[right]) and process it. If it's taller than max_left, update the max (no water here — it's a wall). Otherwise, water fills the dip: max_left - height[left]. Processing the shorter side is safe because the other side is guaranteed to be at least as tall as our current max — the limiting factor is our current side's max.BFS level-order, LCA via recursive DFS, and preorder serialize/deserialize.
BFS with queue. Snapshot queue size at each round to separate levels.
Key insight: level_size = len(queue) before the inner loop. Process exactly that many nodes — their children are for the next level.
len(queue) — that's exactly how many nodes belong to the current level. We dequeue exactly that many, collect their values, and enqueue their children. The children are added to the queue but only processed in the next outer iteration. This cleanly separates levels without sentinel markers.DFS: return node if it's null/p/q. If both left and right return non-null, the current node is the LCA.
Key insight: "Both children return non-null" = p and q found on opposite sides = this node is the split point = LCA.
Preorder DFS with '#' as null marker. Deserialize by consuming tokens with an iterator.
Key insight: Null markers are essential — without them the same preorder sequence can describe many different trees.
'#'. Deserialization uses an iterator over the comma-split tokens. Each recursive build() call consumes exactly one token. If it's '#', return None. Otherwise create the node and build its left then right subtrees recursively — the iterator naturally tracks position.Kadane's algorithm for max subarray, and bottom-up coin change (unbounded knapsack).
At each element: curr = max(num, curr + num). Extend the run or restart — whichever is larger.
Key insight: If the running sum becomes negative, it's a drag — start fresh at the current element. Track the global max separately.
curr_sum tracks the best subarray ending at the current index. If curr_sum + num < num, then curr_sum is negative — it's better to discard the previous run and start fresh at num. We update max_sum after every step to capture the global best. Both are initialized with nums[0] to handle all-negative arrays.Bottom-up DP. dp[i] = min(dp[i - c] + 1) for each coin c. Build from 0 up to amount.
Key insight: Unbounded knapsack pattern — coins can be reused. Each dp[i] represents the minimum coins for that sub-amount. Build up from the base case dp[0] = 0.
i, we try using each coin c. The cost is 1 (for coin c) plus the minimum coins needed for the remainder i - c. Since we've already computed all smaller amounts, dp[i - c] is ready. If dp[amount] is still infinity after filling the table, the amount is unreachable — return -1.Modified binary search on rotated arrays, and floor search for timestamped lookups.
At each step, determine which half is sorted (compare mid vs left). If target in the sorted half, search it; otherwise search the other half.
Key insight: One half is ALWAYS fully sorted after any rotation. Identify it in O(1), check if target is within its range, binary search accordingly.
nums[left] to nums[mid]: if nums[left] <= nums[mid], the left half is sorted (no rotation in it). We then check if target lies within its range — if yes, search left; if no, search right. The right half check is symmetric.Store sorted (timestamp, value) pairs per key. Use bisect_right - 1 (floor search) for O(log n) get.
Key insight: bisect_right(timestamps, target) - 1 gives the largest timestamp ≤ target — the "floor" pattern.
set appends to the list — since timestamps are strictly increasing, the list stays sorted. For get, we use bisect_right to find the insertion point for (timestamp, chr(127)) (a sentinel that sorts after any value string at that timestamp). Subtracting 1 gives the index of the largest timestamp ≤ query — the floor. If idx is -1, no valid timestamp exists.Sliding window — no-repeat substring and minimum window with full character matching.
Sliding window + hash map (char → last index). Jump left past the duplicate in O(1).
Key insight: Store the character's index, not just a boolean. This lets you jump left directly past the duplicate — avoiding O(n) shrinking.
last_seen[char] stores where we last saw a character. If we see a duplicate that's still inside [left, right], we jump left to last_seen[char] + 1 — shrinking the window in one step. The window invariant is: no duplicate characters in s[left..right]. We update last_seen every visit and track the max window size.Expand right until valid (all t chars covered), then shrink left to minimize. Track formed counter for O(1) validity.
Key insight: formed increments only when a char's count crosses its required threshold. This gives O(1) validity check without scanning the full frequency map.
formed increments. When formed == required, the window is valid. We then shrink from the left — updating the best window if it's smaller — until the window becomes invalid (removing left char causes formed to drop). Then we expand right again.Max-heap of size k for top-K selection, and two-heap technique for streaming medians.
Max-heap of size k. Push (dist², x, y). When size exceeds k, pop the max (farthest). Heap always holds the k closest.
Key insight: Negate distance for max-heap behavior in Python (min-heap by default). Use dist² to skip sqrt.
heapq is a min-heap. To get max-heap behavior, we negate the distance. We push (-dist, x, y) for every point. When the heap grows beyond k, we pop — which removes the most negative value, i.e., the largest (farthest) distance. After processing all points, the heap contains exactly the k closest.Two heaps: max-heap lo (lower half), min-heap hi (upper half). Keep sizes balanced. Median = top(s).
Key insight: Two heaps split the stream at the median. Their tops are always the two middle values — median is O(1).
lo stores the lower half (max-heap via negation), hi stores the upper half (min-heap). After each push, two invariants are maintained: (1) every element in lo ≤ every element in hi (corrected by moving lo's max to hi), and (2) sizes differ by at most 1. The median is either the average of both tops (even count) or lo's top (odd count — lo gets the extra).Backtracking with in-place swaps to enumerate all permutations.
At each level, swap each element into the "decided" position, recurse, then swap back (undo).
Key insight: Array is split into "decided" (0..start-1) and "choosing" (start..end). Each undecided element gets a turn at position start. Swap back restores state for the next iteration.
backtrack(start) generates all permutations of nums[start:]. We try each element from start to end as the next element at position start by swapping it into that position. After recursing, we swap back (undo) to restore the original state for the next iteration. When start == len(nums), all positions are decided — we've built a complete permutation.Try answering before revealing — fastest way to find gaps.