ML Interview Prep: Quick recap

01 Hashing, two pointers, windows

Follow one routine: clarify, brute force with its cost, a better plan with cost and invariant, code, test by hand, final complexity.
Read the constraints first: Python does about $10^7$ simple steps per second, so $n \le 3{,}000$ allows $O(n^2)$ , and $n \ge 10^5$ needs $O(n \log n)$ or $O(n)$ .
Dict and set operations are $O(1)$ on average (good hashing) and $O(n)$ in the worst case; x in list, pop(0) and slices are $O(n)$ .
Hash map: look up first, then insert; the map holds only earlier elements, so each pair is checked once.
A subarray sum is a difference of prefix sums, $\text{sum}(i..j-1) = P_j - P_i$ ; counting with a dict that starts at {0: 1} works with negative numbers in $O(n)$ .
Two pointers drop one element per step because the order proves it cannot be in a better answer; fast and slow pointers find the middle of a list and, by Floyd's method, a cycle and its first node with $O(1)$ memory.
A variable sliding window is correct only when the condition is monotone (under shrinking for "longest", under growing for "shortest"); then it is $O(n)$ because each index enters once and leaves at most once.

02 Stacks, binary search, heaps

A stack closes the most recent open item first; with several bracket types a counter is not enough.
A monotonic stack answers "next greater/smaller element" for all indices in $O(n)$ , because each index is pushed once and popped at most once (at most $2n$ comparisons).
Binary search needs a monotone predicate $P$ (F…F T…T). With $[lo, hi)$ , while lo < hi, hi = mid if $P(mid)$ else lo = mid + 1, it returns the first True after at most $\lfloor \log_2(R - L) \rfloor + 1$ calls.
Binary search on the answer works when " $k$ is enough" is monotone; it costs $O(\log(\text{range}))$ calls of the test.
A binary heap stores a complete tree in a list (children $2i+1$ , $2i+2$ ): push and pop cost $O(\log n)$ , heapify costs $O(n)$ , and only heap[0] is known.
For the $k$ largest items of a stream, keep a min-heap of size $k$ : $O(n \log k)$ time, $O(k)$ memory.
Intervals: sort by start, then one sweep merges them; the fewest meeting rooms equals the largest number of overlapping meetings, found by a sweep over start and end events.
A greedy algorithm is correct when some optimal solution starts with the greedy choice; for interval scheduling, earliest end first is optimal (exchange argument), while earliest start and shortest first are not.

03 Trees and graphs

Tree code: solve the left subtree, solve the right subtree, combine at the node; the empty tree is the base case.
Every traversal costs $O(n)$ time. Depth-first traversals need $O(h)$ extra space (the current path); level order needs $O(w)$ (one level in a queue).
A binary tree is a BST if and only if its in-order sequence strictly increases. Validate it by passing an open interval $(low, high)$ down, not by comparing with the parent.
Pre-order with a null marker for every missing child fixes a tree; an $n$ -node tree has $n + 1$ markers.
One loop explores a graph: take a node from the bag, mark it, add its neighbours. A stack gives DFS, a queue gives BFS, a priority queue keyed by distance gives Dijkstra. Cost $O(V + E)$ for BFS and DFS.
BFS finds the fewest edges from the source in an unweighted graph; mark a node when you put it in the queue.
Kahn's algorithm outputs all $V$ nodes exactly when the graph is a DAG; fewer than $V$ means a directed cycle.
Union-find with union by rank and path compression costs $O(\alpha(n))$ amortized per operation. Dijkstra with a binary heap costs $O((V + E)\log V)$ and needs weights $\ge 0$ ; otherwise use Bellman-Ford ( $O(VE)$ ) or DAG relaxation.

04 Backtracking and DP

Backtracking is a depth-first search over partial solutions: choose, explore, undo, and record a copy at each complete solution. Its cost is (number of nodes) × (work per node).
Pruning cuts subtrees that cannot lead to a solution: 8 queens with one queen per row and attacked squares skipped visits 2,057 nodes instead of $8^8 \approx 1.7 \cdot 10^7$ boards.
Use DP when the answer below a node depends only on a small state and states repeat; use backtracking when you must list every solution, because a memo cannot shorten the output.
The DP script: state, recurrence (cases = every possible last choice), base cases and fill order, answer and cost (number of states × work per state).
A memo makes a recursion cost $O(S \cdot W)$ for $S$ states; a bottom-up table fills the states in topological order, has no recursion limit, and often keeps only one row.
Edit distance: $D(i, j) = \min(D(i-1, j) + 1,\ D(i, j-1) + 1,\ D(i-1, j-1) + [a_i \ne b_j])$ , proved by case analysis on the last column of an alignment; traceback recovers the edits.
The tails array of the LIS stays sorted; each new value replaces the first entry $\ge$ it (binary search), so the LIS length costs $O(n \log n)$ .
Greedy coin change fails for coins $\{1, 3, 4\}$ and amount 6 ( $4 + 1 + 1$ against $3 + 3$ ); use the DP $c[a] = 1 + \min_k c[a - k]$ .

05 Practical multi-part coding

A practical round is one class that grows over 3–4 parts. Choose state that keeps every operation cheap, write its invariant, and run all old tests after each part.
Inject the clock and the I/O (clock=time.monotonic, fetch=...), so tests use a fake clock and fake pages and run fast and deterministically.
Nested transactions: a stack of undo maps holds, per key, the value before the level first touched it. begin is $O(1)$ ; rollback writes the top map back; commit copies a key into the parent only if the parent has no entry for it.
An LRU cache is a dict from key to node plus a doubly linked list in order of use, with sentinels; get and put are $O(1)$ , and each node stores its key for eviction.
A token bucket refills lazily, $\tau \leftarrow \min(b, \tau + r(t - t_0))$ , and allows a request if $\tau \ge 1$ ; it allows at most $b + rT$ requests in any window of length $T$ .
A fixed-window limiter can allow $2N$ requests around a window boundary; a sliding log is exact but stores $N$ timestamps; a token bucket allows bursts up to $b$ and the long-run rate $r$ .
A crawler is a BFS with a seen set: mark a URL as seen when it is discovered. In asyncio, a check-and-add with no await in between needs no lock; with threads it does.
In unfamiliar code: run the tests first, reproduce bugs with a failing test, make the smallest change, and never let a tool edit the tests.

06 ML coding in NumPy

Softmax does not change when a constant is subtracted from all logits; subtract $m = \max_j z_j$ , so every exponent is $\le 0$ and the sum is in $[1, K]$ .
$\operatorname{LSE}(z) = m + \log\sum_j e^{z_j - m}$ ; cross-entropy from logits is $\operatorname{LSE}(z) - z_y$ , with gradient $p - e_y$ . Never take $\log$ of a softmax output.
Binary cross-entropy from a logit is $\operatorname{softplus}(z) - yz$ ; logistic regression has the gradient $X^\top(p - y)/n + \lambda w$ , a convex loss, and a safe step $\eta \le 1/\beta$ with $\beta \le \lambda_{\max}(X^\top X)/(4n) + \lambda$ .
On linearly separable data with $\lambda = 0$ , logistic regression has no minimizer: gradient descent drives $\|w\| \to \infty$ .
Lloyd's algorithm never increases the inertia $J$ and stops after finitely many steps, at a local optimum; use k-means++ seeding, several starts, and vectorized distances $\|x\|^2 - 2x^\top\mu + \|\mu\|^2$ clipped at 0.
$\mathrm{AUC} = P(S^+ > S^-) + \tfrac12 P(S^+ = S^-)$ , computed in $O(n \log n)$ as $(R_+ - n_+(n_+ + 1)/2)/(n_+ n_-)$ with average ranks for ties.
In backprop, every gradient has the shape of its parameter, $dW = (\text{input})^\top (\text{upstream gradient})$ , and the bias gradient sums over the batch; for softmax cross-entropy with a mean, $\partial L/\partial Z = (P - Y)/B$ .
Check a hand-written gradient with central differences in float64, $\varepsilon \approx 10^{-6}$ : a relative error below about $10^{-6}$ means correct.

07 Training loop, AdamW, BPE

AdamW: decay $\theta \leftarrow (1 - \gamma\lambda)\theta$ , then $m$ and $v$ updates, bias correction $\hat m = m/(1 - \beta_1^t)$ , $\hat v = v/(1 - \beta_2^t)$ , and the step $\gamma\,\hat m/(\sqrt{\hat v} + \varepsilon)$ .
Bias correction makes $\hat m_t$ unbiased when $m_0 = 0$ ; with it, Adam's first step has size $\gamma$ in every coordinate, and Adam ignores the scale of the loss.
L2 inside Adam is divided by $\sqrt{\hat v}$ , so weights with large gradients are barely regularized; AdamW decays every weight by the same factor $1 - \gamma\lambda$ .
Mixed-precision Adam needs about 16 bytes per parameter: 2 (bf16 weights) + 2 (bf16 gradients) + 4 (fp32 master) + 4 ( $m$ ) + 4 ( $v$ ).
Gradient accumulation is exact when each micro-batch loss is divided by $K$ (equal sizes); for token losses, divide the summed loss by the total number of tokens in the window.
fp16 has a small range and needs dynamic loss scaling; bf16 has the fp32 range but only 8 significant bits, so weights, optimizer state and long sums stay in fp32.
The step order: zero grad, autocast forward, scaled backward, unscale, clip, step, update the scaler, step the schedule.
Byte-level BPE merges the most frequent adjacent pair (weighted by chunk counts, with a stated tie rule); encoding applies the merges in learned order, and there is no unknown token.

08 Transformer decoder from scratch

Attention: $S = QK^\top/\sqrt{d_h}$ , masked entries set to $-\infty$ before a softmax over the keys, $O = \operatorname{softmax}(S)V$ ; scale by the head size because $q^\top k$ has variance $d_h$ .
Heads are a reshape: view(B, T, H, d_h).transpose(1, 2); view(B, H, T, d_h) has the right shape but mixes tokens. Multi-head attention has $4D^2$ weights for any $H$ .
RMSNorm$(x) = \gamma \odot x/\sqrt{\operatorname{mean}(x^2) + \varepsilon}$: LayerNorm without centering and without $\beta$ ; use the biased mean, $\varepsilon$ inside the root, fp32 inside.
RoPE rotates pair $i$ of $q$ and $k$ by $m\omega_i$ ; since $R_m^\top R_n = R_{n-m}$ , the score depends only on the offset $n - m$ . Rotate $q$ and $k$ , never $v$ .
In a causal decoder, the keys and values of a token never change, so cached decoding equals the full forward pass; new tokens need absolute positions $P, \dots, P+T-1$ and the mask tril(diagonal=P), not is_causal=True.
The KV cache needs $2 L\, n_{kv} d_h\, b$ bytes per token; GQA divides it by $n_h/n_{kv}$ .
Top-p keeps the smallest set of tokens with mass at least $p$ (keep sorted token $j$ when the mass before it is $< p$ ), then renormalizes; temperature is applied first.
Beam search keeps the $n_b$ best prefixes by summed log-probability; finished hypotheses are compared by $\log P(y)/|y|^\alpha$ , because raw scores favour short outputs.

09 Classic ML and A/B tests

Bias–variance (squared loss): expected test error $= \sigma^2 + \text{bias}^2 + \text{variance}$ ; the cross terms vanish because the noise has mean 0 and is independent of the training set.
L1 (lasso) gives exact zeros by soft thresholding, $w_j = \operatorname{sign}(\hat w_j)(|\hat w_j| - \lambda)_+$ ; L2 (ridge) only shrinks. L1 = Laplace prior, L2 = Gaussian prior.
The variance of an average of $M$ models with correlation $\rho$ is $\rho\sigma^2 + (1-\rho)\sigma^2/M$ : bagging lowers variance, random forests also lower $\rho$ ; boosting fits pseudo-residuals and mainly lowers bias.
ROC-AUC measures ranking and ignores the class ratio; precision and AP depend on it. With rare positives, report precision at the operating point.
With calibrated probabilities, flag when $p > c_{FP}/(c_{FP} + c_{FN})$ .
Bayes with a base rate: 99% sensitivity and specificity at 0.5% prevalence give $P(D \mid +) \approx 33\%$ .
Sample size per arm: $n = (z_{1-\alpha/2} + z_{1-\beta})^2(\sigma_1^2 + \sigma_2^2)/\delta^2 \approx 16\,p(1-p)/\delta^2$ ; half the MDE needs four times the users.
A/B pitfalls: peeking (10 looks give about 19% false positives), sample-ratio mismatch (check with $\chi^2$ ), many metrics, interference, unit of analysis ≠ unit of randomization.

10 Deep learning breadth

Deep networks multiply per-layer gains; initialization, normalization, residual connections, clipping, warmup and Adam all keep these gains near 1 or survive when they are not.
Variance propagation: $\operatorname{Var}(z_i) = n\,\sigma_w^2\,\mathbb E[h_j^2]$ , and ReLU halves the second moment, so He initialization uses $\sigma_w^2 = 2/n_{\text{in}}$ ; with $1/n$ , 12 ReLU layers shrink it to $2^{-12}$ .
AdamW decays every weight by $1 - \eta\lambda$ outside the adaptive step; L2 inside Adam is divided by $\sqrt{\hat v}$ and barely regularizes weights with large gradients.
BatchNorm uses batch statistics in training and running averages in eval; LayerNorm and RMSNorm compute the same function in both and do not depend on the batch, so transformers use them.
A residual block has Jacobian $I + J$ , so the gradient always has an identity path; pre-LN keeps that path clean and trains stably without warmup.
Inductive bias: CNNs assume locality and translation equivariance; transformers let all pairs interact at cost $O(T^2)$ and need positional information and more data.
Flow matching learns the conditional mean velocity $\mathbb E[x - \varepsilon \mid x_t]$ ; one Euler step from noise gives the data mean, and with Gaussian paths diffusion and flow matching are one family.
Before a long run: the first loss should be about $\ln K$ , and the model must be able to overfit one batch.

11 LLM breadth

Training a chat model: pretraining (knowledge) → mid-training (quality, long context) → SFT (format) → preference tuning (which answer people prefer) → RL with verifiable rewards (reasoning), with evaluation at every step.
A uniform model over $V$ tokens has loss $\ln V$ and perplexity $V$ . Compare perplexity only with the same tokenizer; bits per byte does not depend on it.
Training compute is $C \approx 6ND$ FLOPs (2 forward + 4 backward per parameter per token); inference is about $2N$ FLOPs per token; mixed-precision Adam stores about 16 bytes per parameter.
Chinchilla: at fixed compute, grow $N$ and $D$ together, about 20 tokens per parameter, so $N \approx \sqrt{C/120}$ . The iso-FLOP curve is flat near its minimum, so practice trains smaller models on many more tokens to save inference cost.
LoRA trains $\Delta W = (\alpha/r) BA$ with $r(d + k)$ parameters, $A$ random and $B = 0$ at the start. It saves gradients and optimizer states, not activations.
The KL-regularized RLHF objective has the optimal policy $\pi^* \propto \pi_{\text{ref}}\, e^{r/\beta}$ . DPO puts this into the Bradley–Terry model, where $\log Z$ cancels, and trains offline on pairs.
GRPO uses the group-normalized advantage $(r_i - \text{mean})/\text{std}$ instead of a value model; a group with equal rewards gives no signal.
An accuracy $\hat p$ on $n$ questions has standard error $\sqrt{\hat p(1-\hat p)/n}$ ; pass@ $k$ needs the unbiased estimator $1 - \binom{n-c}{k}/\binom{n}{k}$ .

12 Training at scale

Mixed-precision AdamW needs 16 bytes per parameter (2 weight + 2 gradient + 12 optimizer states), plus activations of about $sbh(34 + 5as/h)$ bytes per layer, or $34\,sbh$ with FlashAttention.
A ring all-reduce sends $2\frac{p-1}{p}n \approx 2n$ bytes per GPU, whatever the number of GPUs; it is a reduce-scatter followed by an all-gather.
Data parallelism with equal shards gives exactly the full-batch gradient; the all-reduce hides behind the backward pass when each GPU has at least $F/\text{BW}$ tokens per step.
ZeRO-1/2/3 shard optimizer states, then gradients, then parameters: ZeRO-3 needs $16\Psi/N_d$ bytes per GPU and sends $3\Psi$ values per step, $1.5\times$ DDP.
Tensor parallelism splits each weight matrix (columns, then rows) and needs 4 all-reduces per layer per step, so it stays inside an NVLink node.
A pipeline with $p$ stages and $m$ micro-batches idles a fraction $(p-1)/(m+p-1)$ of the step; 1F1B keeps the bubble but caps the stored activations at $p$ micro-batches.
Training costs $6\Psi + 12Lsh$ FLOPs per token (full attention); GPU-hours follow from the total FLOPs at an assumed MFU of 35–45%.
A job on $N$ GPUs fails every $M = M_{\text{gpu}}/N$ on average; the best checkpoint interval is $\tau^* = \sqrt{2\delta M}$ , with overhead $\sqrt{2\delta/M}$ .

13 LLM serving

Decode reads all weights and every sequence's KV cache in each step, so its step time is about $(\Psi b + B\,C\,k)/\text{BW}$ : it is memory-bound, and TPOT $\approx$ this step time.
The KV cache needs $k = 2\,L\,n_{kv}\,d_h\,b$ bytes per token (800 KiB for Llama-2-13B in bf16); the tokens that fit are the free memory divided by $k$ .
A weight matmul on $B$ tokens does about $B$ FLOPs per byte, so prefill is compute-bound and decode needs a large batch; decode attention stays at $n_h/n_{kv}$ FLOPs per byte for any batch.
Continuous batching refills a batch slot at the next step after a request ends, which removes idle slots and head-of-line blocking.
Paged attention stores the cache in fixed blocks with a block table, so each sequence wastes less than one block; reference counts and copy-on-write let sequences share a prefix.
Weight-only int4/int8 speeds up memory-bound decode; W8A8/FP8 speeds up compute-bound prefill and large batches; an fp8 KV cache doubles the tokens that fit.
Speculative decoding gives $(1-\alpha^{\gamma+1})/(1-\alpha)$ tokens per target pass and keeps the target distribution exactly.
Little's law $L = \lambda W$ turns traffic into concurrency; an M/M/1 server has $W = 1/(\mu - \lambda) = S/(1-\rho)$ , so latency explodes near full utilization.

14 ML system design

An ML system design answer follows a time plan: clarify (0–5 min), metrics (5–8), funnel and numbers (8–11), data and labels (11–19), model (19–27), serving and evaluation (27–34), monitoring, deep dives and trade-offs (34–45).
Large catalogs need a funnel: retrieval optimizes recall over millions of items cheaply; ranking optimizes precision at the top on a few hundred candidates with rich features; re-ranking adds diversity and rules.
Back-of-envelope: peak QPS $= f \cdot U r / 86{,}400$ ; index memory $= N d b$ ; ranker compute $\approx$ QPS $\times K \times 2P$ FLOP/s.
$\text{NDCG@}k = \text{DCG@}k / \text{IDCG@}k$ with $\text{DCG@}k = \sum_{i \le k} (2^{\text{rel}_i} - 1)/\log_2(i+1)$ ; say which gain you use.
A two-tower model scores $\langle u(x), v(y)\rangle/\tau$ , so item vectors go in an ANN index; its in-batch softmax needs the log-Q correction $s - \log q_j$ , or popular items are under-scored.
Ranking learns from impressions with several heads (click, watch time, like, dismiss); weighted logistic regression with watch-time weights learns odds $\approx \mathbb{E}[\text{watch time}]$ .
Position bias: weight clicks by $1/\theta_k$ (IPS) or use the position as a training-only feature; fight feedback loops with exploration.
Deploy through a gate, shadow, canary and A/B test, with a fast rollback. PSI $= \text{KL}(q\|p) + \text{KL}(p\|q)$ has a noise floor $(k-1)(1/n + 1/m)$ with no drift.

15 GenAI system design

The adaptation ladder: prompting for format and simple tasks, RAG for knowledge that changes or needs citations and access control, fine-tuning for behaviour; RAG for knowledge, fine-tuning for behaviour.
A RAG system has an offline path (parse, chunk, embed, index with metadata) and an online path (rewrite, hybrid retrieval, fusion, rerank, prompt with chunk ids, generate, check, stream).
Chunks of $c$ tokens with overlap $o$ : $n = \lceil (T - c)/(c - o) \rceil + 1$ ; every span of at most $o + 1$ tokens lies inside one chunk.
Hybrid retrieval fuses BM25 and dense lists by ranks: $\text{RRF}(d) = \sum_r 1/(60 + \text{rank}_r(d))$ ; a cross-encoder reranks the top 20–100.
RAG latency is dominated by prefill ( $\approx 2 P T_\text{in}$ FLOPs) and the extra model calls; prefix caching saves the prefill of the system prompt and the earlier turns.
An agent with per-step accuracy $p$ completes $n$ steps with probability $p^n$ ( $0.95^{10} \approx 0.60$ ); defend against prompt injection with least privilege and human confirmation.
Classifier-free guidance: $\hat\varepsilon = \varepsilon_\emptyset + w(\varepsilon_c - \varepsilon_\emptyset)$ , two denoiser evaluations per step; the number of steps is the main cost lever.
Evaluate retrieval (recall@k, MRR, nDCG) separately from answers (correctness, faithfulness, citations); check an LLM judge with Cohen's $\kappa$ ; compare two systems with a paired test such as McNemar's.

16 Behavioral and research talk

Behavioral questions collect evidence of past decisions; the level of the offer follows the scope of your stories (your work, the team, several teams).
STAR plus Reflection: Situation and Task about 25% of the time, Action about 50–55%, Result about 15%, Reflection 5–10%; a 2.5-minute answer is about 375 words at 150 words per minute.
A strong story says "I" for decisions, has a number in the Situation and in the Result, and contains a decision between real alternatives.
The six common themes are conflict, failure, ambiguity, influence without authority, ownership and hard trade-off; a bank of 8–10 stories should give each theme at least two stories, with no story used for more than three themes.
A research talk is judged on depth, judgment, communication and fit; state the main result in the first 3 minutes, then earn it.
The 5-minute talk keeps the problem and the main result, one picture of the idea, one result with its baseline, and why it matters for the team.
A decision table (choice, alternatives, evidence, cost or risk, what would change my mind) prepares you to defend every design choice.
Answer questions with a routine: listen, clarify, answer first in one sentence, give the evidence, say what you do not know and how you would check it.