Coding & DSA

A favorite practical screen at the labs, because it tests concurrency, time handling, and judgment in 20 lines. The trap is the background thread that wastes CPU. Here is the lazy-refill version interviewers want, plus the follow-ups.

A staple ML-coding screen. Writing the loop is easy; the signal is k-means++ init, a real convergence criterion, and knowing the failure modes. Here is the tight implementation plus the follow-ups interviewers always ask.

A deceptively simple ML-coding ask. Anyone can write exp/sum; the signal is the max-subtraction trick and the log-sum-exp form that keep it from overflowing. Here is the stable implementation and why the naive one breaks.

Hashmap for lookup, doubly linked list for recency, move-to-front on access, evict at the tail. Then the usual follow-ups: TTL and thread safety.

A classic that rewards the two-heap insight. A sorted list gives O(n) inserts; two balanced heaps give O(log n) insert and O(1) median. Here is the implementation and the rebalancing detail people get wrong.

The from-scratch implementation that frontier labs and NVIDIA actually ask. Writing it proves you understand shapes, the scale, the causal mask, and how heads split and recombine. Here is a correct, readable implementation and the follow-ups.

Beam search is the decoding algorithm everyone references and few can implement correctly. The signal is keeping k hypotheses by cumulative log-prob, summing logs (not multiplying probs), and handling completed sequences and length. Here is a correct implementation and the tradeoffs.

A from-scratch ML-coding staple that checks whether you actually know the math you use. The signal is the clean gradient (it simplifies to Xᵀ(ŷ - y)/n), numerical stability, and vectorization. Here is the implementation and the details interviewers push on.

Autocomplete is the canonical trie question, and it tests whether you reach for the right structure instead of scanning a word list. The signal is O(prefix) lookup, the DFS to collect completions, and the follow-ups (ranking, memory). Here is the build.

The core operation under every embedding/RAG retrieval, asked as a coding exercise. The signal is vectorizing the similarity, normalizing correctly, and using a partial selection (argpartition) instead of a full sort. Here is the efficient implementation and the scaling follow-up.

A classic that tests whether you reach past sorting for the right structure. The signal is the heap solution (O(n log k)), the bucket-sort O(n) trick, and how it changes for an unbounded stream. Here is the answer.

Sliding window is one of the highest-yield coding patterns, and this is its canonical problem. The real signal is recognizing when a window collapses an O(n squared) scan into one linear pass, and maintaining the invariant cleanly.

Graph traversal underpins a huge class of interview problems. The signal is knowing the BFS-vs-DFS tradeoff (shortest path vs memory shape) and applying it cleanly, then handling the directed-vs-undirected cycle gotcha most candidates miss.

DP feels like pattern-matching magic until you have a method. The signal is a repeatable drill: spot overlapping subproblems and optimal substructure, define the state and recurrence, then memoize or tabulate. Here is that method on a worked example.

A common ML-coding check that verifies you actually understand the metrics you quote. The signal is getting TP/FP/FN/TN right and knowing macro vs micro averaging for multiclass, not reaching for sklearn.

Data loading is where training pipelines silently bottleneck. The signal is a correct shuffle-then-batch iterator plus knowing why prefetching and parallel loading keep the GPU fed.

BPE is the tokenizer behind GPT-style models, and implementing it proves you understand how subword vocabularies are built, not just that they exist. The signal is the iterative merge of the most frequent adjacent pair.

Interval merging is a classic that tests the sort-then-sweep insight. The signal is sorting by start, then merging in one pass, O(n log n). Here is the pattern and the family of problems it unlocks.

k-NN is simple to write and a good test of vectorization and the lazy-learner tradeoff. The signal is a clean vectorized distance computation and knowing why naive prediction is O(n) and how to speed it. Here is the implementation.

Implementing conv2d proves you understand what a CNN layer actually computes, not just that you can name it. The signal is correct output-shape math, clean stride/padding handling, and knowing the im2col trick frameworks really use.

LayerNorm sits in every transformer, and implementing it checks that you know what it normalizes over and why. The signal is normalizing across the feature dimension per token, the learnable scale/shift, and the RMSNorm simplification modern LLMs adopted.

Implementing the KV cache proves you understand why decode is efficient: you append the new token's K/V and reuse the rest instead of recomputing. The signal is the append-and-attend-over-cache logic. Here is the implementation.

Binary search is easy to describe and famously easy to get wrong (off-by-one, infinite loops). The signal is a correct template plus the variants (boundaries, rotated arrays) that come up constantly. Here is the answer.

Backtracking is the pattern behind permutations, subsets, N-queens, and constraint problems. The signal is the choose/explore/un-choose template plus pruning, and knowing exactly which knob separates permutations from combinations.

A warm-up that screens for the stack instinct. The signal is recognizing last-opened-first-closed maps to a stack, and handling the edge cases (leftover opens, early close). Here is the pattern.

Merging k sorted sources is the canonical min-heap problem and a real data-engineering pattern (merging sorted shards/streams). The signal is the heap of k heads giving O(N log k). Here is the answer.

A classic that rewards the two-pointer insight over brute force. The signal is realizing water at each position is bounded by the min of the max walls on each side, then computing it in one pass. Here is the answer.

Implementing BatchNorm checks that you know the train/inference difference, the part everyone forgets. The signal is normalizing over the batch with running stats maintained for inference. Here is the implementation.

The canonical warm-up that screens for the hash-map instinct: trade space for time to turn O(n squared) into O(n). The signal is the one-pass complement lookup. Here is the pattern.

Topological sort orders a DAG so dependencies come first, the backbone of build systems, schedulers, and ML/data pipeline DAGs. The signal is Kahn's algorithm (or DFS) plus cycle detection. Here is the answer.

Union-Find answers 'are these in the same group?' near-instantly and powers connected-components, cycle detection, and clustering. The signal is path compression plus union by rank for near-O(1) operations. Here is the answer.

A grid-traversal classic that tests BFS/DFS flood fill and the visited-marking discipline. The signal is treating the grid as a graph and counting connected components. Here is the answer.

Edit distance is the canonical 2D string DP, behind spell-check, diff, and fuzzy matching. The signal is defining the subproblem and the insert/delete/replace recurrence. Here is the answer.

Sampling uniformly from a stream you cannot fit in memory (or whose length you never learn) is a real data-engineering problem. The signal is the replace-with-decreasing-probability trick and a proof that telescopes. Here is the answer.

Reversing a linked list is the canonical pointer-handling screen. The signal is the three-pointer walk done without ever losing the rest of the list, plus knowing why the iterative version beats recursion in production. Here is the answer.

Encoding a tree into a string and rebuilding it exactly hinges on one decision most candidates skip. Miss it and the structure becomes ambiguous. Here is the answer and the interview-grade reasoning.

LCA is the recursion classic that tests how you propagate information up from subtrees in a single pass. The signal is the post-order 'found in left, found in right' logic. Here is the answer plus the BST shortcut.

Maximum subarray is the gateway 1D DP problem, and Kadane's is the O(n) one-liner. The signal is the 'extend or restart' decision at each element and the all-negative edge case most people botch. Here is the answer.

Word Break is the classic 1D string DP that trips people who reach for greedy or naive recursion. The signal is the dp[i] = 'is the prefix of length i segmentable' recurrence, plus why a locally valid split can doom the rest. Here is the answer.

Rotating a matrix in place tests index manipulation and the transpose-then-reverse trick. The signal is decomposing the rotation into two simple passes rather than juggling four-way swaps. Here is the answer.

Bit-manipulation problems screen for comfort with binary and the O(1)-space tricks most candidates fumble. The tell is whether you reach for XOR's self-canceling property and the n & (n-1) idiom on instinct. Here is the toolkit.

K-th largest has three textbook solutions, and the signal is knowing Quickselect's average O(n) beats sorting's O(n log n), why its worst case is O(n²), and when a heap is actually the better call. Here is the answer.

TF-IDF is the classic text-vectorization scheme and a fast check of whether you actually understand term-frequency times inverse-document-frequency, or just recite it. The signal is explaining why IDF kills common words. Here is the implementation.

The DP that exposes why greedy quietly breaks on non-standard denominations, and how one bottom-up table fixes it. The signal interviewers want is the dp[amount] recurrence and the unbounded-reuse insight.

LCS is the template 2D-sequence DP behind diff tools and bioinformatics. The signal is reconstructing the match/mismatch recurrence cold and not confusing subsequence (gaps allowed) with substring (contiguous). Here is the answer.

Gas Station rewards spotting a greedy invariant that turns O(n²) into O(n). Two facts carry the whole solution: total feasibility, and that a failed prefix lets you skip every start inside it.

Jump Game rewards spotting that a greedy reachability scan beats DP. The signal is tracking the farthest reachable index in one pass, and detecting the exact moment you fall behind it.

LIS has an obvious O(n²) DP and a clever O(n log n) solution that surprises people. The signal is the patience-sorting/binary-search approach maintaining 'tails'. Here is both.

Minimum Window Substring is the hard sliding-window problem that tests expand-and-contract with a character-count map. The signal is the grow-to-valid then shrink-to-minimal pattern, checked in O(1) per step.

House Robber is the cleanest choose-with-a-constraint 1D DP, and it collapses to O(1) space. The signal is the take-this-or-skip recurrence and the two-variable rolling optimization.

Group Anagrams tests the 'compute a canonical key and bucket by it' pattern. The signal is choosing a key that anagrams share without comparing every pair. Here is the answer.

Building a PR/ROC curve from scratch proves you understand thresholds and the precision/recall tradeoff. The real signal is sweeping the threshold in one sorted pass and integrating the area. Here is the implementation.

This problem bans the obvious division trick, forcing the prefix/suffix-product insight. The signal is computing left and right products in two passes with O(1) extra space. Here is the answer.

Sorting an array of three values in one pass tests the three-pointer partition (Dutch National Flag). The signal is the low/mid/high invariant and knowing when not to advance mid. Here is the answer.

Spiral traversal tests careful boundary management more than algorithmic insight. The signal is shrinking four boundaries layer by layer without double-visiting a row or column. Here is the answer.

The canonical grid DP where each cell depends on three neighbors at once. The signal interviewers want is the min-of-three recurrence, and the reason it has to be min. Here is the answer.

This famously-hard problem wants better than the O(m+n) merge: an O(log) binary search on the partition. The signal is binary-searching the split point so the left halves stay below the right halves. Here is the answer.

Decode Ways is a 1D DP whose difficulty lives entirely in the edge cases: zeros and the valid 1-26 range. The signal is the take-one-digit-or-two recurrence plus disciplined validity checks. Here is the answer.

This classic has a clean O(n^2) expand-around-center solution that beats the naive O(n^3). The signal is expanding from every center and handling odd and even lengths separately. Here is the answer.

Implementing Adam proves you understand what's happening under .step(): momentum plus per-parameter adaptive rates with bias correction. The signal is the two moments and the bias-correction step.

Single-head attention is common; multi-head adds the split-into-heads, attend-per-head, concatenate structure. The signal is the reshape into heads and a clear reason why multiple heads help. Here is the implementation.

Finding the max of every window of size k naively is O(n*k). The trick that drops it to O(n) is a monotonic deque of indices, and the reason it stays linear surprises most candidates.

The minimum number of meeting rooms equals the peak number of meetings running at once. The reframing is the whole interview; two O(n log n) solutions fall out of it, and the tie-handling trips up the careless.

This problem rewards knowing that an in-order traversal of a BST yields sorted order. The signal is stopping early at the kth element rather than traversing the whole tree.

A row- and column-sorted matrix rewards one observation: start from a corner and kill an entire row or column each step. That turns an O(m*n) scan into O(m+n), and the choice of corner is not arbitrary.

Dropout is five lines, yet most candidates botch two of them: disabling it at inference and scaling the survivors so the expected activation stays constant. Inverted dropout is the convention they want to see.

Finding the longest run of consecutive integers without sorting separates candidates who reach for O(n log n) from those who see the hash-set trick. The signal is one loop invariant that kills redundant work. Here is the answer.

Validating a BST catches people who only check parent-child pairs and miss violations buried deep in a subtree. The signal is propagating min/max bounds or using in-order monotonicity. Here is the answer.

Course Schedule reduces to one question: is the prerequisite graph a DAG? The signal is spotting the graph framing and using topological sort or DFS to detect a cycle. Here is the answer.

Comparing every pair of a million documents is a trillion comparisons. MinHash estimates Jaccard similarity from a tiny signature, and LSH turns dedup into a near-linear scan. Here is the implementation.

Every chat model's 'temperature' and 'top_p' knobs are a few lines of logit surgery. Implementing them shows you understand decoding, not just call it. Here is the from-scratch version.

RoPE is why modern LLMs extrapolate to longer contexts, and it's a rotation, not an addition. Coding it shows you actually understand how position enters attention. Here is the implementation.

A wrong split quietly inflates every metric you'll ever report, and the bugs are subtle: leaked groups, shuffled time, preprocessing fit on everything. Here is the split done right.

Many state-of-the-art training runs keep a shadow copy of the weights that's a moving average of the trajectory, and serve that instead of the final step. It's a few lines and a real accuracy boost. Here it is.

Almost every modern training run uses warmup-then-cosine, and getting it wrong destabilizes early training or wastes the tail. It's a closed-form function of the step. Here is the implementation and the why.

Before transformers, this was the language model, and it is still the cleanest way to show you understand what perplexity actually measures. Smoothing is the part people get wrong. Here is the implementation.

The textbook variance formula loses catastrophic precision on streaming data and cannot update incrementally. Welford's one-pass update is the standard for online feature normalization. Here it is.

Negative sampling in word2vec and recommendation draws millions of weighted samples; doing each in O(log n) is a bottleneck. The alias method makes each draw O(1) after an O(n) setup. Here it is.

When you shard a vector index or route requests across model replicas, naive 'hash mod N' reshuffles everything when N changes. Consistent hashing moves only a small fraction. Here is the implementation.

A Bloom filter answers 'have I seen this?' using a few bits per item instead of storing the key, trading a rare false positive for a huge memory win. Here is the build, the sizing math, and where it pays off in dedup and serving.

Floyd's tortoise and hare detects a cycle in O(1) space, but the part that separates strong candidates is the second phase: a short distance argument that pinpoints exactly where the loop begins. Here is the answer and the math.

Two lists that share a tail must intersect at a single node, but matching their lengths without counting is the elegant move interviewers want. Here is the two-pointer trick that makes the lengths cancel out, plus the answer.

The two-pass length-then-delete solution works, but the interview wants a single pass: a gap of N between two pointers, plus a dummy head that makes deleting the real head fall out for free. Here is the clean answer.

The diameter is not the tree's height, and the path need not pass through the root. The clean solution computes height and best path in one DFS, updating a global max at every node. Here is the answer and the subtlety candidates miss.

Preorder names the root; inorder splits the rest into left and right subtrees. Doing it naively is O(n squared); the strong answer uses a value-to-index map and a moving preorder pointer for O(n). Here is the answer and why both orders are required.

Negative subtrees, a path that bends through any node, and a return value that differs from the answer you track: this problem packs three traps into one DFS. Here is the clean O(n) solution and the reasoning that survives follow-ups.

The brute force is O(n squared) nested scans. A monotonic stack does it in one O(n) pass by keeping only the candidates that can still be a future answer. Here is the pattern and why each element is pushed and popped exactly once.

The naive triple loop is O(n cubed). Sort first, then fix one element and converge two pointers for O(n squared). The real test is deduplication: returning unique triplets without a set. Here is the clean template.

Merging intervals is the gateway to the whole interval family. The trick is sorting by start so overlaps land next to each other, then collapsing them in one linear sweep. Here is the pattern and the sweep-line generalization behind it.

Generating then filtering is O(2^(2n)) and wasteful. Backtracking with two counters builds only valid strings by enforcing the balance rule at every step. Here is the template and why the pruning conditions are exactly right.

The words encode a partial order between characters. Turn each adjacent pair into a directed edge, then topologically sort. The traps are the prefix edge case and detecting contradictions. Here is the full solution with cycle handling.

Words are nodes, one-letter edits are edges, and the shortest ladder is a shortest path in an unweighted graph, so BFS. The make-or-break detail is generating neighbors in O(26 * L) without scanning the whole dictionary. Here is the pattern.

Checking every subarray is O(n squared). Prefix sums plus a remainder-frequency map does it in one O(n) pass: two prefixes with the same remainder mod k bracket a divisible subarray. The trap is negative remainders. Here is the clean answer.

Evaluating arithmetic with precedence and nested parentheses is a parsing problem, and a stack handles both cleanly. The traps are operator precedence, multi-digit numbers, and the sign of truncated division. Here is a single-pass solution.

The canonical multi-round build screen: a simple key-value store that grows new requirements every stage (TTL, transactions, scans). The signal is not stage 1, it is whether your code absorbs stage 4 without a rewrite. Here is how to design for it.

A credit ledger that grants GPU-hours, spends them, and expires unused grants. The trap is which grant to spend first. Here is the FIFO-by-expiry design.

Writes inside a transaction commit or get thrown away, and transactions nest. The overlay-stack design that makes rollback O(1) without touching the base.

A practical build screen: turn a stream of sampled call stacks into a flame tree, then report self-time vs total-time per function. The trap is conflating the two times. Here is how to aggregate the tree and rank the hot functions.

A grounded systems-coding screen: find files with identical content across a tree. The naive all-pairs hash is wasteful. The signal is the size prefilter and a cheap-hash gate before the full hash. Here is the layered approach.

The rotting-oranges family of build screens: a state spreads outward one step per tick across a grid, and the spec gains rules each round. The signal is multi-source BFS by layers, not per-cell loops. Here is the design that absorbs each new test case.

Cells hold values or formulas over other cells, and an edit must recompute dependents without looping forever. Dependency graph plus cycle detection.

Google's 'vibe coding' screen: the spec is deliberately vague and changes mid-interview. The signal isn't the algorithm, it's whether you clarify before coding, structure for change, and keep tests green while the requirements move. Here is how to run that loop.

A Fenwick tree answers prefix-sum queries and point updates in O(log n) with a single flat array and one bit trick. The signal is the lowbit operation and why it beats a plain prefix array under updates. Here is the answer.

A segment tree answers any associative range query (sum, min, max, gcd) with point or range updates in O(log n). The signal is the recursive split into covered, disjoint, and partial nodes, plus lazy propagation for range updates. Here is the answer.

Dijkstra finds single-source shortest paths in O((V+E) log V) with a min-heap, the backbone of routing and network latency problems. The signal is why it needs non-negative weights and how lazy deletion keeps the heap simple. Here is the answer.

Bellman-Ford handles negative edge weights that break Dijkstra and detects negative cycles, the basis of currency-arbitrage problems. The signal is the V-1 relaxation rounds and the extra Vth round that flags a negative cycle. Here is the answer.

Floyd-Warshall computes shortest paths between every pair of nodes in O(V cubed) with a tight three-line triple loop. The signal is the intermediate-node DP order and why k must be the outer loop. Here is the answer.

Kruskal builds a minimum spanning tree by sorting edges and adding the cheapest that does not form a cycle, using union-find for the cycle check. The signal is the greedy cut property and why disjoint-set is the right tool. Here is the answer.

KMP matches a pattern in linear time by precomputing a failure function that skips redundant comparisons instead of backtracking the text. The signal is what the prefix function actually stores and why the text pointer never moves backward. Here is the answer.

Rabin-Karp slides a fixed-width hash over the text so each window costs O(1) to update, making it ideal for matching many patterns at once. The signal is the polynomial rolling hash, modular arithmetic, and why you still verify on a hash hit. Here is the answer.

Binary search on the answer solves minimize-the-maximum and capacity problems by guessing the result and checking feasibility in a monotone predicate. The signal is spotting monotonicity and writing a clean feasibility function. Here is the answer.

Sieving primes, fast modular power, and Euclid's gcd are the number-theory primitives that quietly power crypto, hashing, and combinatorics problems. The signal is the O(n log log n) sieve and O(log e) binary exponentiation. Here is the answer.

Matrix exponentiation evaluates linear recurrences like Fibonacci at index n in O(log n) by raising a transition matrix to the nth power via binary exponentiation. The signal is building the transition matrix and squaring it. Here is the answer.

A time-based key-value store records versioned writes and answers 'what was the value at time t' via binary search over per-key timestamps. The signal is the append-only design and the floor (largest timestamp <= t) lookup. Here is the answer.

A from-scratch classic that tests recursion plus the split criterion math. The signal is computing impurity correctly, choosing the best threshold by information gain, and knowing the stopping rules. Here is a clean recursive implementation.

Fit a mean and variance per class per feature, sum log-likelihoods with the log prior, argmax. Why log space, and what conditional independence buys you.

A from-scratch favorite that tests linear algebra fluency. The signal is centering first, using SVD instead of forming the covariance matrix, and reading variance off the singular values. Here is the implementation and the details interviewers push on.

A from-scratch test of the EM algorithm and soft clustering. The signal is the two alternating steps (responsibilities then weighted re-estimation), log-sum-exp for stability, and knowing how GMM generalizes k-means. Here is the implementation.

A from-scratch test of the least-squares closed form and the numerical traps in it. The signal is deriving the normal equations, knowing why you never explicitly invert, and reaching for lstsq or the SVD instead. Here is the implementation.

A from-scratch test of recurrent forward passes and backprop through time. The signal is the shared-weight recurrence, accumulating gradients across timesteps, and explaining the vanishing-gradient problem. Here is the implementation.

A from-scratch test of gated recurrence. The signal is wiring the forget/input/output gates and candidate correctly, separating cell state from hidden state, and explaining why the additive cell path fixes vanishing gradients. Here is the implementation.

A from-scratch test of modern optimizers. The signal is the moment estimates, bias correction, and the one change that matters: AdamW decouples weight decay from the gradient instead of folding it into the loss. Here is the implementation and why it wins.

A from-scratch test of how learning-rate schedules are actually computed. The signal is correct closed-form formulas, knowing when each schedule shines, and why decaying the rate helps convergence. Here is the implementation of the common ones.

A from-scratch test of how PyTorch actually works under the hood. The signal is building a computation graph during the forward pass, local derivatives per op, and a topological-order backward pass that accumulates gradients. Here is a minimal engine.

A from-scratch test of subword tokenization. The signal is greedy longest-match encoding against a fixed vocabulary, the continuation-prefix convention, and how WordPiece differs from BPE. Here is the implementation.

A from-scratch test of distributed input pipelines. The signal is partitioning data across workers with no overlap and no gaps, epoch-consistent shuffling with a shared seed, and handling the uneven-last-batch problem. Here is the implementation.

The classic recursive-descent exercise with an applied-AI twist: the JSON your model streams is truncated mid-token for the entire generation. The signal is a clean strict parser plus a small repair layer, not a second parser. Here is the implementation.

The most job-shaped coding screen in Applied AI: fan out N LLM calls without melting the rate limit or losing the batch to one bad request. The signal is in the retry policy, not the async syntax. Here is the version that passes.

The coding round version of the RAG question every candidate can describe in prose. Embed, index, retrieve, generate, cite. What separates a pass from a fail is the branch you write for when retrieval comes back with nothing worth quoting.

Everyone can recite the chunking tradeoff. Far fewer can write the splitter, keep the offsets a citation needs, and answer the question that kills the fixed splitter: what happens to a fact that straddles a boundary.

Every LLM product streams, and almost nobody can write the server. The interesting part is not the async generator, it is what happens when the user hits stop, the provider dies at token 90, or moderation flags text you have already put on the screen.