Five short exercises: calculate, implement, check

These exercises need neither a large model nor a GPU. Define the inputs, expected results, and boundaries before comparing implementations. They are original practice problems, not questions attributed to a company.

The reference implementation, prep_checks.py, needs only NumPy. From the repository root:

python interview/code/prep_checks.py
python -m unittest discover -s site/tests -p 'test_interview_preparation.py'

kNN: what does vectorization actually save?

Take three points, [[0,0], [2,0], [0,3]], with labels [0,1,1]. The query [1,0] has squared distances [1,1,10]; [0,2] has distances [4,8,1]. Write a loop first, then calculate the same distances with NumPy. The neighbor order should agree.

Our convention breaks distance ties by original row index and voting ties by the smaller numerical label. The first query's 1-NN prediction is therefore 0; the second is 1. Other conventions are possible, but changing implementations should not silently change them.

For queries [Q,D] and points [N,D], direct broadcasting produces differences [Q,N,D]. Summing squared differences over D gives [Q,N]. Fewer Python loops does not mean fewer distance calculations—or less memory.

For reproducible ties, the reference fully stable-sorts each row. That adds $O(QN\log N)$ time; final neighbor indices take $O(Qk)$ space. Distance work is not the entire kNN cost. A partial-selection alternative needs an explicit rule for sorting the chosen k and breaking ties at the cutoff.

A scale check: 1,000 queries, 10,000 points, and 128 features produce 1.28 billion difference elements. The float64 differences alone occupy about 10.24 GB, before output and temporary arrays. Blocks of 10 queries reduce one difference tensor to about 102.4 MB. These are element counts, not measured process peaks.

Try duplicate points and k equal to 1, N, and N+1. The first two need defined results; this implementation rejects the last. Empty queries return empty results; an empty point set cannot support a valid k. The exercise assumes finite float64 inputs of ordinary scale; it does not claim exact results for arbitrarily extreme coordinates.

Binary search: a match is not a boundary

Finding any 2 in [1,2,2,4] is not enough. The first value ≥ 2 is at index 1; the last value ≤ 2 is at index 2.

Both searches maintain a half-open interval [lower, upper). The first discards values < target to find the bisect_left position. The second discards values ≤ target to find bisect_right, then subtracts one. Python's bisect documentation specifies these partition conditions.

The reference search_bounds returns (0,-1) for an empty list. Check sentinels before indexing: Python's values[-1] means the last element, not an absent result. Inputs must already be sorted ascending. Search takes $O(\log N)$ time and $O(1)$ extra space; sorting and insertion have separate costs.

Broadcasting: valid code can compute the wrong loss

Two predictions are [[1],[3]] and their targets are [1,2]. Direct subtraction gives:

import numpy as np

predictions = np.array([[1.0], [3.0]])
targets = np.array([1.0, 2.0])
wrong = predictions - targets
right = predictions - targets[:, None]
assert wrong.shape == (2, 2)
assert right.shape == (2, 1)
assert np.mean(wrong ** 2) == 1.5
assert np.mean(right ** 2) == 0.5

The first compares every prediction with every target: [[0,-1],[2,1]]. The second aligns examples: [[0],[1]]. NumPy checks the numbers here; in PyTorch autograd, both versions would support backpropagation and yield scalar losses. A training loop that runs without errors will not expose the difference.

NumPy broadcasting compares trailing dimensions: sizes must match, or one must be 1. It checks shapes, not which axis represents examples. For [B,H,T,D], matrix multiplication, and masks, continue with tensor operations and shapes.

Task dependencies: what can start now?

Consider a small data workflow: read the data, then run cleaning and auditing independently, and start training only after both finish.

             → clean ─┐
read ────────         ├→ train
             → audit ─┘

Kahn's algorithm tracks each task's unfinished predecessors: its indegree. Take tasks with indegree zero, and reduce successor indegrees after completion. Removing every task yields a topological order. If tasks remain but none is ready, there is a cycle.

The reference dependency_layers returns [[read], [clean,audit], [train]]. Its input maps tasks to predecessors; it separately builds successor lists and deduplicates repeated dependencies. Time and space are $O(V+E)$, including the output.

These layers describe dependencies, not an optimal parallel schedule. If independent tasks take 1 and 10 seconds, successors of the short task need not wait for the long one. A real executor releases dependencies as individual tasks finish and accounts for worker limits, resources, failure, retries, and idempotency. Python's TopologicalSorter.get_ready() / done() illustrates the distinction: call done() when a task finishes, not when it is submitted to a worker.

Add a dependency from read to train: the algorithm must reject the cycle. Add an independent report task: it can appear in the first layer. This implementation also requires every predecessor to be declared, so a typo cannot silently become an already-completed node.

Markov chains: three different questions

Suppose states A and B have transition matrix

$$P=\begin{bmatrix}0.8&0.2\\0.4&0.6\end{bmatrix}.$$

Rows are the current state; columns are the next state, with each row summing to 1. The same table can answer a finite-step, stationary, or waiting-time question—but those are not interchangeable.

For the first question, paths A→A→B and A→B→B give $0.8\times0.2+0.2\times0.6=0.28$. For the second, solve $0.2\pi_A=0.4\pi_B$ and normalize. For the third, spend one step, then with probability 0.8 return to A and start waiting again. Stop upon reaching B; its subsequent transitions do not enter the hitting time.

The reference markov_example checks the three results with matrix multiplication and linear equations. It is a fixed two-state example, not a general solver for all chains. More generally, non-target states satisfy $h=\mathbf1+Qh$, where $Q$ is $P$ restricted to the non-target rows and columns (here $Q=[0.8]$). Solving $(I-Q)h=\mathbf1$ for finite expected times requires appropriate reachability and finiteness conditions.

Stationarity does not guarantee convergence from every initial distribution. With [[0,1],[1,0]], [0.5,0.5] is stationary, but starting at A alternates forever. If a starting state cannot reach the target, its hitting time is not finite. To add actions to states, continue with MDPs and Bellman equations.

Change one assumption

The number of problems you have solved is a poor measure of mastery. With ten times as much kNN data, how would you block it? When a task fails, when may its successors run? How do duplicates change a binary-search boundary? Predict the effect, then test it rather than memorizing this page.

Return to the RE / MLE preparation route, or continue with attention, sampling, and MLP implementations.