Interview Prep
A pattern-organized interview library: every problem is grouped by the algorithmic family it teaches (arrays & hashing, two pointers, sliding window, trees, graphs, DP, ...) and tagged with a difficulty tier — warm-up, standard, hard, or legendary. Every entry is solved in Python with the brute-force-then-optimal walkthrough you would actually deliver in a real interview. The goal is fluency, not memorisation.
Why Python: it has become the lingua franca for whiteboard interviews.
Dict and set literals are unbeatable for the patterns we need;
collections.Counter, heapq, and the slice
syntax let solutions compress to the algorithmic essentials without
Java-style ceremony.
The ML Engineering section at the bottom is the parallel track: stable softmax, gradients, attention, normalization, PCA — the numerical building blocks every ML candidate should be able to write from a cold start.
Have I Seen It? 4
A hash set or map answers "have I encountered X?" in O(1) during a single scan.
- Warm-up Contains Duplicate
Decide if any value appears at least twice. Hashset as a presence detector.
- Warm-up Longest Consecutive Sequence
Longest run of consecutive integers in an unsorted array in O(n). The "only start counting at sequence heads" trick.
- Warm-up Two Sum
Find indices of two numbers summing to a target. The "have I seen the complement?" pattern.
- Warm-up Valid Sudoku
Decide whether a partially filled Sudoku board violates any rule.
Canonical-Key Bucketing 2
Map each item to a canonical form, then group or compare by that key.
Count, Then Select 2
Tally frequencies first, then pull out the top or required few.
Prefix / Suffix Sweeps 2
Precompute running aggregates (prefix/suffix) so each query is O(1).
- Warm-up Product of Array Except Self
Compute "product of all other elements" without division and in O(n).
- Hard Shortest Subarray with Sum ≥ K also: Monotonic Stack / Deque
Shortest contiguous subarray with sum ≥ K, allowing negative numbers. Monotonic deque on prefix-sum indices — sliding window fails because of the negatives.
Running Extreme (the Fold) 5
Carry a running best as you scan; the answer is one fold over the input.
- Warm-up Best Time to Buy and Sell Stock
Maximize profit from one buy-then-sell. Single pass with a running minimum.
- Warm-up Kadane's Algorithm with Indices
Return the indices of the max subarray, not just the sum. Track start/end alongside the running current sum; reset start on restart.
- Warm-up Maximum Subarray also: 1-D Linear DP
Find the contiguous subarray with the largest sum. Kadane's algorithm in 4 lines.
- Standard Maximum Product Subarray
Track both min AND max running products. A large negative times another negative becomes a large positive — the min can flip the result.
- Standard Maximum Subarray (Circular)
Allow the subarray to wrap around the end. Trick: max(Kadane on array, total − Kadane on negated array). Edge case: all-negative.
Converging Pointers 3
Two indices walk inward on a sorted shape — advance whichever one limits the answer.
- Warm-up Container With Most Water
Find two lines that form the container holding the most water. Two-pointer convergence on a sorted-shape argument.
- Standard 3Sum
Find all unique triples that sum to zero. Sort + two-pointer extension of Two Sum.
- Hard Trapping Rain Water also: Monotonic Stack / Deque
Total water trapped between elevation bars. Famous for having five elegant solutions.
Variable Window 1
Grow and shrink a window over the array to keep an invariant true.
Stack as LIFO Matcher 1
Push openers, pop on close — the stack tracks the most-recent unmatched item.
Monotonic Stack / Deque 5
Keep a monotonic stack/deque so range extremes and nearest-greater queries stay amortized O(1).
- Hard Largest Rectangle in Histogram
Largest axis-aligned rectangle under a histogram in O(n). The reference monotonic-stack problem.
- Hard Shortest Subarray with Sum ≥ K also: Prefix / Suffix Sweeps
Shortest contiguous subarray with sum ≥ K, allowing negative numbers. Monotonic deque on prefix-sum indices — sliding window fails because of the negatives.
- Hard Sliding Window Maximum
Maximum of every length-k window in an array. The monotonic-deque pattern.
- Hard Sliding Window Minimum
Minimum of every length-k window. Identical to Sliding Window Maximum with the comparison flipped — but several other DP problems reduce to it.
- Hard Trapping Rain Water also: Converging Pointers
Total water trapped between elevation bars. Famous for having five elegant solutions.
Binary Search on an Invariant 2
Halve the space using a monotone predicate, even when the array is not plainly sorted.
Post-Order: Return One, Track Another 6
Bubble one value up the recursion while updating a separate global answer.
- Warm-up Balanced Binary Tree
Decide whether |depth(left) − depth(right)| ≤ 1 at every node. Single post-order; propagate −1 upward as soon as imbalance is detected.
- Warm-up Maximum Depth of Binary Tree
Compute the maximum depth of a binary tree. Recursive tree fundamentals.
- Warm-up Minimum Depth of Binary Tree
Minimum root-to-leaf depth. The "one missing child" trap — min(depth(left), depth(right)) silently returns 0 when one side is empty.
- Standard Diameter of Binary Tree
Longest path between any two nodes. At each node, the through-path is depth(left) + depth(right); compute both in one post-order traversal.
- Standard Lowest Common Ancestor of a Binary Tree
Find the deepest node that has both p and q in its subtree. Elegant 5-line recursion once you see it.
- Hard Binary Tree Maximum Path Sum
Maximum sum of any path (need not pass through root). The "return one, track another" tree-DP pattern.
In-Order = Sorted 3
A BST's in-order traversal emits values in sorted order — exploit the ordering.
- Standard Kth Smallest Element in a BST
In-order traversal of a BST yields values in sorted order. Stop on the k-th visit. O(h + k).
- Standard Validate Binary Search Tree also: Bounds-Passing Recursion
Decide whether a binary tree is a valid BST. The classic "recursion with bounds" pattern.
- Hard Recover Binary Search Tree
Two BST nodes have been swapped. Restore the BST by swapping their values. In-order traversal finds the two out-of-order points.
Bounds-Passing Recursion 2
Thread a min/max (or range) down the recursion to validate or prune subtrees.
- Standard Range Sum / Count in a BST
Sum (or count) the values in [L, R] in a BST. Bounds-pruning recursion — skip whole subtrees that fall outside the range.
- Standard Validate Binary Search Tree also: In-Order = Sorted
Decide whether a binary tree is a valid BST. The classic "recursion with bounds" pattern.
Heap for Top-K & Streams 4
A size-k heap (or two balanced heaps) keeps order without sorting everything.
- Warm-up Top K Frequent Elements also: Count, Then Select
Return the K most frequent values without sorting everything.
- Standard Kth Largest Element
Find the k-th largest in O(n) average with quickselect, or O(n log k) with a min-heap. Two solutions worth knowing.
- Hard Find Median from Data Stream also: Build the Data Structure
Support add(x) and findMedian() on a growing stream. Two heaps split below/above the median.
- Hard Merge K Sorted Lists
Merge k sorted linked lists into one sorted list. Min-heap of heads.
Backtracking Template 4
Choose, recurse, un-choose — enumerate a decision tree with explicit undo.
- Warm-up Generate Parentheses
Generate all well-formed parenthesis strings of length 2n. The canonical "count remaining" backtracking.
- Standard Permutations
Generate all n! permutations of an array. Backtracking with a "used" set; sibling of Subsets.
- Standard Subsets (Backtracking)
Generate all 2^n subsets of an array. The reference template for every backtracking problem.
- Standard Word Search (Grid Backtracking) also: Grid DFS / Flood Fill
Decide whether a word can be spelled by a path through neighboring cells. DFS with mark-and-unmark backtracking.
Grid DFS / Flood Fill 2
Walk a grid as an implicit graph, marking cells visited as you go.
BFS, Layer by Layer 3
Breadth-first expansion: shortest unweighted paths and level-order traversal.
- Standard Binary Tree Level Order Traversal
Return the values of a binary tree level by level. The canonical BFS-on-a-tree problem.
- Hard Word Ladder
Find the shortest transformation sequence between two words via one-letter swaps. BFS on an implicit graph.
- Legendary Serialize and Deserialize Binary Tree also: Build the Data Structure
Encode a binary tree to a string and decode it back. Demonstrates traversal + parsing in one problem.
Topological Order 1
Order a DAG by dependencies — and catch cycles while you do it.
1-D Linear DP 3
Each state depends on the previous one or two — a Fibonacci-shaped recurrence.
- Warm-up Climbing Stairs
Count ways to climb n stairs taking 1 or 2 at a time. The simplest non-trivial DP.
- Warm-up House Robber
Max non-adjacent subarray sum. The simplest linear DP after Fibonacci.
- Warm-up Maximum Subarray also: Running Extreme (the Fold)
Find the contiguous subarray with the largest sum. Kadane's algorithm in 4 lines.
2-D String DP 4
Fill a table indexed by prefixes of two strings, or by substring ranges.
- Standard Word Break
Decide whether a string can be segmented into a sequence of dictionary words. DP over prefix lengths.
- Hard Edit Distance
Minimum edits to turn one string into another. The textbook 2D DP.
- Hard Longest Palindromic Substring
Find the longest palindrome substring. Center-expansion in O(n²); Manacher in O(n).
- Legendary Regular Expression Matching
Implement regex matching with . and *. 2D DP that everyone gets wrong on the first try.
Knapsack DP 1
Build up the set of reachable totals from repeated item choices.
Sort, Then Sweep 1
Sort by a key, then a single linear pass merges or decides.
Pointer Surgery 4
Rewire linked-list pointers in place, usually behind a dummy head.
- Warm-up Merge Two Sorted Lists
Merge two sorted linked lists into one sorted list. The dummy-node pattern.
- Warm-up Reverse Linked List
Reverse a singly linked list in place. The pointer-juggling primitive.
- Standard Sort a Linked List (Merge Sort)
Sort a singly linked list in O(n log n). Merge sort is the natural fit — splitting and merging are both cheap on linked lists.
- Legendary LRU Cache also: Build the Data Structure
O(1) get and put for a fixed-size cache. Build the doubly-linked-list-plus-hashmap from scratch.
Build the Data Structure 5
Compose primitives — hashmap, list, heap — into a custom O(1) structure.
- Warm-up Implement Trie (Prefix Tree)
Build a trie with insert, search, and startsWith. The fundamental string-indexed dictionary.
- Warm-up Min Stack
A stack supporting push, pop, top, and getMin all in O(1). The auxiliary-stack trick.
- Hard Find Median from Data Stream also: Heap for Top-K & Streams
Support add(x) and findMedian() on a growing stream. Two heaps split below/above the median.
- Legendary LRU Cache also: Pointer Surgery
O(1) get and put for a fixed-size cache. Build the doubly-linked-list-plus-hashmap from scratch.
- Legendary Serialize and Deserialize Binary Tree also: BFS, Layer by Layer
Encode a binary tree to a string and decode it back. Demonstrates traversal + parsing in one problem.
Numerical Stability 3
Reformulate to dodge overflow and cancellation: log-sum-exp, Welford, fused softmax.
- Warm-up Cross-Entropy + Softmax Gradient also: Backprop by Hand
Derive the famous (p − y) gradient of softmax + cross-entropy and explain why fusing them is critical for numerical stability.
- Warm-up Online Mean and Variance (Welford) also: Streaming / Online
Compute running mean and variance in one pass without numerical instability. The Welford recurrence.
- Warm-up Stable Softmax
Implement softmax without overflowing on large logits. The log-sum-exp trick.
Backprop by Hand 7
Forward pass, then the gradient by hand, term by term.
- Warm-up Cross-Entropy + Softmax Gradient also: Numerical Stability
Derive the famous (p − y) gradient of softmax + cross-entropy and explain why fusing them is critical for numerical stability.
- Warm-up Sigmoid and Its Gradient
Implement the sigmoid, compute its derivative, and explain why σ(x)(1−σ(x)) makes backprop cheap.
- Standard Backprop a 2-Layer MLP
Forward + backward pass on a 2-layer MLP by hand. The autograd primitive every ML candidate should be able to write from scratch.
- Standard Dropout From Scratch
Implement inverted dropout (forward + backward) and explain why the scale factor lives in training, not inference.
- Standard Layer Normalization also: Transformer Components
Implement layer norm (forward + backward) and explain how it differs from batch norm. Foundational transformer component.
- Hard Attention From Scratch also: Transformer Components
Implement scaled dot-product attention and a single-head self-attention block. The transformer's load-bearing primitive.
- Hard Multi-Head Attention also: Transformer Components
Extend single-head attention to multi-head with split/concat. The complete transformer attention block.
Streaming / Online 2
One pass over an unbounded stream with O(1) state.
Transformer Components 3
The load-bearing blocks of attention-based models.
- Standard Layer Normalization also: Backprop by Hand
Implement layer norm (forward + backward) and explain how it differs from batch norm. Foundational transformer component.
- Hard Attention From Scratch also: Backprop by Hand
Implement scaled dot-product attention and a single-head self-attention block. The transformer's load-bearing primitive.
- Hard Multi-Head Attention also: Backprop by Hand
Extend single-head attention to multi-head with split/concat. The complete transformer attention block.
Classic ML From Scratch 2
End-to-end classical algorithms in pure NumPy.
Arrays & Hashing
Indexing and presence checks. Hashmaps and sets as the "have I seen this before?" primitive.
- Warm-up Contains Duplicate arrayshashset
Decide if any value appears at least twice. Hashset as a presence detector.
- Warm-up Group Anagrams stringshashmap
Partition a list of strings into anagram buckets.
- Warm-up Longest Consecutive Sequence arrayshashset
Longest run of consecutive integers in an unsorted array in O(n). The "only start counting at sequence heads" trick.
- Warm-up Product of Array Except Self arraysprefix-products
Compute "product of all other elements" without division and in O(n).
- Warm-up Top K Frequent Elements heaphashmap
Return the K most frequent values without sorting everything.
- Warm-up Two Sum arrayshashmap
Find indices of two numbers summing to a target. The "have I seen the complement?" pattern.
- Warm-up Valid Anagram stringscounting
Decide if two strings are permutations of each other.
- Warm-up Valid Sudoku matrixhashset
Decide whether a partially filled Sudoku board violates any rule.
Two Pointers
Two indices sweeping a sorted (or sortable) array — opposite ends, fast/slow, or partition style.
- Warm-up Container With Most Water arraystwo-pointers
Find two lines that form the container holding the most water. Two-pointer convergence on a sorted-shape argument.
- Standard 3Sum arraystwo-pointerssorting
Find all unique triples that sum to zero. Sort + two-pointer extension of Two Sum.
- Hard Trapping Rain Water arraystwo-pointers
Total water trapped between elevation bars. Famous for having five elegant solutions.
Sliding Window
A moving window over an array or string, expanding and contracting to maintain an invariant.
- Warm-up Best Time to Buy and Sell Stock arraysone-pass
Maximize profit from one buy-then-sell. Single pass with a running minimum.
- Standard Longest Substring Without Repeating Characters stringssliding-window
The canonical sliding-window problem. Maintain a moving window of distinct chars.
- Hard Sliding Window Maximum arraysmonotonic-deque
Maximum of every length-k window in an array. The monotonic-deque pattern.
- ↳ Hard Shortest Subarray with Sum ≥ K Shortest contiguous subarray with sum ≥ K, allowing negative numbers. Monotonic deque on prefix-sum indices — sliding window fails because of the negatives.
- ↳ Hard Sliding Window Minimum Minimum of every length-k window. Identical to Sliding Window Maximum with the comparison flipped — but several other DP problems reduce to it.
Stack
LIFO bookkeeping. Matching, monotonic stacks, and "nearest greater/smaller" patterns.
- Warm-up Min Stack stackdesign
A stack supporting push, pop, top, and getMin all in O(1). The auxiliary-stack trick.
- Warm-up Valid Parentheses stackstrings
Decide whether a string of brackets is properly nested. The canonical stack problem.
- Hard Largest Rectangle in Histogram stackmonotonic-stack
Largest axis-aligned rectangle under a histogram in O(n). The reference monotonic-stack problem.
Binary Search
Halving the search space on a sorted (or monotone-predicate) input. The most over-rated and under-mastered primitive.
- Standard Search in Rotated Sorted Array binary-searchinvariants
Find a target in a sorted array that has been rotated by an unknown amount. Modified binary search.
- Legendary Median of Two Sorted Arrays binary-searchinvariants
Find the median of two sorted arrays in O(log min(m, n)). The famous "I can’t do this on the whiteboard" Google problem.
Linked List
Pointer juggling with dummy heads, fast/slow runners, and in-place reversal.
- Warm-up Merge Two Sorted Lists linked-listpointers
Merge two sorted linked lists into one sorted list. The dummy-node pattern.
- Warm-up Reverse Linked List linked-listpointers
Reverse a singly linked list in place. The pointer-juggling primitive.
- Hard Merge K Sorted Lists heaplinked-list
Merge k sorted linked lists into one sorted list. Min-heap of heads.
- Legendary LRU Cache designlinked-listhashmap
O(1) get and put for a fixed-size cache. Build the doubly-linked-list-plus-hashmap from scratch.
Trees
Recursion on binary trees — pre/in/post order, BFS, recursion with bounds, tree DP.
- Warm-up Maximum Depth of Binary Tree treesrecursion
Compute the maximum depth of a binary tree. Recursive tree fundamentals.
- ↳ Warm-up Balanced Binary Tree Decide whether |depth(left) − depth(right)| ≤ 1 at every node. Single post-order; propagate −1 upward as soon as imbalance is detected.
- ↳ Warm-up Minimum Depth of Binary Tree Minimum root-to-leaf depth. The "one missing child" trap — min(depth(left), depth(right)) silently returns 0 when one side is empty.
- ↳ Standard Diameter of Binary Tree Longest path between any two nodes. At each node, the through-path is depth(left) + depth(right); compute both in one post-order traversal.
- Standard Binary Tree Level Order Traversal treesbfs
Return the values of a binary tree level by level. The canonical BFS-on-a-tree problem.
- Standard Lowest Common Ancestor of a Binary Tree treesrecursion
Find the deepest node that has both p and q in its subtree. Elegant 5-line recursion once you see it.
- Standard Validate Binary Search Tree treesrecursioninvariants
Decide whether a binary tree is a valid BST. The classic "recursion with bounds" pattern.
- ↳ Standard Kth Smallest Element in a BST In-order traversal of a BST yields values in sorted order. Stop on the k-th visit. O(h + k).
- ↳ Standard Range Sum / Count in a BST Sum (or count) the values in [L, R] in a BST. Bounds-pruning recursion — skip whole subtrees that fall outside the range.
- ↳ Hard Recover Binary Search Tree Two BST nodes have been swapped. Restore the BST by swapping their values. In-order traversal finds the two out-of-order points.
- Hard Binary Tree Maximum Path Sum treesdp
Maximum sum of any path (need not pass through root). The "return one, track another" tree-DP pattern.
- Legendary Serialize and Deserialize Binary Tree treesdesigntraversal
Encode a binary tree to a string and decode it back. Demonstrates traversal + parsing in one problem.
Trie
Prefix-indexed dictionaries. The right structure when "all words starting with..." is the bottleneck.
Heap / Priority Queue
Top-k, k-way merges, streaming medians. Min/max-heap as the streaming-priority primitive.
- Standard Kth Largest Element heapquickselect
Find the k-th largest in O(n) average with quickselect, or O(n log k) with a min-heap. Two solutions worth knowing.
- Hard Find Median from Data Stream heapdesignstreaming
Support add(x) and findMedian() on a growing stream. Two heaps split below/above the median.
Backtracking
Decision trees explored by depth-first search with explicit undo. Subsets, permutations, constraint satisfaction.
- Warm-up Generate Parentheses backtrackingrecursion
Generate all well-formed parenthesis strings of length 2n. The canonical "count remaining" backtracking.
- Standard Permutations backtrackingrecursion
Generate all n! permutations of an array. Backtracking with a "used" set; sibling of Subsets.
- Standard Subsets (Backtracking) backtrackingrecursion
Generate all 2^n subsets of an array. The reference template for every backtracking problem.
- Standard Word Search (Grid Backtracking) backtrackinggriddfs
Decide whether a word can be spelled by a path through neighboring cells. DFS with mark-and-unmark backtracking.
Graphs
BFS/DFS on grids and graphs, topological sort, shortest paths.
- Standard Course Schedule graphstopological-sortcycle-detection
Decide if all courses can be completed given prerequisites. Topological sort with cycle check.
- Standard Number of Islands graphsdfsgrid
Count connected components of land cells in a grid. Grid-DFS in its purest form.
- Hard Word Ladder graphsbfsshortest-path
Find the shortest transformation sequence between two words via one-letter swaps. BFS on an implicit graph.
Dynamic Programming
Optimal substructure. From linear recurrences (Fibonacci-shaped) up to 2D table DPs on strings.
- Warm-up Climbing Stairs dpfibonacci
Count ways to climb n stairs taking 1 or 2 at a time. The simplest non-trivial DP.
- Warm-up House Robber dprecurrence
Max non-adjacent subarray sum. The simplest linear DP after Fibonacci.
- Warm-up Maximum Subarray arraysdpkadane
Find the contiguous subarray with the largest sum. Kadane's algorithm in 4 lines.
- ↳ Warm-up Kadane's Algorithm with Indices Return the indices of the max subarray, not just the sum. Track start/end alongside the running current sum; reset start on restart.
- ↳ Standard Maximum Product Subarray Track both min AND max running products. A large negative times another negative becomes a large positive — the min can flip the result.
- ↳ Standard Maximum Subarray (Circular) Allow the subarray to wrap around the end. Trick: max(Kadane on array, total − Kadane on negated array). Edge case: all-negative.
- Standard Coin Change dpunbounded-knapsack
Minimum coins to make a target amount. Greedy fails; DP nails it.
- Standard Word Break dpstrings
Decide whether a string can be segmented into a sequence of dictionary words. DP over prefix lengths.
- Hard Edit Distance dpstrings
Minimum edits to turn one string into another. The textbook 2D DP.
- Hard Longest Palindromic Substring stringsdp
Find the longest palindrome substring. Center-expansion in O(n²); Manacher in O(n).
- Legendary Regular Expression Matching dpstrings
Implement regex matching with . and *. 2D DP that everyone gets wrong on the first try.
Intervals
Sort by start, sweep, merge. The intervals canon.
ML Engineering
Numerical building blocks every ML engineer should be able to write: softmax, gradients, attention, normalization, PCA, sampling.
- Warm-up Cross-Entropy + Softmax Gradient mlderivativesnumerics
Derive the famous (p − y) gradient of softmax + cross-entropy and explain why fusing them is critical for numerical stability.
- Warm-up Online Mean and Variance (Welford) mlstreamingnumerics
Compute running mean and variance in one pass without numerical instability. The Welford recurrence.
- Warm-up Reservoir Sampling mlstreamingprobability
Sample k items uniformly from a stream of unknown length. Foundational streaming ML.
- Warm-up Sigmoid and Its Gradient mlderivatives
Implement the sigmoid, compute its derivative, and explain why σ(x)(1−σ(x)) makes backprop cheap.
- Warm-up Stable Softmax mlnumerics
Implement softmax without overflowing on large logits. The log-sum-exp trick.
- Standard Backprop a 2-Layer MLP mlautogradnumpy
Forward + backward pass on a 2-layer MLP by hand. The autograd primitive every ML candidate should be able to write from scratch.
- Standard Dropout From Scratch mlregularizationnumpy
Implement inverted dropout (forward + backward) and explain why the scale factor lives in training, not inference.
- Standard K-Means From Scratch mlclusteringnumpy
Implement Lloyd's algorithm in pure NumPy. The unsupervised baseline.
- Standard Layer Normalization mlnumpytransformer
Implement layer norm (forward + backward) and explain how it differs from batch norm. Foundational transformer component.
- Hard Attention From Scratch mltransformernumpy
Implement scaled dot-product attention and a single-head self-attention block. The transformer's load-bearing primitive.
- Hard Multi-Head Attention mltransformernumpy
Extend single-head attention to multi-head with split/concat. The complete transformer attention block.
- Legendary PCA From Scratch mllinear-algebranumpy
Implement PCA via SVD: center, decompose, project. The dimensionality-reduction primitive every ML engineer must know.