这几题不用大模型，也不用 GPU。先把输入、结果和边界讲清楚，再比较不同写法。它们是本站自拟练习，不对应某家公司的原题。

参考实现在 prep_checks.py，只需要 NumPy。从仓库根目录运行：

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

kNN：向量化到底省了什么？

有三个点 [[0,0], [2,0], [0,3]]，标签是 [0,1,1]。查询点 [1,0] 的平方距离是 [1,1,10]；查询点 [0,2] 的平方距离是 [4,8,1]。先写循环，再用 NumPy 算同一份距离，邻居顺序应该一致。

这里约定：距离相同时取原始行号较小的点，投票相同时取数值较小的标签。因此第一个查询的 1-NN 预测是 0，第二个是 1。换一种平局规则也可以，但要固定下来，不让不同实现偷偷改变结果。

设查询为 [Q,D]，样本为 [N,D]。直接广播会先得到 [Q,N,D] 的差，再沿 D 求平方和，得到 [Q,N]。少写 Python 循环不等于少做距离计算，也不等于更省内存。

写法 距离计算量 主要额外空间，不含输入与最终邻居
逐查询、逐样本、逐维度循环 $O(QND)$ 每次保存一行距离，$O(N)$
一次广播 $O(QND)$ 差值张量 $O(QND)$，再加距离与排序索引
每次处理 C 个查询 $O(QND)$ $O(CND+CN)$；C 控制峰值，不改变所求邻居

配套代码为了平局可重复，对每行完整稳定排序，另需 $O(QN\log N)$ 时间，最终索引占 $O(Qk)$ 空间。别把距离计算量当成整个 kNN 的成本。想改成 partial selection，需要说明最终 k 个如何排序，以及阈值上的平局如何处理。

一个量级检查：1,000 个查询、10,000 个样本、128 维，差值张量有 12.8 亿个元素。仅 float64 差值就约 10.24 GB，还没算输出和临时数组；分成每批 10 个查询，单个差值张量约 102.4 MB。这是元素计数，不是测到的进程峰值。

能不能不生成三维差值张量？

可以用 $\|q-x\|^2=\|q\|^2+\|x\|^2-2q^\top x$，把主要中间量降为 [Q,N]，再继续分块。但两个很接近、幅度很大的向量，可能在相减时损失精度。把负的小误差截成 0，并不能恢复已经丢失的距离排序。先用小数组的直接差值版本做对照，再判断是否需要中心化、提高精度或其他实现。

这页没有实现 ANN 索引。精确搜索、树索引与近似检索（retrieval）的使用条件不同，可接着读 scikit-learn 的邻居算法说明与站内检索路线。

练习：加一个重复点，再把 k 改成 1、N 和 N+1。前两种应有明确结果，最后一种在这份实现里报错。空查询返回空结果；空样本不能回答任何有效 k。这里用普通尺度的有限 float64 数据，不承诺任意极端坐标下都可精确计算。

二分：找到值，和找到边界，不是一回事

[1,2,2,4] 里找 2，返回任意一个 2 不够。如果问题是第一个 ≥ 2，答案是索引 1；最后一个 ≤ 2，答案是索引 2。

两次搜索都维护半开区间 [lower, upper)：第一次把 < target 的部分丢掉，找到 bisect_left 的位置；第二次把 ≤ target 的部分丢掉，找到 bisect_right 的位置，再减一。Python bisect 文档把这两个分区条件写得很清楚。

target 第一个 ≥ target 最后一个 ≤ target
0 0 -1，表示不存在
2 1 2
3 3 2
5 4，表示不存在 3

配套 search_bounds 对空列表返回 (0,-1)。调用者要先检查哨兵；Python 的 values[-1] 会取最后一项，不能直接当“不存在”。输入须已升序排列，搜索本身 $O(\log N)$、额外空间 $O(1)$；排序或插入不是免费的。

Broadcasting：最危险的是能运行，却算错了

两条样本的预测是 [[1],[3]]，标签是 [1,2]。直接相减：

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

第一种把每个预测和每个标签都比较了，得到 [[0,-1],[2,1]]；第二种才是按样本对齐的 [[0],[1]]。上面用 NumPy 检查数值；把这两种写法搬到 PyTorch 的自动求导里，两者都能反向传播，loss 也都是一个标量，所以“训练没报错”发现不了这个问题。

NumPy 的广播规则从尾维开始比较：尺寸相等，或其中一个为 1。规则只检查形状，不知道哪个轴代表样本。继续用 [B,H,T,D] 练 matmul 和 mask，可看张量与形状。

任务依赖：谁现在就能开始？

用一个小数据流程：先读数据，随后清洗和审计可以各自开始；两项都完成，才能训练。

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

Kahn 算法记录每个任务还有几个前置任务没完成，也就是入度。把入度为 0 的任务拿出来，完成后逐个减少后继入度。全部取出就得到拓扑顺序；还有任务却没有可取的点，就有环。

配套 dependency_layers 返回 [[read], [clean,audit], [train]]。图用“任务 → 前置任务列表”输入，邻接表另外建后继关系；重复前置条件去重。时间与空间都是 $O(V+E)$，输出也计入空间。

这些层只表示依赖关系，不是最佳并行排程。 若两个互不相关的任务分别耗时 1 秒和 10 秒，短任务的后继不必等长任务结束。真实执行器应在单个任务完成时释放依赖，并考虑 worker 数、资源、失败、重试与幂等。Python 的 TopologicalSorter.get_ready() / done()可以对照这个区别；done() 要在任务真正跑完后才调用，不能在刚把任务交给 worker 时就调用。

练习：加一条 read 依赖 train 的边，必须报环；加一个独立的 report 任务，它应该可以从第一层开始。代码还要求所有前置任务显式声明，拼错名字不能被当成一个自动完成的节点。

Markov chain：三种问题，别混在一起

假设两个状态 A、B 的转移矩阵是

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

行是现在，列是下一步，每行和为 1。下面三问只用这一张表，就能区分“过几步”“长期分布”和“等多久”。

问题 计算 结果
从 A 出发，两步后在哪？ $[1,0]P^2$ $[0.72,0.28]$
哪个分布转移后不变？ $\pi P=\pi,\ \pi_A+\pi_B=1$ $[2/3,1/3]$
从 A 出发，第一次到 B 平均几步？ $h_B=0,\ h_A=1+0.8h_A$ $h_A=5$

第一问到 B 的概率，也可以拆成 A→A→B 与 A→B→B：$0.8\times0.2+0.2\times0.6=0.28$。第二问由 $0.2\pi_A=0.4\pi_B$ 再归一化。第三问每次先花一步，概率 0.8 回到 A 重新等；到了 B 就停止，不继续计算 B 的后续转移。

配套 markov_example 用矩阵乘法和线性方程验证这三个数。它是这个固定二状态例子的检查，不是处理所有 Markov chain 的通用求解器。更一般的首次到达问题，对非目标状态写 $h=\mathbf1+Qh$（$Q$ 是 $P$ 去掉目标状态所在行和列后剩下的子矩阵，本例中 $Q=[0.8]$）；只有到达条件合适、期望有限时，才可以解 $(I-Q)h=\mathbf1$。

平稳也不自动代表从任意初始分布都收敛。把矩阵换成 [[0,1],[1,0]]，[0.5,0.5] 仍然平稳，但从 A 出发会一直交替。若某个起点根本到不了目标，首次到达时间不是一个有限数。想把状态和动作接起来，继续读 MDP 与 Bellman。

做完之后，改一个条件

不必靠题数判断掌握程度。kNN 数据大十倍，怎么分块？任务有失败，何时允许后继开始？二分允许重复，边界怎么变？能预测改动会影响哪一部分，再写测试验证，比背下这一页更有用。

接下来回到 RE / MLE 准备路线，或继续手写 attention、采样与 MLP。

本页术语 1
检索 retrieval
从外部语料里找出相关内容