Coding Interview Prep Guide

A function that calls itself on a smaller input - the call stack handles bookkeeping so you only need to define the base case and the recursive step, trusting that smaller subproblems are already solved.

The most fundamental data structure - contiguous memory, O(1) access, and the three patterns (two pointers, sliding window, prefix sums) that unlock most array interview problems.

Halving the search space - how binary search achieves O(log n), how to get the boundary conditions right, and how to apply the same idea beyond sorted arrays to any problem with a monotonic feasibility check.

Count distinct ways to reach the top of n stairs climbing 1 or 2 steps at a time - a Fibonacci recurrence solvable in O(1) space with two rolling variables.

Seen-before check with a set: O(1) membership test replaces an O(n) scan per element.

Compute the nth Fibonacci number recursively - the naive O(2^n) call tree collapses to O(n) once overlapping subproblems are cached with memoization.

Build insert, search (exact match), and starts_with (prefix check) on a trie - the foundation for autocomplete and prefix-based lookups.

Greedy reachability frontier: determine if you can reach the last index by tracking the farthest reachable position at each step.

Min-heap of size K: maintain only the K largest elements seen so far; the root is always the Kth largest.

Fixed sliding window: find the contiguous subarray of length k with the highest average in O(n) by sliding a running sum.

Postorder recursion: depth = 1 + max(left_depth, right_depth) - children are resolved before the parent.

BFS stop-on-first-leaf: the first leaf BFS reaches is guaranteed to be at minimum depth - no full traversal needed.

Count connected land regions in a 2D grid using DFS with in-place mutation to mark visited cells

Count connected components in an adjacency matrix using Union-Find with path compression and union by rank.

Queue as a sliding time window: enqueue each ping timestamp and popleft all timestamps outside the 3000ms window before returning the count.

Tree DFS carrying remaining sum: recurse with remaining_sum minus node value; return true when a leaf is reached with remaining_sum equal to zero.

A concise protocol for clarifying, planning, building, testing, and explaining a coding solution under interview pressure.

XOR cancellation practice: every element in the array appears twice except one. Find the unique element in O(n) time with O(1) space.

Generate the power set of a distinct-element array using backtracking: record path at every node, not just leaves.

Opposite-ends two-pointer on a sorted array: converge left and right based on whether the current sum is too small or too large.

Deep copy a connected undirected graph using DFS with a hash map to track original-to-clone node mapping

Find all unique combinations summing to target where candidates can be reused: backtrack with start index and break pruning after sorting.

Fixed-capacity array with head/tail pointers and modular arithmetic - enqueue advances tail, dequeue advances head, both wrap around with % capacity.

Maximize loot from an array of houses without robbing two adjacent houses - at each house decide rob or skip, using two rolling variables for O(1) space.

Preorder DFS: swap left and right children at the current node before recursing - produces a mirror image of the original tree.

Nodes connected by pointers - the three patterns that cover 90% of linked list interviews: reversal, fast/slow pointers, and two-pointer with offset.

Grid DFS accumulating area: DFS from each unvisited 1-cell, mark visited by setting to 0, return the count of cells reached - track the maximum across all islands.

Interval merging pattern: sort by start time, then extend or append as you scan - produces a minimal non-overlapping set.

Augment a stack with O(1) minimum retrieval using a parallel auxiliary stack that tracks the running minimum.

Count the 1-bits in a non-negative integer using the Kernighan trick - n &= n-1 clears the lowest set bit, so the loop runs exactly popcount(n) times.

Fixed window frequency match: slide a window of len(s1) over s2 comparing character counts to detect any permutation of s1.

Implement x raised to the power n using divide-and-conquer - halve the exponent each call for O(log n) multiplications instead of O(n).

Cycle detection in undirected graphs: the first edge whose endpoints share a root is the redundant edge creating the cycle.

Replace each word in a sentence with its shortest dictionary root using a trie - walk until is_end=True and return the root prefix found.

Multi-source BFS: enqueue all rotten oranges simultaneously and let BFS compute each fresh orange's minimum time-to-rot in a single pass.

Leftmost binary search: given a sorted array and a target, return its index or the index where it would be inserted to keep the array sorted.

A compact map of five practical coding shapes, their first state choices, failure modes, and speed drills.

Dutch national flag algorithm: three pointers partition 0s, 1s, and 2s in one pass without counting or using library sort.

Frequency count plus min-heap of size K: keep only the K highest-frequency (count, element) pairs seen so far.

Two index variables that eliminate the inner loop - the opposite-ends pattern for sorted-array pair problems and the same-direction pattern for partitioning and in-place removal.

Character frequency counting: two strings are anagrams when their character frequency dicts are equal.

Opposite-ends two-pointer with character normalization: skip non-alphanumeric characters and compare the remaining characters case-insensitively.

Union all emails within an account, then group emails by root representative to reconstruct merged accounts with sorted emails.

Detect a cycle in a directed prerequisite graph using Kahn's topological sort to check if all courses can finish

Canonical monotonic stack problem: find the next warmer day for each index in O(n) using a decreasing stack of indices.

Binary search on a rotated array: find the minimum by detecting which half is sorted and whether the inflection point lies left or right of mid.

Recursively flatten a list of integers and sublists to any depth - if an element is a list, recurse into it; if it is a value, collect it.

Grouping by derived key: sorted characters form a canonical key that routes every anagram to the same bucket.

Max-heap of size K keyed on negated squared distance: keep only the K nearest points; pop the farthest when the heap exceeds K.

Variable window with a character set: expand right until a duplicate appears, shrink left until it is gone, track the longest valid window.

Minimum removals to make intervals non-overlapping: sort by end time and greedily keep the interval finishing earliest.

Generate all orderings of distinct integers using backtracking: track used elements with a boolean array, loop from index 0 every call.

Determine if n is an exact power of two - a power of two has exactly one bit set, so clearing the lowest set bit with n & (n-1) produces 0.

Same-direction slow/fast pointers: slow tracks the next write position, fast scans for new values and writes them at slow's position.

Simultaneous DFS on two trees: both null means equal, one null means not equal, then compare values and recurse on both sides.

Return up to 3 lexicographic suggestions after each keystroke using a trie - navigate to the prefix node, then DFS to collect sorted completions.

Grid BFS with 8-directional movement: BFS guarantees the first path to reach the destination is the shortest - count steps from (0,0) to (n-1,n-1) through 0-cells.

A contiguous subarray maintained by advancing start and end pointers - fixed-size windows for k-element aggregates and variable-size windows for constraint-satisfying substrings.

Merge sort on a linked list: find the middle with slow/fast pointers, split, sort each half recursively, then merge - O(n log n) time O(1) space.

LIFO storage built on a Python list - the two patterns that cover most stack interviews: monotonic stack for next-greater problems and an explicit stack for DFS and bracket matching.

Count distinct paths for a robot moving only right or down in an m x n grid - 2D DP where each cell sums the paths from above and from the left.

Sort first, fix one element with an outer loop, then apply opposite-ends two pointers on the rest - skip duplicates at all three positions.

Level-by-level graph traversal using a queue - guarantees the shortest path in unweighted graphs and naturally groups nodes by their distance from the source.

BFS with level-size snapshotting: capture len(queue) before the inner loop to group nodes by depth into separate lists.

Find the minimum coins to make an amount - 1D unbounded knapsack where dp[amount] = min(dp[amount - coin] + 1) for each coin; initialize unreachable states to infinity.

Return the popcount for every integer from 0 to n in O(n) time - popcount(i) = popcount(i >> 1) + (i & 1) reuses already-computed results by linking each number to its right-shifted half.

Extend a trie with '.' wildcard matching - handle exact characters normally and recurse into all children when a dot is encountered.

Operand stack evaluation: push numbers, pop two operands on each operator, push the result.

Answer-space binary search: find the minimum eating speed that lets Koko finish all piles within H hours by binary searching over feasible speeds.

Custom sort comparator: compare string concatenations in both orders to determine which arrangement of two numbers produces the larger value.

Variable window with a max-frequency trick: the window is valid when window_size - max_freq <= k, letting you grow as long as replacements stay within budget.

Minimum conference rooms via greedy heap: sort by start time, reuse the room whose meeting ends soonest when it frees up.

K-way merge with a min-heap: always extract the global minimum in O(log K) by seeding the heap with the head of each list.

Count connected components in an undirected graph by launching DFS from each unvisited node

FIFO storage built on collections.deque - the two patterns that appear in nearly every queue interview: BFS level traversal and the monotonic deque for sliding window extremes.

Two-pass Union-Find: union all == pairs first, then verify no != pair shares a root - order of passes matters.

Generate the power set of an array that may contain duplicates: sort first, then skip duplicate elements at the same recursion depth.

BFS on an implicit graph: each word is a node, edges connect words differing by one character - BFS finds the shortest transformation sequence in O(n * L^2) time.

Depth-first graph traversal that explores one path completely before backtracking - recursive DFS for connected components and tree problems, backtracking DFS for generating all valid combinations.

Two-heap split: a max-heap for the lower half and a min-heap for the upper half give O(1) median access with O(log n) insertions.

O(1) average key-value lookup built on a hash function - the three patterns that cover most hash map interviews: complement lookup, frequency counting, and grouping by derived key.

Minimum jumps via level-by-level greedy: track the farthest reach within the current level, increment jumps when exhausting each level.

Monotonic increasing stack tracks candidate bars; each pop triggers an area calculation using the popped bar as the limiting height.

Find the length of the longest strictly increasing subsequence - O(n^2) DP where dp[i] = max(dp[j]+1) for all j < i with nums[j] < nums[i].

Variable minimum window: expand until all target characters are covered, then shrink from the left while still valid to find the smallest covering window.

Find cells reachable by both oceans using reverse multi-source BFS from each ocean's border, then intersect the two reachable sets

Binary search in a rotated array: determine which half is sorted, then decide which half must contain the target based on its value range.

Every element appears exactly 3 times except one - XOR alone fails here; count set bits at each position modulo 3 and reconstruct the answer from positions where the count is not divisible by 3.

Two pointers tracking the running max from each side: the shorter side's running max determines water at the current position; advance that pointer inward.

Min/max bounds propagation: pass allowed range down the recursion - going left tightens max, going right tightens min.

Find a word in a 2D character grid using DFS backtracking: mark cells visited in-place with a sentinel and restore them on return.

Find all target words on a character board by combining trie pruning with backtracking DFS - one pass checks all words simultaneously.

Breaking problems into overlapping subproblems and caching results - top-down memoization for natural recursion and bottom-up tabulation for space-efficient iteration.

Min-heap seeded with (nums1[i]+nums2[0], i, 0): expand by incrementing the second index to explore sorted pairs without generating all n*m candidates.

Circular route feasibility: if total gas >= total cost a solution exists, and the start is where the running tank sum hits its minimum.

Map digits to phone keypad letters and backtrack over all character choices per digit to enumerate every possible combination.

Find the length of the longest common subsequence of two strings - 2D DP where matching characters extend the diagonal, non-matching cells take the max of left and above.

BST property navigation: if both targets are less than root go left, if both are greater go right, otherwise root is the split point and is the LCA.

Reverse the 32 bits of an unsigned integer - extract the current LSB with n & 1, append it to the result by shifting result left and ORing, then shift n right; repeat 32 times.

Monotonic deque: maintain a decreasing-order deque of indices so the front is always the current window maximum in O(1) per step.

Hierarchical nodes with left/right children - the two traversal families (recursive DFS and level-order BFS) that unlock most binary tree interviews, plus the BST property for ordered queries.

Making the locally optimal choice at each step to reach a global optimum - interval scheduling by earliest deadline, activity selection, and the exchange argument that proves greedy correctness.

A complete binary tree with the heap property - O(log n) insert and extract, O(1) peek of the min or max, and the two patterns that cover most heap interviews: top-K elements and the two-heap split for running median.

Place n queens on an n x n board with no conflicts: backtrack row by row, pruning via column and diagonal sets.

Hash map complement lookup: for each element, check if its complement (target minus current) is already seen - O(n) time and space vs the O(n²) nested loop.

Determine if a string can be segmented into dictionary words - 1D DP where dp[i] is True if any dp[j] is True and s[j:i] is in the dictionary set.

Nodes connected by arbitrary edges - BFS for shortest path, DFS for connected components and cycle detection, and topological sort for dependency ordering.

Kadane's algorithm: at each element, decide whether to extend the running subarray or restart fresh - O(n) time with O(1) space by maintaining only two variables.

Arranging elements in order - merge sort for stable O(n log n), quicksort for in-place average O(n log n), and how to use Python's sort with custom keys to solve comparison problems without implementing a sort from scratch.

Systematic search that builds candidates incrementally and abandons a path the moment it cannot lead to a valid solution - choose, explore, unchoose is the three-step template for all backtracking problems.

Running minimum scan: track the cheapest price seen so far and the maximum profit achievable if you sold today - one pass, O(n) time and O(1) space.

A prefix tree where each path from root to a marked node spells a word - O(m) insert and search by word length, enabling prefix lookups and autocomplete that a hash set cannot do efficiently.

Operating directly on binary representations - XOR for cancellation, AND for masking, and the handful of tricks (power-of-2 check, lowest set bit, popcount) that cover most bit manipulation interview problems.

Prefix and suffix product passes: build left products left-to-right, then multiply in right products right-to-left - O(n) time and O(1) extra space without division.

A disjoint set data structure that tracks connected components in near-O(1) per operation - path compression and union by rank combine to give O(alpha(n)) amortized, faster than BFS/DFS for dynamic connectivity.

Opposite-ends two pointers: always move the shorter side inward - advancing the taller side can only decrease area, so the shorter side is the only move that could improve.

Three-pointer in-place reversal: save next_node before redirecting curr.next - that one save line is what keeps the rest of the list reachable throughout the traversal.

Dummy head pattern: a sentinel node gives curr a valid starting point so the first real node needs no special case - return dummy.next to skip the sentinel.

Floyd's cycle detection: slow moves one step, fast moves two - inside a cycle fast must eventually lap slow, so they collide; if fast reaches None, no cycle exists.

n-step head start: advance fast by n nodes first, then move both until fast reaches the tail - slow lands at the node just before the target, enabling O(1) deletion.

Fast/slow to find the midpoint, reverse the second half, compare both halves from their respective heads - O(n) time and O(1) space without extra storage.

Doubly linked list + hash map: the map gives O(1) lookup, the list gives O(1) eviction and promotion - always evict from the tail, always insert/promote to the head.

Stack-walk a bracket string to validate it, then localize the first error, then find the longest valid substring (LC 32).

A sampling profiler captures call stacks at fixed intervals. Convert those snapshots into start/end span events. Three phases - basic diff, recursion, then a min-consecutive-count debounce.