本文是《面试手撕代码：从 LeetCode 中等题到 Transformer 组件》系列的第 20 篇（共二十篇）。上一篇：Infra 岗手撕——并发与系统。
十九篇正文回答了一个问题：面试官给一道没见过的中等题、四十分钟，怎样在前五分钟认出它属于哪一类、用哪个模板、复杂度是多少，然后把时间用来写对代码、想清边界、接住追问。前十三篇按解题模式而不是数据结构的名字组织 LeetCode 中等题——哈希、双指针、单调栈、链表、树、图、二分、堆与贪心、回溯、字符串、两篇 DP、设计题，每篇一个可以默写的骨架、三到七道主讲题、一张两种语言的坑表；后六篇是 AI 岗特有的”手撕模型组件”——attention、Transformer block 与反向传播、tokenizer 与解码、损失与训练算法、经典 ML 与指标、Infra 岗的并发与系统，每个组件从零写出来并与 PyTorch 参考实现对拍。
本文不讲新内容，做三件事：把十九篇压成一张表与十九段回顾，把贯穿全系列的四条线拎出来，然后给一套三段式的通关自测——判断与计算、跨篇综合、面试手撕题。各篇末尾的自测检验的是”这一篇读懂了没有”，这里检验的是”看到新题能不能调出正确的模板、写出能跑的代码”。
一、总览：系列回答的问题与主线
系列的一句话主张是：中等难度的面试题背后只有十来种模式，每种模式有一个可以背下来的骨架、两三处必错的边界、一组典型的追问；AI 岗的手撕题不考识别，考对组件的理解是否精确到能写出来、并且知道怎么验证。前十三篇的主线是”识别信号 → 模板 → 主讲题推演 → 变式与追问 → 两种语言的坑”，后六篇的主线是”面试怎么出题 → 形状推演 → 从零实现 → 与 torch 对拍 → 数值与形状陷阱 → 追问”。两条主线共用一个方法：先说清骨架与不变量，再写代码，写完用最小的边界输入走查。
| 篇 | 回答的问题 | 一句话结论 | 必记的数字 / 公式 |
|---|---|---|---|
| 01 数组、哈希与前缀和 | 怎样用一张哈希表换掉一层循环？ | 边查边存、前缀和 + 计数、只从起点数、原地哈希、差分——五种用法都是”把见过的记下来” | \(\text{sum}(i, j] = \text{pre}[j] - \text{pre}[i]\)；count[0] = 1；值 \(v\) 放下标 \(v - 1\)，交换 \(\le n\) 次 |
| 02 双指针与滑动窗口 | 两个指针只往一个方向走，凭什么不漏解？ | 单调性：右扩不会让违规变合法、左收不会让合法变违规；含负数的”和 = k”不满足 | 窗口 / 对撞 / 快慢三形态；LC 76 用 missing 计数使每步 \(O(1)\)；接雨水水位 \(= \min(\text{leftMax}, \text{rightMax})\) |
| 03 栈、单调栈与单调队列 | 单调栈弹出时结算什么？ | 被弹出者的右侧第一个更大 = 当前元素、左侧第一个更大 = 新栈顶，两侧边界同时确定 | 每个元素进出各一次 \(O(n)\)；两端哨兵 0；单调队列取窗口最值 \(O(n)\) 而堆是 \(O(n \log k)\) |
| 04 链表 | 链表题怎样手稳不丢链？ | 哑节点统一头节点特判，三指针反转先存 nxt，快慢指针找中点 / 判环 |
Floyd：\(a = (k - 1)c + (c - b)\)；归并切分 fast = head.next；K 组反转 prev 初值 = group_next |
| 05 二叉树 | 递归函数”返回什么”与”更新什么”为什么不是同一个量？ | 返回给父节点的是能继续向上延伸的链，答案在拐点处用全局变量更新 | 递归三要素；层序先记 len(q)；BST 验证带上下界 (lo, hi)；建树 pos[val] 哈希 + 前序指针 |
| 06 图 | 先看出是图，然后 visited 放在哪？ | 五个算法：BFS、DFS、Kahn 拓扑、并查集、Dijkstra；BFS 入队时标记 | Kahn 出队数 \(< n\) 即有环；并查集路径压缩 + 按大小合并 \(O(\alpha(n))\)；Dijkstra 堆 + 懒删除 \(O(E \log E)\)；双向 BFS \(O(b^{d/2})\) |
| 07 二分 | 为什么二分只有一个模板？ | 在”假假假真真真”的单调谓词上找第一个真：[lo, hi)、真收 hi = mid、假收 lo = mid + 1 |
答案二分 \(O(n \log V)\)；值域第 k 小 count_le(x) >= k；两数组中位数在短数组上二分 \(O(\log \min(m, n))\) |
| 08 堆、Top-K、区间与贪心 | 按什么键排序或维护什么顺序？ | 第 K 大用大小为 K 的最小堆；区间按起点排一趟扫、选最多不重叠按终点；贪心靠交换论证 | 堆 \(O(n \log k)\)、快速选择期望 \(O(n)\)；双堆先进 small 再倒；会议室 = 起点排序 + 结束时间最小堆 |
| 09 回溯 | 排列、组合、子集的递归参数差在哪？ | 做选择 → 递归 → 撤销；排列用 used[]，组合用 start；剪枝不改量级但决定能否跑完 |
排列 \(O(n \cdot n!)\)、子集 \(O(n \cdot 2^n)\)、括号 \(O(4^n / \sqrt{n})\)、单词搜索 \(O(mn \cdot 3^L)\)；out.append(path[:]) 必须拷贝 |
| 10 字符串 | 字符串特有的技巧有哪些？ | 中心扩展、KMP 失配表、状态机解析、竖式、a + b 与 b + a 比较、滚动哈希 |
\(2n - 1\) 个中心；lps[i] = 最长真前缀 == 真后缀；竖式 res[i + j + 1]；溢出在乘 10 之前判 |
| 11 DP（一） | 怎样从题面推出状态定义？ | 五步法：定义状态（”前 \(i\) 个”还是”以 \(i\) 结尾”）→ 枚举最后一步 → 初始 → 顺序 → 答案 | LIS tails 二分 \(O(n \log n)\)；编辑距离三格 = 删 / 插 / 换；最大正方形 1 + min(上, 左, 左上)；INF = amount + 1 |
| 12 DP（二） | 背包、区间、状态机、树形各记一句什么？ | 倒序 = 一次、正序 = 无限；区间枚举最后被处理的元素；状态机画图再写 | 组合数外层物品、排列数外层容量；戳气球 \(O(n^3)\) 开区间 + 哨兵 1；hold 初值 \(-\infty\)（Java MIN_VALUE / 2） |
| 13 设计题 | 单一结构做不到的复杂度怎样用两个结构互相索引做到？ | 哈希 → 双向链表节点；频次桶 + min_freq；26 叉树；数组 + 值到下标；lowbit 分块 |
LRU 全 \(O(1)\)；LFU min_freq 最多 +1 或重置为 1；O(1) 随机集删除末尾换位；树状数组 \(O(\log n)\) |
| 14 attention | multi-head 的四次形状变换是什么，KV cache 缓存什么？ | 先 reshape(B, T, H, d) 再 transpose；softmax 减最大值；mask 用 \(-\infty\)；online softmax 最大值变时重缩放 |
参数 \(4D^2\)；FLOPs \(8TD^2 + 4T^2D\)；每 token KV \(2 L H_{kv} d \cdot \text{bytes}\)（Llama-3-8B 128 KB）；GQA 缩 \(H / H_{kv}\) 倍 |
| 15 Transformer block 与反向 | 一层参数为什么约 \(12D^2\)，CE 的梯度为什么是 \(p - y\)？ | 每参数一次乘加 → 前向 \(2N\)、训练 \(6N\)；局部导数 × 上游梯度，形状自查 | GPT-2 small 124,439,808；LayerNorm 反向 \(\frac{1}{\sigma}(d\hat{x} - \overline{d\hat{x}} - \hat{x}\,\overline{d\hat{x} \odot \hat{x}})\)；micrograd 梯度累加 += |
| 16 tokenizer 与解码 | BPE 编码为什么按 merge 顺序而不是贪心最长匹配？ | tie-break (频次, 字典序)；采样流水线 penalty → T → softmax → top-k → top-p → min-p；投机解码输出分布恰为 \(p\) |
top-p 保留首个越界项；蓄水池第 \(i\) 个以 \(k / i\) 替换；接受率 \(= 1 - \text{TV}(p, q)\) |
| 17 损失与训练算法 | 论文公式怎样落成十行正确的代码？ | DPO 四个序列 log 概率、初值 \(\ln 2\)；GAE 从末尾递推；PPO 取 min；AdamW 衰减解耦；LoRA B = 0 |
\(A_t = \delta_t + \gamma\lambda A_{t+1}\)；Adam 第一步移动约 \(\eta \cdot \text{sign}(g)\)；每参数 16 字节训练状态；LoRA \(r(\text{in} + \text{out})\) |
| 18 经典 ML 与指标 | k-means 为什么收敛，AUC 怎样 \(O(n \log n)\)？ | 模型 = 目标 + 优化；AUC = 正样本秩和 \(- n_+(n_+ + 1)/2\) 除 \(n_+ n_-\)；conv = im2col + GEMM | 逻辑回归梯度 \(X^\top(p - y) / n\)；NDCG 折扣 \(1 / \log_2(i + 1)\)；\(H_\text{out} = \lfloor (H + 2p - k) / s \rfloor + 1\)；im2col 大 \(k_h k_w\) 倍 |
| 19 Infra 并发与系统 | 一把锁保护什么、条件变量为什么 while？ |
get 也要锁；两个条件变量各叫各的；异常进 Future；空闲链表嵌在块内；分块要测了再说 |
ring allreduce 每 rank \(2\frac{N - 1}{N}V\) 与 \(N\) 无关；ikj 比 ijk 快 11 倍；paged KV fork 只加引用、写时复制一块 |
1. 本文的章节安排
| 章 | 内容 |
|---|---|
| 二 | 逐篇回顾：核心问题、结论、必记、常见误解，共十九段 |
| 三 | 贯穿全系列的四条线：识别信号 → 模式的决策、不变量思维、Python 与 Java 的差异、AI 手撕与 torch 对拍的方法论 |
| 四 | 常见误区表 |
| 五 | 通关自测：A 判断与计算 10 题、B 跨篇综合 5 题、C 面试手撕题 8 题、D 掌握判据 |
| 六 | 下一步 |
二、逐篇回顾
1. 第 01 篇：数组、哈希与前缀和
核心问题：”和为 K 的子数组个数”为什么是前缀和 + 哈希而不是滑动窗口？最长连续序列怎样 \(O(n)\) 不排序？缺失的第一个正数要求 \(O(1)\) 额外空间，哈希表放在哪？
结论：数组题考的只有一件事——用一张哈希表换掉一层循环。两数之和是”先查再存”（先存会让 \(x\) 和自己配对）；和为 K 的子数组把问题变成”有多少对 \((i, j)\) 使 \(\text{pre}[j] - \text{pre}[i] = k\)“，对每个 \(j\) 查 \(\text{pre}[j] - k\) 出现过几次，数组含负数时窗口不单调、只能这样做；最长连续序列只从起点（\(x - 1\) 不在集合里）向右数，每个数只被数一次；缺失的第一个正数答案在 \([1, n + 1]\)，把值 \(v\) 交换到下标 \(v - 1\)，数组自己就是哈希表；差分把区间加法变成两个端点的单点修改，与前缀和互逆。
必记：
count[0] = 1代表空前缀，漏掉它[1, 2]里k = 3的整段答案会丢。- 原地哈希的
while条件比较目标位置nums[nums[i] - 1] != nums[i]，防[1, 1]死循环；交换总次数 \(\le n\)。 - 遍历
set而不是nums：一万个 1 加 \(1 \ldots 5000\) 时遍历原数组退化到 \(O(n \cdot L)\)。 - 除自身以外的乘积：左积写进输出、右积一个变量，两趟 \(O(n)\)，无除法。
- 二维差分是同一思路的四个角；\(k\) 次多项式的区间加需要 \(k + 1\) 阶差分。
常见误解：含负数的”和 = k”用滑动窗口——右扩后和可能变小，无法决定何时收左边。另一个：Python 的 -1 % 3 == 2 直接可用，Java 是 -1，前缀和取模要 ((x % k) + k) % k。
2. 第 02 篇：双指针与滑动窗口
核心问题：”右扩左收”什么时候成立？最小覆盖子串怎样让每一步 \(O(1)\)？接雨水的双指针为什么可以只看自己这一侧的最大值？
结论：不用额外空间、靠单调性把 \(O(n^2)\) 压到 \(O(n)\)。三种形态：同向变长 / 定长窗口（子串题）、相向对撞（有序配对、面积、接雨水）、同向不同速的快慢指针（原地分区）。窗口能用的前提是合法性对窗口长度单调；每个决定”动哪个指针”都要能用一句话证明”不动的那种情况不可能更优”——盛水容器移动矮的一侧，因为移高的那侧面积必然变小。LC 76 用一个整数 missing 代替每步比较两张计数表；LC 424 的 max_freq 只记历史最大也不影响答案，因为窗口长度只在真实合法时增长。
必记：
- LC 3 的
left只能跳到last[ch] + 1且必须last[ch] >= left，否则"abba"返回 3。 - LC 76：
need[c] > 0才减missing；need[s[left]] < 0的左端字符多余可丢；覆盖后主动破坏窗口继续找更短。 - 接雨水：
height[lo] < height[hi]时right_max >= height[hi] > height[lo]，且此刻left_max <= right_max，结算lo只用left_max。 - 三数之和三处去重：
i跳过相同、找到后lo、hi各跳过相同值。 - 求”最短”时把动作换过来：满足时记录并收左边。
常见误解：LC 209 含负数也能用窗口——[1, 2, -5, 4]、target 3 会返回 2 而正解是 1（[4]），要用前缀和 + 单调队列（LC 862）。
3. 第 03 篇：栈、单调栈与单调队列
核心问题：单调栈里的元素弹出时，为什么左右两侧边界同时确定？柱状图最大矩形的两端哨兵各解决什么？滑动窗口最大值为什么用双端队列不用堆？
结论：栈解决”最近的未完成事项”：括号配对、3[a2[c]] 展开、乘除立即结算加减延迟到最后求和（末尾补 + 逼出最后一个数）。单调栈是特化：递减栈里栈顶 \(j\) 被 \(i\) 弹出时 \(a_j < a_i\) 且中间元素都已被弹出，所以 \(i\) 是 \(j\) 右侧第一个更大、新栈顶是左侧第一个不小于它的。柱状图用递增栈 + 两端哨兵 0：开头的 0 让栈永不空、结尾的 0 把所有柱子在循环内逼出。单调队列维护”下标递增、值递减”，队尾比新元素小的永远不会再是窗口最大，队首过期就弹。
必记：
- 四种变体只改比较符：递减栈
<找右侧更大，递增栈>找右侧更小；含不含相等决定重复元素归谁。 - 柱状图宽 \(= i - \text{stack.top} - 1\)；相等高度用
>留在栈里，后一个会算出完整宽度。 - 单调队列 \(O(n)\)，堆 + 懒删除 \(O(n \log k)\)。
- 接雨水单调栈解：弹出高
bottom时这一层水 \(= (\min(h_l, h_i) - \text{bottom}) \times (i - l - 1)\)，栈空则break。 - Java 用
ArrayDeque不用java.util.Stack；Pythonint(a / b)向零取整而//向下。
常见误解：每日温度的 while 用 <=——把 70 当成比 70 更高，[70, 70, 71] 得 [1, 1, 0] 而正解 [2, 1, 0]；比较符由题目里”更大”是否严格决定。
4. 第 04 篇：链表
核心问题：哑节点省掉了哪些特判？快慢指针相遇后为什么一个回到头、同速再走就在环入口相遇？K 个一组反转怎样 \(O(1)\) 空间且代码不失控？
结论：链表题不考算法考手稳。哑节点让头节点也有前驱，”修改前驱的 next“对所有位置通用，删头、头前插入、left = 1 的区间反转、分组反转的第一组都不再特判。三指针反转的顺序固定：先存 nxt、再改 cur.next、再前进。Floyd 判环：设头到入口 \(a\)、入口到相遇点 \(b\)、环长 \(c\)，\(2(a + b) = a + b + kc\) 得 \(a = (k - 1)c + (c - b)\)，所以从头与从相遇点同速走 \(a\) 步都到入口。K 组反转的关键是反转时 prev 初值设为 group_next，反转后组尾自动接上下一组。合并 K 条用堆 \(O(N \log k)\)；排序用归并、切分时 fast = head.next。
必记：
- 快慢指针
while fast and fast.next；偶数长度slow停在第二个中点，切分要第一个中点则fast = head.next。 - Python 堆元组必须带链编号
(val, i, node)，否则值相等时比较ListNode抛TypeError。 - 相交链表”各走 A + B”，不相交时两者同时到
None。 - 递归反转深度 \(O(n)\)，Python 默认上限 1000。
- 写完用
[]、[1]、[1, 2]三个输入过一遍。
常见误解：归并切分 fast = head 也行——[2, 1] 会切成 [2, 1] 与空，无限递归。另一个：cur.next = prev 写在 nxt = cur.next 之前，后半段全部丢失。
5. 第 05 篇：二叉树
核心问题：递归”返回什么”和”更新什么”为什么常常不是同一个量？验证 BST 为什么不能只比较父子？前序 + 中序建树时哈希表与递归指针各解决什么？
结论：树天然递归——一个节点的答案由左右子树的答案拼出。写任何树递归先回答三要素：返回什么、在前序还是后序处理当前节点、终止条件。直径、最大路径和、LCA 这类题返回值是”向下的一条链”（能继续向上延伸），答案是”在某节点拐弯”的量（l + r + node），只能在拐点更新全局变量。层序 BFS 先记 len(q) 一轮一层。BST 的约束是全局的，递归带上下界 (lo, hi) 或中序严格递增。前序 + 中序建树：pos[val] 让”根在中序里的位置”\(O(1)\)，前序指针顺序消耗、先建左子树自然先用掉左子树节点。序列化用前序 + #。路径总和 III 是 01 篇的前缀和搬到树上，离开节点时要撤销计数。
必记：
- 最大路径和
best初值 \(-\infty\)（节点可全负），gain里负贡献截断为 0。 - LCA：左右都非空返回当前，否则返回非空的一侧；
root is p直接返回。 - 反例
[5, 4, 6, null, null, 3, 7]：3 在 5 的右子树里却小于 5。 - Java 上下界用
Long，否则单节点[2147483647]误判。 - 前序 + 后序不能唯一建树：单孩子节点无法区分左右。
常见误解：LC 437 不撤销 count[pre] -= 1 也对——[2, -2, 0]、target 2 会多算一条不存在的路径返回 3。
6. 第 06 篇：图——BFS / DFS / 拓扑 / 并查集 / 最短路
核心问题：BFS 的 visited 在入队时打还是出队时打？拓扑排序怎样同时判环？并查集的路径压缩和按大小合并各起什么作用？
结论：面试的图题很少给”图”，给的是网格、课程依赖、单词列表、账户邮箱——第一步是看出它是图，第二步建图（显式邻接表或隐式邻居函数），第三步套五个模板之一。网格 DFS 把边界判断放进递归入口、原地标记；BFS 按层、入队时标记、多源同时入队；Kahn 入度为 0 先出，出队数 \(< n\) 即有环，DFS 三色法遇灰色即环；并查集 find 路径减半 + union 小挂大；Dijkstra 堆里放 (dist, node)，弹出时 d > dist[u] 就是过期条目跳过，不需要 decrease-key。单词接龙用双向 BFS，总是扩展小的一侧。
必记：
- 出队时标记结果仍对，但同一节点重复入队，最坏 \(O(V^2)\)。
- 腐烂橘子
while q and fresh：没有好橘子返回 0、最后一层烂完不多算一分钟。 - 只压缩或只按大小合并都是 \(O(\log n)\)，两个都写 \(O(\alpha(n))\)，各两行。
- Dijkstra 堆里最多 \(O(E)\) 条目，忘了跳过过期条目答案仍对但退化为 \(O(E \cdot \deg)\)；负权不能用。
- \(300 \times 300\) 全陆地网格递归 \(9 \times 10^4\) 层，Python 会崩，改显式栈或 BFS。
常见误解：三色 DFS 遇到黑色节点算环——黑色是已探索完且无环的区域，只有灰色（在当前栈上）才构成回路。另一个：无权图最短路用 DFS——DFS 找到的只是一条路径。
7. 第 07 篇：二分——只有一个模板
核心问题：为什么”第一个使谓词为真的位置”能覆盖全部二分题？”答案二分”怎样把最优化变成判定？两个有序数组的中位数为什么在短数组上二分？
结论：lo <= hi 还是 lo < hi、mid 还是 mid + 1——每次现场想的根源是把二分当成”有序数组找值”。二分的本质是在”假假假真真真”的单调谓词上找第一个真：first_true(lo, hi, pred)，左闭右开、hi 兼作”没找到”、真收 hi = mid、假收 lo = mid + 1、mid 向下取整保证 mid < hi 不死循环。找值是 a[i] >= t，找最后一个是对取反谓词找第一个再减一，旋转数组最小值是 a[i] <= a[-1]，峰值是 a[i] > a[i + 1]，答案二分是 feasible(x)，值域第 k 小是 count_le(x) >= k。唯一例外是”找等于就返回”的 LC 33 用闭区间变体。答案二分三步：定范围 [理论下界, 一定可行值 + 1)、写 \(O(n)\) 贪心判定、确认单调方向。
必记：
- 吃香蕉判定 \(\sum \lceil p_i / k \rceil \le h\)；分割数组与运送包裹（LC 1011）完全同构，判定是”贪心装箱段数 \(\le k\)“。
- 有序矩阵第 k 小：
count_le从左下角走阶梯 \(O(n)\)，总 \(O(n \log V)\)，答案一定在矩阵里。 - 中位数：\(j = \text{half} - i\)，
a[i-1] <= b[j]且b[j-1] <= a[i]即合法；短数组上 \(j\) 自动不越界。 - Java
mid = lo + (hi - lo) / 2，(long) m * m，求和用long。 - 数据范围 \(10^9\) 以上、答案是整数 → 想值域二分。
常见误解：mid = (lo + hi + 1) // 2 也行——区间长 1 时 mid = hi 越界，pred 为真时 hi = mid 不缩小、死循环；只有”最后一个为真、收 lo = mid“的镜像模板才向上取整。
8. 第 08 篇：堆、Top-K、区间与贪心
核心问题：第 K 大用大小为 K 的最小堆还是快速选择？数据流中位数的两个堆怎样维持平衡？会议室 II 为什么按开始时间排序、用最小堆存结束时间？
结论：三类题写起来相似——先决定按什么键排序或维护什么顺序，剩下的是一趟循环。第 K 大用最小堆存最大的 K 个，堆顶就是第 K 大，\(O(n \log k)\)、支持数据流；快速选择随机 pivot 三路分区期望 \(O(n)\)，但改数组、最坏 \(O(n^2)\)、不能用于流。前 K 高频用桶排序 \(O(n)\)。数据流中位数：新数先进大顶堆 small 再把最大倒到 large，这一进一出保证 small 全 \(\le\) large 全，只剩一个方向的平衡判断。区间合并按起点排、终点取 max；选最多不重叠按终点排保留结束最早的；会议室按开始排序，堆顶（最早结束的房间）没空出则其他更不可能，堆大小即答案。贪心用交换论证：把最优解某一步换成贪心选择，结果不会更差。
必记：
- 求第 K 大用最小堆、第 K 小用最大堆；Python 最大堆存负数。
heapreplace比 pop + push 少一次调整。- 扫描线里同一时刻 \(-1\) 先于 \(+1\)，
[1, 5]与[5, 10]只要一间。 - 跳跃游戏 II 循环到 \(n - 2\)，否则
end恰等于 \(n - 1\) 时多算一跳。 - Java 比较器写
Integer.compare，不写x - y（溢出）。
常见误解：合并区间 out[-1][1] = e——[[1, 10], [2, 3]] 得 [[1, 3]]，起点排序不保证终点递增。
9. 第 09 篇：回溯
核心问题：排列、组合、子集三种题的递归参数差在哪？排列去重为什么要多加 not used[i-1]？回溯的复杂度怎么估、剪枝能改量级吗？
结论：回溯只有一个骨架——做选择、递归、撤销；所有题的差别在三处：候选集合怎么定（排列没有 start 用 used[]，组合 / 子集从 start 往后，可重复选递归传 i 否则 i + 1）、怎么去重（排序后跳过同层相同值）、怎么剪枝（排序后 > remain 就 break）。子集在每个节点收集答案无终止条件；括号生成只走合法的边天然无重；切分型枚举下一段的结束位置；棋盘题原地标记再恢复，N 皇后用 c、r - c、r + c 三个集合 \(O(1)\) 判冲突。回溯与 DFS 的区别只在”撤销”。复杂度 = 决策树节点数 × 每节点工作量；剪枝不改最坏上界，但决定能否在时限内跑完。
必记：
- 排列 \(O(n \cdot n!)\)、子集 \(O(n \cdot 2^n)\)、组合 \(O(k \binom{n}{k})\)、括号 \(C_n \approx 4^n / n^{1.5}\)、单词搜索 \(O(mn \cdot 3^L)\)。
- 排列去重
nums[i] == nums[i-1] and not used[i-1]；子集去重i > start and nums[i] == nums[i-1]——是i > start不是i > 0。 break是剪枝（后面都不可能），continue是去重（跳过这一个）。- 只问方案数（LC 377 / 518）用 DP 不用回溯；最少切几刀（LC 132）同理。
- \(n \le 20\) 说明预期就是指数级枚举。
常见误解：out.append(path) 不拷贝——六个引用指向同一个最后被 pop 空的列表，返回六个空列表。
10. 第 10 篇：字符串
核心问题：最长回文子串为什么中心扩展比区间 DP 更适合面试，Manacher 改进了什么？KMP 的 lps 存的是什么、失配跳到 lps[k-1] 为什么不漏解？”拼接后最大的数”为什么用 a + b 与 b + a 比较就是对的？
结论：字符串题一半是前面模式的字符版，另一半是特有技巧。中心扩展试 \(2n - 1\) 个中心（\(n\) 个字符 + \(n - 1\) 个间隙），\(O(n^2)\) 时间 \(O(1)\) 空间；Manacher 插 # 统一奇偶、用镜像复用回文半径、右边界只增，\(O(n)\)。KMP 的 lps[i] 是 pattern[:i+1] 最长”真前缀 == 真后缀”的长度，失配时主串指针不回退、模式指针退到 lps[k-1]，建表与匹配是同一段代码；取最长保证任何更短的合法对齐都会被后续 while 依次尝试。atoi 是四阶段状态机，溢出在乘 10 之前判断。竖式乘法 res[i + j + 1] 累加后统一进位。最大数的比较器把每个数映射到 \(x / (10^{\lvert x \rvert} - 1)\)，是真正的全序。DNA 重复序列用 2 bit 位压缩滚动哈希无冲突。
必记：
build_lps("ababaca") = [0, 0, 1, 2, 3, 0, 1]；重复子串判定n % (n - lps[-1]) == 0。- Java atoi 判断
num > (MAX - d) / 10对-2147483648恰好正确——截断值刚好是边界。 - 竖式
res[k]最大 \(81 \min(m, n)\)，不溢出int；结果去前导零。 - 最大数全零特判只看
out[0]；Java 比较器不满足传递性TimSort会抛异常。 - 写完过三个输入：空串、单字符、全相同字符。
常见误解：最大数按数值排序——3 与 30，330 > 303。另一个：只试 \(n\) 个字符中心，"cbbd" 返回 "c" 而不是 "bb"。
11. 第 11 篇：动态规划（一）——线性与二维
核心问题：怎样从题面推出状态定义而不是背题？LIS 的 \(O(n \log n)\) 解法里 tails 存的是什么？编辑距离的三种操作各对应状态表的哪一格？
结论：中等 DP 只有一维和二维两种形状，难点在状态定义。五步法：定义状态并说清是”前 \(i\) 个”（答案在 f[n]）还是”以 \(i\) 结尾”（答案是 max(f)，子数组 / 子序列的最值几乎都用它）→ 枚举”最后一步是什么”得转移 → 初始条件 → 计算顺序 → 答案在哪。零钱兑换最后一枚是哪种硬币；LIS 的 tails[k] 是长度 \(k + 1\) 的递增子序列的最小可能末尾，二分找第一个 \(\ge x\) 替换或追加；Kadane 要么接上前面要么从自己重开，乘积版同时维护最大最小；LCS 相等取左上 +1、否则取上与左的 max；编辑距离末字符不等时上格是删、左格是插、左上格是换；最大正方形 1 + min(上, 左, 左上)；单词拆分 f[i] = any(f[j] and s[j:i] in words)。
必记：
INF = amount + 1：Pythonfloat("inf")会让返回值变浮点，JavaMAX_VALUE + 1溢出成负。tails不一定是真实子序列（[2, 5, 1]得[1, 5]），长度是对的。- 乘积最大子数组候选三个：
x、cur_max·x、cur_min·x，少了x时[0, 2]得 0。 - 编辑距离
f[i][0] = i全删、f[0][j] = j全插；只允许插删时答案 \(= m + n - 2 \cdot \text{LCS}\)。 - 二维表初始化不要
[[0] * n] * m——所有行是同一个列表。
常见误解：零钱兑换能贪心——[1, 3, 4] 凑 6 贪心三枚、最优两枚。另一个：最大正方形去掉左上项——[[0, 1], [1, 1]] 会算出 2。
12. 第 12 篇：动态规划（二）——背包、区间、状态机、树形
核心问题：0/1 背包与完全背包的一维写法为什么只差容量倒序还是正序？区间 DP”枚举最后一个被处理的元素”怎样把戳气球变成三重循环？买卖股票六道题为什么是同一个状态机？
结论：四种更特殊的状态形状。背包压成一维后，容量倒序遍历读 f[c - x] 时它还是上一行的值——每个物品只用一次；正序读到的是本行的值——可以重复用。计数时外层硬币内层容量得组合数，外层容量得排列数（LC 377）；最值不怕重复计数，顺序无所谓。区间 DP 正着想”先戳哪个”子问题不独立，反着想开区间 \((i, j)\) 里最后被戳的 \(k\)，它的邻居恰是不会被戳的边界，两端补哨兵 1，\(O(n^3)\)。股票全家族只有 hold / free 两状态加交易次数维度，121 / 122 / 123 / 188 只差 \(k\)，309 把 free 拆成 sold 与 rest，714 卖出减手续费。树形 DP 后序返回 (偷, 不偷)。正则的 * 依附前一个字符（记忆化更自然），通配符的 * 独立，两个分支”匹配空 / 再吃一个”覆盖任意长度。
必记：
- 倒序 = 一次、正序 = 无限；
[1]、target 2 正序会错得True。 - 分割等和子集：总和奇数直接否；目标和 \(P = (S + \text{target}) / 2\)。
- \(k \ge n / 2\) 时股票 IV 退化为 122；
hold初值 \(-\infty\)，JavaMIN_VALUE / 2防+ p溢出；\(j\) 倒序复用一维。 - 冷冻期买入只能从
rest转来，允许从sold转就退化成 122。 - 戳气球 \(n = 300\) 三重循环 \(2.7 \times 10^7\) 次，Python 约 3 秒接近超时。
常见误解：零钱兑换 II 内外层可以交换——amount = 3、coins = [1, 2] 外层金额得 3（排列数），外层硬币得 2（组合数）。
13. 第 13 篇：设计题与数据结构实现
核心问题：LRU 为什么必须是哈希表 + 双向链表？LFU 怎样 \(O(1)\) 找到”频次最低且最久未用”的键？O(1) 随机集删除时为什么把末尾换到被删位置？
结论：设计题考组合数据结构——先列每个操作要做的事，再问”哪一步不是 \(O(1)\)“，给那一步加索引。LRU：哈希定位节点 \(O(1)\)，摘中间节点要改前驱的 next 所以是双向链表，两个哨兵免去空链特判，节点存 key 是为了淘汰尾节点时能从 map 删掉。LFU：kv、kf、buckets（频次 → OrderedDict，插入序即 LRU 序）加 min_freq；新 key 进来 min_freq 重置为 1，某 key 升频时只有它是 min_freq 桶最后一个时 min_freq 才 +1。Trie 沿字符走 \(O(L)\)，单词搜索 II 沿 Trie 走一次 DFS 匹配所有单词、命中置空 end 去重、叶子用完摘掉。O(1) 随机集：数组 + 值到下标，删除时末尾换到被删位置再弹，先 pos[last] = i 再 del pos[val]。树状数组 tree[i] 覆盖 \((i - \text{lowbit}(i), i]\)。
必记：
- 单用哈希找最久未用 \(O(n)\)；单用链表定位 key \(O(n)\)。
- LFU 容量 0 时
put直接返回，否则buckets[min_freq]为空会崩。 prefix(i)访问的元素个数 =i二进制里 1 的个数，\(\le \log n\)；lowbit(i) = i & -i。- 库实现先手写再提：Python
OrderedDict.move_to_end，JavaLinkedHashMap(cap, 0.75f, true)。 - 写完用容量 1 / 容量 0 / 重复 key / 删最后一个元素四个边界过一遍。
常见误解：Python 有内置有序表——标准库没有平衡树，选项是 bisect + list（插入 \(O(n)\)）、第三方 sortedcontainers 或用堆 / 树状数组绕过；Java 直接 TreeMap。
14. 第 14 篇：手撕 attention 家族
核心问题：multi-head attention 的四次形状变换各是什么、为什么必须先 reshape 再 transpose？KV cache 缓存了什么、增量解码为什么不需要 causal mask？online softmax 为什么扫一遍就能得到与完整 softmax 相同的结果？
结论：(B, T, D) 里连续的是 \(D\)，reshape(B, T, H, d) 只是按顺序切成 \(H\) 段不移动数据，再 transpose(1, 2) 得 (B, H, T, d) 让每个头独立做矩阵乘；直接 reshape(B, H, T, d) 形状对但数全错；合并是严格的逆操作。softmax 减最大值让最大的指数是 \(e^0 = 1\) 不上溢、分母至少 1 不除零；log-softmax 写成 \(x - \text{logsumexp}(x)\)。除 \(\sqrt{d}\) 把内积方差从 \(d\) 拉回 1；mask 用 \(-\infty\) 而不是 0，否则被屏蔽位置仍有权重。GQA 在 split_heads 后沿头维 repeat，KV cache 与 KV 投影从 \(H\) 份变 \(H_{kv}\) 份，计算量不变。RoPE 只加在 q、k 上，内积只依赖 \(s - t\)。KV cache 缓存历史 token 的 \(k, v\)，增量解码新 token 是最后一个、没有未来可屏蔽，只有 prefill 需要 mask。online softmax 维护 \(m, \ell, \text{acc}\)，最大值变大时旧值乘 \(e^{m - m'}\) 换到新基准——这是 FlashAttention 一趟分块的核心。
必记：
- 参数 \(4D^2\)（多头不增加参数）；FLOPs \(8TD^2 + 4T^2D\)，\(T > 2D\) 时 attention 项超过投影项。
- 每 token KV \(= 2 L H_{kv} d \cdot \text{bytes}\)；Llama-3-8B 128 KB / token，8K 上下文 1 GB；不用 GQA 则 512 KB。
- 一行全 mask 的 softmax 是
nan；fp16 下-1e4不够小，用torch.finfo(dtype).min。 nn.MultiheadAttention的attn_maskTrue 表示屏蔽；in_proj_weight是 \((3D, D)\)，权重要转置写入。- RoPE 相邻配对与
rotate_half两种约定数学等价但不能混用。
常见误解：训练与推理的 attention 一样——训练一次算全序列，推理 prefill 全序列 + decode 逐 token 用 KV cache；KV cache 用 list.append 每步拼接 \(O(T)\) 拷贝，要预分配 T_max。
15. 第 15 篇：手撕 Transformer block 与反向传播
核心问题：一个 GPT 层的参数量为什么约 \(12D^2\)、每 token 前向 FLOPs 为什么约 \(2 \times\) 参数量？softmax + 交叉熵对 logits 的梯度为什么是 \(p - y\)？LayerNorm 反向里那两个”减均值”项从哪来？
结论：pre-LN block：x + mha(LN₁(x))，再 x + ffn(LN₂(x))。LayerNorm 沿最后一维、有偏方差、eps 在开方里；RMSNorm 去掉均值中心化和 beta；SwiGLU 三个矩阵、中间维 \(\frac{8}{3}D\) 与 \(4D\) FFN 参数持平。一层 attention \(4D^2\) + FFN \(8D^2\) = \(12D^2\)，bias 与 LN 只有 \(O(D)\)。每参数一次乘加 = 2 FLOPs，前向 \(2N + 4TDL\)，训练 \(6N\)——Chinchilla \(C = 6ND\) 的来源。反向是”局部导数 × 上游梯度”：Linear dx = dout @ w.T、dw = x.T @ dout；CE 的 \(\log p_y = z_y - \log\sum e^{z_k}\) 求导后 softmax 雅可比与 \(-1/p_y\) 约掉只剩 \(p - \mathbb{1}[j = y]\)；LayerNorm 的 \(\mu\)、\(\sigma\) 都依赖每个 \(x_i\)，传回两个修正项，分别扣掉”整体平移”与”整体缩放”方向的梯度。micrograd 三要点：前向时挂反向闭包、梯度累加 +=、后序 DFS 拓扑序反转。
必记：
- GPT-2 small：每层 7,087,872；12 层 85,054,464；嵌入 38,597,376（占 31%）；总 124,439,808。
- attention 项超过全部线性项的条件 \(T > 6D\)（\(D = 768\) 时 4608）；\(T = 1024\) 时 attention 占 18%。
- torch 的
var默认无偏，对拍差 \(\sqrt{N / (N - 1)}\)；GELU 精确版与 tanh 版差 \(10^{-3}\)。 - CE 用
mean就要/ N，忘了等效学习率放大 \(N\) 倍（Adam 下几乎不受影响）。 - He 初始化 \(\sqrt{2 / \text{in}}\)；XOR 数据、隐层 16、300 步 loss 0.80 → 0.05。
常见误解：micrograd 里梯度用 =——c = a + a * a 在 \(a = 2\) 处正确梯度 5，用 = 得 2。另一个：log(softmax(x)) 可用——极小概率处已下溢成 0，log(0) = -inf。
16. 第 16 篇：手撕 tokenizer 与解码
核心问题：BPE 训练”合并最频繁的相邻对”如何确定性、编码为什么必须按训练顺序应用 merge？top-k、top-p、min-p 各在哪一步、按什么顺序叠加？投机解码的接受规则加拒绝重采样为什么恰好得到分布 \(p\)？
结论：BPE 训练把词拆成字符加 </w>，按词频加权统计相邻对，合并最频繁的一对，tie 按 (频次, 字典序)；编码不是贪心最长匹配，而是反复合并当前序列里 rank 最小的相邻对，未见过的组合退化到更小单元、永不失败。采样流水线：repetition penalty（正除负乘）→ temperature 除 logits → softmax → top-k → top-p（”之前累计已 \(\ge p\)“的丢，首个越界项保留）→ min-p → 重归一化。beam search 在 log 域累加、每步剪到 \(b\)、遇 eos 移入 finished、长度归一化 score / len^alpha；beam 大会让”安全、短”的序列胜出。蓄水池第 \(i\) 个以 \(k / i\) 替换随机一个，每个元素最终概率 \(k / n\)。投机解码接受 \(\min(1, p / q)\)，拒绝后从 \(\text{norm}(\max(0, p - q))\) 重采：\(\min(p, q) + \max(0, p - q) = p\)。
必记：
- 语料
low×5 lower×2 newest×6 widest×3第一次合并t</w>（9 次）；newer编码为['ne', 'w', 'e', 'r', '</w>']。 probs = [0.6, 0.25, 0.1, 0.05]：top_p = 0.5只留首项，top_p = 0.85留前两个，min_p = 0.2阈值 0.12 留前两个。- temperature 在 softmax 前，截断在后；截断后必须重归一化。
- 接受率 \(= \sum \min(p, q) = 1 - \text{TV}(p, q)\)；\(q = [0.5, 0.3, 0.2]\)、\(p = [0.2, 0.3, 0.5]\) 时 0.7。
- 玩具 LM 里贪心
[1, 0, 3]概率 0.15，beam = 2 找到[2, 3]概率 0.38。
常见误解：投机解码拒绝后从 \(p\) 重采——接受的部分已经拿了 \(\min(p, q)\)，再从 \(p\) 采分布会偏离；必须从残差重采。
17. 第 17 篇：手撕损失函数与训练算法
核心问题：DPO 只用四个序列 log 概率，怎样组合、\(\beta\) 起什么作用？GAE 的递推为什么从末尾往前、\(\lambda\) 怎样在偏差与方差之间调？AdamW 与”Adam + L2”的区别在代码哪一行？
结论：这些题考”把公式落成十行正确的代码”的细节。label smoothing 平滑的是目标分布，ignore_index = -100 是 SFT 的 loss mask；KL 的 \(p\) 是 target，F.kl_div(input=log q, target=p) 参数顺序与数学记法相反；BCE 用 \(\max(z, 0) - zy + \log(1 + e^{-\lvert z \rvert})\) 恒等式；InfoNCE 是相似度矩阵上标签为对角线的交叉熵，温度 0.07 把 \([-1, 1]\) 拉到 \([-14, 14]\)。DPO：policy 与 reference 各对 chosen / rejected，先减 reference 再 chosen 减 rejected，乘 \(\beta\) 过 \(-\log\sigma\)，是 Bradley–Terry 的负对数似然。GAE \(A_t = \delta_t + \gamma\lambda A_{t+1}\) 只能从末尾递推，\(\lambda = 0\) 是一步 TD、\(\lambda = 1\) 是 MC 回报。PPO 的 min 让 clip 只在改进方向越界时生效，是悲观下界。GRPO 用组内 z-score 代替 critic。AdamW 把 \(\lambda\theta\) 直接加在更新里而不进 \(m, v\)。LoRA B = 0 让初始 \(\Delta W = 0\)，(x @ A) @ B 保持低秩收益，alpha / r 让调 \(r\) 不用重调学习率。
必记：
- DPO 初值 \(\ln 2 = 0.693\)；loss 降到 0.1 时 margin \(\approx 2.25\)、\(\beta = 0.1\) 下 log 比之差 \(\approx 22.5\)。
- Adam 第一步更新 \(\approx \eta \cdot \text{sign}(g)\)——warmup 必要的直观原因；偏差修正除 \(1 - \beta^t\)。
- 每参数训练状态约 16 字节，7B 全参训练 112 GB 以上。
- 全局范数裁剪
[3, 4]→[0.6, 0.8]保方向；按值裁剪变[1, 1]改方向。 - LoRA \(4096^2\)、\(r = 16\)：可训练 0.78%；误写
x @ (A @ B)先算 \(AB\) 要 537M FLOPs，比主分支多 16 倍。
常见误解：weight decay 加进梯度就是 AdamW——那是 L2 正则，衰减项被 \(\sqrt{\hat{v}}\) 归一化，梯度大的参数几乎不衰减。另一个：LoRA 两个矩阵都随机初始化——初始输出被噪声破坏；都置零则梯度永远为 0。
18. 第 18 篇：手撕经典 ML 与评测指标
核心问题：k-means 的两步各在优化什么、为什么一定收敛？AUC 为什么等于”随机一对正负样本排对的概率”、怎样 \(O(n \log n)\)？im2col 展开后的矩阵形状是什么、代价是什么？
结论：十行代码暴露对”模型 = 目标函数 + 优化”的理解。k-means 分配步与更新步各自让 \(J = \sum \lVert x_i - c_{\text{label}_i} \rVert^2\) 不增，分配方式有限且不重复，有限步收敛到局部最优，用 k-means++（按 \(D^2\) 概率选中心）与多次重启；空簇保留旧中心。逻辑回归梯度 \(X^\top(p - y) / n\) 与 softmax-CE 同型，L2 只加在 \(w\)。KNN 直接复用 08 篇大小为 k 的堆。PCA = 中心化数据的 SVD，主成分是右奇异向量，方差解释比是奇异值平方占比。AUC 是 Mann–Whitney U：正样本秩和减 \(n_+(n_+ + 1) / 2\) 除 \(n_+ n_-\)，并列取平均秩自动算 0.5。NDCG 增益 \(2^{rel} - 1\)、折扣 \(1 / \log_2(i + 1)\)、除理想 DCG。conv2d 把每个感受野展平成 cols 的一行，cols @ w_mat.T 一次 GEMM，代价是内存大 \(k_h k_w\) 倍。NMS 按分排序贪心压制，IoU 不相交时要 clip 到 0。
必记：
scores = [0.9, 0.8, 0.8, 0.3]、y = [1, 0, 1, 0]：AUC = 0.875。[3, 2, 3, 0, 1, 2]的 NDCG@5 = 0.876；第 2 位折扣 0.63、第 10 位 0.29。- ResNet 第一层 \(224 \times 224 \times 3\)、\(7 \times 7\)、64 通道、stride 2、pad 3：输出 112、参数 9,472、FLOPs 236M，
cols是 \((12544, 147)\)。 - 卷积参数 \(C_\text{out} C_\text{in} k_h k_w + C_\text{out}\)，与输入尺寸无关。
- 99% 负样本时全预测负准确率 99%、F1 为 0；不平衡看 F1 / PR-AUC。
常见误解：PCA 不中心化也行——第一主成分会指向数据均值方向；不标准化时单位为毫米的特征方差大一百万倍主导第一主成分。
19. 第 19 篇：Infra 岗手撕——并发与系统
核心问题：条件变量的等待为什么必须 while 而不是 if？ring allreduce 每个 rank 发送的数据量为什么与 rank 数无关？paged KV cache 的 fork 为什么只加引用计数、写时才复制？
结论：Infra 岗考系统，每道题背后有一个”为什么这样设计”。线程安全 LRU 的 get 也改链表顺序必须加锁；miss 时锁外计算 + 锁内二次检查，或 singleflight。有界队列用一把锁两个条件变量：被唤醒到重新拿到锁之间条件可能已变、POSIX 还允许虚假唤醒，所以 while；只用一个条件变量会叫醒错误的一方。线程池 worker 必须捕获异常存进 Future，关闭时每个 worker 一个 None 哨兵；Python 线程池适合 IO 密集，CPU 密集受 GIL 用进程池。内存池把空闲链表嵌在块内，\(O(1)\)、无碎片、LIFO 复用热块。GEMM 的 ikj 让内层沿连续维、可向量化，\(n = 512\) 时比 ijk 快 11 倍，而分块反而慢——三个矩阵 3 MB 装得进 16 MB 的 L2；真正的 BLAS 分块是为寄存器分块加 packing。ring allreduce 两阶段各 \(N - 1\) 步，每步发一块 \(V / N\)，合计 \(2\frac{N - 1}{N}V < 2V\)；参数服务器的 server 入流量 \(N \cdot V\)。paged KV：fork 只加引用是 \(O(\text{块数})\) 元数据操作，只有最后一个未满的块可能被写、写前 ref > 1 就复制这一块。令牌桶用一个时间戳懒补充，允许突发、长期匀速。
必记：
- ijk 93 ms / 2.9 GFLOP/s，ikj 8.3 ms / 32，blocked（bs = 64）12 ms / 22。
- 内存池块至少
sizeof(Node*)= 8 字节；tcmalloc 用 32 位下标支持更小块。 - \(N = 4\) 时每 rank 发 6 块；NCCL 小消息用 tree、大消息用 ring。
- 10 token、block 4、fork 出两个分支各追加一个 token：5 块，b0、b1 ref 3，其余 ref 1。
- 令牌桶容量 5、速率 10/s：突发过 5 个，0.25 s 后再过 2 个；分布式用 Redis + Lua 原子脚本。
常见误解：”分块一定快”——说的是背书，测出来解释为什么不快才是理解。另一个：shared_mutex 能优化 LRU——get 也是写，读写锁帮助不大，要改 CLOCK 近似或分段锁。
三、贯穿全系列的几条线
1. 识别信号 → 模式的决策
每篇算法篇的第一章都是一张”题面里出现 → 想到”的表，总纲把它们合成一张图：数组 / 字符串上找子数组、子串、配对；链式 / 树形 / 图结构；求最值、可行性、方案数；设计一个支持若干操作的结构。第 01 篇与第 02 篇用同一个信号”子数组的和”做了第一次分流：全正数用窗口、含负数用前缀和 + 哈希、含负数求最短用前缀和 + 单调队列（第 03 篇 LC 862）。第 07 篇给出第二个决策入口——数据范围：\(n \le 20\) 想回溯（第 09 篇）、\(n \le 10^5\) 排除 \(O(n^2)\)、值域 \(10^9\) 想值域二分。第 11 篇与第 09 篇之间是第三条分界：”枚举所有方案”用回溯、”只问方案数 / 能否”用 DP——LC 39 与 377 / 518、LC 131 与 132、LC 139 与 140 各是一对。
一道题落在两个分支上是常态，这正是追问的来源：接雨水既是第 02 篇的双指针也是第 03 篇的单调栈；第 K 大既是第 08 篇的堆也是快速选择；LC 287 在第 01 篇是原地哈希的变式、在第 04 篇是 Floyd 判环、在第 07 篇是值域二分；LC 85 在第 03 篇是逐行柱状图、在第 11 篇说明正方形的 min 技巧对矩形不成立；单词搜索在第 09 篇是棋盘回溯、到第 13 篇加上 Trie 一次 DFS 匹配所有单词。识别的目标不是给题贴一个标签，而是能说出两种解法各自的复杂度与适用场景。
2. 不变量思维
代码骨架都不到十行，能不能写对取决于有没有先说清”循环里什么始终成立”。第 02 篇的窗口不变量是”每个 right 处窗口都合法”（或”满足时才收左边”），成立的前提是合法性对长度单调；对撞指针的不变量是”被排除的一侧不可能更优”，接雨水靠 left_max <= right_max 这一条推出只看自己这侧。第 03 篇的单调栈不变量是”栈底到栈顶单调”，弹出这个动作因此有了含义——两侧边界同时确定；单调队列的不变量是”下标递增、值递减”，队首就是最值。第 04 篇的快慢指针靠”进环后每步距离缩短 1”保证相遇。第 06 篇的 Dijkstra 靠”弹出即定终值”，负权破坏它。第 07 篇把这条线推到最一般：二分只需要一个不变量——谓词在 [lo, hi) 上”假假假真真真”，hi = mid 与 lo = mid + 1 都保持它且严格缩小区间。
第 08 篇的双堆不变量是 small 全部 \(\le\) large 全部且大小差不超过 1，”先进 small 再倒”用两次固定操作维持它；第 11 篇的 tails 不变量是”严格递增、tails[k] 是长度 \(k + 1\) 的最小末尾”，二分替换维持它；第 12 篇的背包不变量是”倒序时 f[c - x] 还是上一行”；第 13 篇的 LFU 不变量是 min_freq 桶非空、LRU 的双向链表两端有哨兵。到了 AI 篇这条线变成数值不变量：第 14 篇的 online softmax 维护 \((m, \ell, \text{acc})\) 与”当前基准是迄今最大值”，最大值变化时重缩放保持它；第 19 篇的 paged KV 不变量是”引用为 0 才回收、ref > 1 的块不原地写”，条件变量的 while 则是在”醒来时条件未必成立”的前提下重建不变量。写代码前把不变量说给面试官听，正是总纲四十分钟流程里第 5 步的内容。
3. Python 与 Java 反复出现的差异
每篇算法篇末尾的”两种语言的坑”表加起来，同样几条反复出现。整数溢出：第 01 篇前缀和用 long，第 02 篇三数相加，第 07 篇 mid = lo + (hi - lo) / 2 与 (long) m * m，第 08 篇比较器不写 x - y，第 10 篇 atoi 在乘 10 之前判断，第 11 篇 INF 不用 MAX_VALUE，第 12 篇 hold 用 MIN_VALUE / 2——Python 无溢出但也因此可以”算完再截”（atoi）。负数取模：第 01 篇 Python -1 % 3 == 2、Java 要 ((x % k) + k) % k；第 03 篇 Python // 向下取整、int(a / b) 才向零，Java / 本来就向零。递归深度：Python 默认 1000，第 04 篇长链递归反转、第 05 篇退化成链的树、第 06 篇 \(300 \times 300\) 网格 DFS、第 11 篇 lru_cache 记忆化都会撞上，Java 一般够但 \(10^5\) 级深链也溢出。
容器与比较：第 03 篇不用 java.util.Stack；第 04 篇 Python 堆里放节点要带序号、Java 传比较器；第 01 与第 06 篇 int[] 不能做 HashSet 的 key；第 10 篇 Java 字符串比较用 equals；第 11 篇 Python 二维表不能 [[0] * n] * m；第 04 与第 12 篇 Python 多重赋值右侧先算完、Java 必须临时变量且顺序不能反；第 02 与第 10 篇两种语言的切片 / substring 都是拷贝。第 13 篇的有序表是 Python 的尴尬点，Java 直接 TreeMap。这些差异不是琐碎的语法，而是同一个算法在两种语言里”哪一行会错”——面试时主动说出来（”这里 Java 要用 long”）是编码质量维度的加分项。
4. AI 手撕与 torch 对拍的方法论
后六篇共用一条验证方法：NumPy 从零实现，用 --check 与 PyTorch 参考实现对拍到 \(10^{-10}\) 量级（第 14 篇 softmax / sdpa / mha / gqa / 增量解码 / online softmax / RoPE 七组断言；第 15 篇 layer_norm_backward 对 autograd、gpt_params 对 nn 模块 numel、Value 对 torch.tensor 标量；第 17 篇 AdamW 同初值同梯度 10 步误差 \(10^{-12}\)；第 18 篇 conv2d 三组 stride / pad、roc_auc 对 \(O(n^2)\) 定义式、nms 对 torchvision.ops.nms）。面试时不一定能跑对拍，但要能说出对拍的方法，这本身是加分项。
这条线的第二层是”自检基准值”：第 14 篇不减最大值的 softmax 是 [nan nan nan]、增量解码与全序列 causal attention 差 \(10^{-15}\)、online softmax block = 2 差 \(10^{-16}\)；第 15 篇 GPT-2 small 按公式算出 124,439,808 与逐模块数出的一致、micrograd 在 \(a = 2, b = 3\) 处 a.grad = 7/3；第 17 篇 DPO 初值 \(\ln 2\)、GAE 递推对显式级数；第 16 篇 beam = 1 等于贪心、蓄水池每元素频率 0.297–0.303、投机解码输出 [0.205, 0.300, 0.495]。第三层是 torch 语义陷阱，形状能过、结果全错：第 14 篇 attn_mask True 表示屏蔽、in_proj_weight 要转置、transpose 后 .view() 报错；第 15 篇 torch var 默认无偏、GELU 要指定 approximate="tanh"；第 17 篇 F.kl_div 参数顺序反、label_smoothing 与 ignore_index 要传对。第 15 篇给出这条线最便宜的自查——形状检查 dx.shape == x.shape、dw.shape == w.shape；第 19 篇把方法论推到系统题：”分块一定快”要测了再说。
| 概念 | 出现的篇 | 关系 |
|---|---|---|
| “和为 k 的子数组” | 01、02、03 | 01 前缀和 + 哈希；02 说明含负数为何不能窗口；03 含负数求最短用前缀和 + 单调队列 |
| 接雨水 | 02、03、06 | 02 双指针 \(O(1)\) 空间；03 单调栈按层算水；二维版用 06 的堆（Dijkstra 思路） |
| 第 K 大 / Top-K | 08、04、18 | 08 堆与快速选择；04 合并 K 链表是堆做 K 路归并；18 KNN 直接复用大小为 k 的堆 |
| 快慢指针 / Floyd | 02、04、01、07 | 02 原地分区；04 判环与入口证明；01 LC 287 把 nums[i] 当指针；07 同题值域二分 |
| 二分 | 07、11、13 | 07 唯一模板；11 LIS 的 tails 用 bisect_left；13 基于时间的键值存储用 bisect_right - 1 |
| 回溯 vs DP | 09、11、12 | 09 枚举所有方案；11 / 12 只问方案数或能否时用 DP（39 → 377 / 518、131 → 132、139 → 140） |
| 前缀和 | 01、05、13 | 01 数组版；05 树上版要撤销；13 树状数组让单点更新 + 前缀查询都 \(O(\log n)\) |
| Trie | 13、09 | 09 单词搜索每个单词一次 DFS；13 建 Trie 一次 DFS 匹配全部 |
| LRU | 13、19 | 13 哈希 + 双向链表；19 加锁、缓存穿透、分段锁 |
| softmax 的数值稳定 | 14、15、17 | 14 减最大值、log-softmax；15 CE 用 logits；17 BCE 恒等式、log_softmax |
| KV cache | 14、19 | 14 每 token 字节数与 GQA；19 paged 块分配、引用计数、COW |
| \(p - y\) 型梯度 | 15、18 | 15 softmax-CE 对 logits；18 逻辑回归 \(X^\top(p - y) / n\) 是二分类版 |
| 拒绝采样 | 16 | 投机解码是 LC 470 / 528 一类”用一个分布生成另一个分布”的 AI 版 |
四、常见误区
| 误区 | 为什么错 | 正确的说法 | 出处 |
|---|---|---|---|
| 子数组和等于 k 用滑动窗口 | 含负数时右扩和可能变小，窗口不单调 | 前缀和 + 哈希计数，先放 count[0] = 1 |
第 01 篇 |
| 滑动窗口最大值用堆 | 滑出的元素不在堆顶，只能懒删除，\(O(n \log k)\) | 单调双端队列 \(O(n)\)，队尾弹掉永不再当最值者 | 第 03 篇 |
| 验证 BST 比较父子节点即可 | 约束是全局的，[5, 4, 6, null, null, 3, 7] 局部成立全局不成立 |
递归带上下界，或中序严格递增 | 第 05 篇 |
| BFS 出队时标记 visited | 同一节点被多个前驱重复入队，最坏 \(O(V^2)\) | 入队时标记，每个节点入队一次 | 第 06 篇 |
| 二分是”在有序数组里找一个值” | 那只是谓词 a[i] >= t 的特例 |
在单调谓词上找第一个真；数组有序只是特例 | 第 07 篇 |
| 第 K 大用最大堆 | 堆顶是最大值，无法 \(O(1)\) 判断新元素是否进前 K | 大小为 K 的最小堆，堆顶就是第 K 大 | 第 08 篇 |
| 剪枝能改变回溯的复杂度量级 | 最坏上界不变，只减少实际访问的节点 | 排列仍 \(O(n \cdot n!)\)；剪枝决定能否在时限内跑完 | 第 09 篇 |
tails 就是一个 LIS |
[2, 5, 1] 得 [1, 5]，不是子序列 |
只有长度是对的；tails[k] 是长度 \(k + 1\) 的最小末尾 |
第 11 篇 |
| 完全背包计数内外层可以交换 | 外层容量会把 1+2 与 2+1 分别计数 |
外层物品得组合数，外层容量得排列数（LC 377） | 第 12 篇 |
mask 填 0 或 -1e4 就够 |
0 经 softmax 仍有权重；fp16 下 -1e4 相对不够小 |
-inf 或 torch.finfo(dtype).min |
第 14 篇 |
| weight decay 加进梯度就是 AdamW | 那是 L2 正则，衰减项被 \(\sqrt{\hat{v}}\) 归一化 | 解耦：\(\lambda\theta\) 直接加在更新里 | 第 17 篇 |
| 矩阵乘法分块一定更快 | \(n = 512\) 时 3 MB 装进 16 MB L2，分块只加循环开销 | 先测再说；ikj 快 11 倍，分块 8 倍 | 第 19 篇 |
五、通关自测
A. 判断与计算（10 题）
-
整数数组 \(n \le 10^5\)、含负数，求和等于 \(k\) 的最长子数组长度。用哪个模式、复杂度多少、与”个数”版差在哪一行？
答案
前缀和 + 哈希，\(O(n)\) 时间 \(O(n)\) 空间（第 01 篇 LC 325）。含负数不能用窗口。与 LC 560 的差别：哈希存”前缀和首次出现的下标”而不是次数，
ans = max(ans, i - first[pre - k])，且不覆盖已有的键（保留最早的下标才最长）；初始first[0] = -1。 -
下面的两数之和有没有 bug？输入
[3, 2, 4]、target 6 返回什么？def two_sum(nums, target): seen = {} for i, x in enumerate(nums): seen[x] = i if target - x in seen: return [seen[target - x], i]答案
有：先存再查。\(i = 0\)、\(x = 3\) 时先写入
seen[3] = 0，再查6 - 3 = 3命中自己，返回[0, 0]；正确答案是[1, 2]。第 01 篇模板 1 的顺序是”先查再存”，保证配对的是之前的元素，target = 2x时不会自配对。 -
滑动窗口最大值里把队首过期判断写成
if dq[0] < i - k，输入nums = [5, 1, 1, 1]、\(k = 2\) 输出什么？答案
[5, 5, 1]，错误（正确[5, 1, 1]）。\(i = 2\) 时窗口是[1, 1]（下标 1、2），下标 0 已滑出，正确条件dq[0] <= i - k即0 <= 0会弹掉它；写成<时0 < 0不成立，队首仍是下标 0，输出 5。窗口[i - k + 1, i]的左端是i - k + 1，下标<= i - k都过期（第 03 篇模板 2）。 -
数组 \(n = 10^4\)、值域 \(10^9\)，求所有数对绝对差中第 \(k\) 小的（LC 719）。用哪个模式、谓词是什么、复杂度多少？
答案
值域二分（第 07 篇）：排序后在
[0, max - min]上first_true(lambda x: count_le(x) >= k)；count_le(x)用双指针数”差 \(\le x\) 的数对个数”，\(O(n)\)（对每个右端点，左端点只往右走）。总 \(O(n \log n + n \log V)\)。信号是”值域 \(10^9\)、答案是一个整数、直接枚举数对 \(O(n^2) = 10^8\) 太慢”。答案一定在某个真实的差值上，理由与 LC 378 相同。 -
两个回溯任务：（a）\(n = 12\) 的全排列；（b）\(n = 22\) 的全部子集。按”一秒约 \(10^8\) 次简单操作”估算，哪个能跑完？
答案
（a）叶子 \(12! = 479{,}001{,}600 \approx 4.8 \times 10^8\)，每个拷贝 \(O(n)\)，总约 \(5.7 \times 10^9\)——跑不完。（b）叶子 \(2^{22} = 4{,}194{,}304 \approx 4.2 \times 10^6\)，乘 \(n = 22\) 约 \(9 \times 10^7\)——勉强可以。第 09 篇的复杂度表：排列 \(O(n \cdot n!)\)、子集 \(O(n \cdot 2^n)\)；总纲的规模表：\(n \le 20\) 才该想指数级枚举。\(n = 12\) 的排列题若只问个数或某种最优，应改 DP / 状压 DP。
-
GPT-2 medium：\(D = 1024\)、\(L = 24\)、\(V = 50257\)、\(T_{\max} = 1024\)、带 bias、tied。用第 15 篇的公式算每层参数与总参数。
答案
每层 \(12D^2 + 13D = 12{,}582{,}912 + 13{,}312 = 12{,}596{,}224\)；24 层 \(302{,}309{,}376\)；嵌入 \(50257 \times 1024 = 51{,}463{,}168\)；位置 \(1024 \times 1024 = 1{,}048{,}576\)；最后一个 LN \(2 \times 1024 = 2{,}048\)。总计 \(354{,}823{,}168 \approx 355\)M。嵌入占 14.5%——比 small 的 31% 低，符合”\(D\) 变大后 \(12D^2 L\) 迅速主导”。
-
一层 attention、\(D = 1024\)、\(T = 4096\)、一个序列：投影 FLOPs 与 \(QK^\top\) + \(PV\) 的 FLOPs 各是多少？后者是前者的几倍？
答案
第 14 篇：投影 \(8TD^2 = 8 \times 4096 \times 1024^2 \approx 3.4 \times 10^{10}\)；attention \(4T^2D = 4 \times 4096^2 \times 1024 \approx 6.9 \times 10^{10}\)，是投影的 2 倍——因为 \(T = 4D\)，而临界点是 \(T = 2D\)。注意与第 15 篇的 \(T > 6D\) 不矛盾：那是 attention 项对整层线性项（含 FFN 的 \(24D^2\)）的比较。
-
某模型 \(L = 40\)、\(H_{kv} = 4\)、\(d = 128\)，KV 用 fp8（1 字节）。每 token 的 KV cache 多少字节？32K 上下文一条序列占多少？
答案
\(2 \times 40 \times 4 \times 128 \times 1 = 40{,}960\) B = 40 KB / token；\(32768\) token 是 \(1{,}342{,}177{,}280\) B = 1.25 GB。公式来自第 14 篇 \(2 L H_{kv} d \cdot \text{bytes}\)；GQA 的 \(H_{kv}\) 与量化的字节数是两个独立的缩小因子。
-
PPO clipped objective，\(\epsilon = 0.2\)、优势 \(A = -1\)。（a）\(r = 0.7\) 时单样本 loss 是多少、对 \(r\) 的梯度是多少？（b）\(r = 0.9\) 呢？
答案
loss \(= -\min(rA, \text{clip}(r, 0.8, 1.2) \cdot A)\)。（a）\(rA = -0.7\)，clip 项 \(0.8 \times (-1) = -0.8\)，min 取 \(-0.8\)，loss \(= 0.8\)；取到的是 clip 项（常数），梯度 0——坏动作的概率已经压得够低，不再惩罚继续减小。（b）\(rA = -0.9\)，clip 项 \(-0.9\)，loss \(= 0.9\)，取原始项，梯度 \(-A = 1 > 0\)，推 \(r\) 变小。第 17 篇的四种情况图里的下半部分。
-
ring allreduce，\(N = 8\) 个 rank、向量 \(V = 1\) GB。每个 rank 总共发送多少数据、多少个串行步？换成参数服务器，server 要接收多少？
答案
每 rank 发送 \(2\frac{N - 1}{N}V = 2 \times \frac{7}{8} \times 1 = 1.75\) GB；reduce-scatter 与 all-gather 各 7 步，共 14 个串行步。参数服务器的 server 入流量 \(N \cdot V = 8\) GB。\(N\) 再翻倍时每 rank 发送量趋近 2 GB 不再增长，但步数翻倍——所以第 19 篇说 NCCL 小消息用 tree、大消息用 ring。
B. 跨篇综合（5 题）
-
\(n\) 个位置（坐标可到 \(10^9\)）放 \(m\) 个球，最大化任意两球的最小距离（LC 1552）。给出算法、判定函数与复杂度，并说明用了哪两篇的什么。
答案
第 07 篇的答案二分：”最大的 \(x\) 使得能放下 \(m\) 个球且两两距离 \(\ge x\)“——\(x\) 越大越难，谓词是”真真真假假假”，对
not ok用first_true再减 1，范围[1, max - min + 1)。第 08 篇的贪心判定与交换论证：排序后第一个球放最左，之后每个位置只要与上一个球距离 \(\ge x\) 就放——”能放就放”得到的球数最多，任何放法的第 \(t\) 个球都不早于贪心的第 \(t\) 个球（与第 07 篇 LC 410 的证明同型）。复杂度 \(O(n \log n + n \log V)\)。 -
二维接雨水（LC 407）：\(m \times n\) 的高度矩阵能接多少水。用哪两篇的结论拼出解法？
答案
第 02 篇一维接雨水的结论”矮的一侧决定上限、可以先结算”推广到二维：水位由四周边界中最矮的那个决定。第 06 篇的 Dijkstra 结构：把所有边界格子按高度放进最小堆，每次弹出最矮的边界格 \(h\)，向内看它的未访问邻居——邻居比 \(h\) 矮就接 \(h - \text{height}\) 的水，然后以 \(\max(h, \text{height})\) 作为新边界入堆；visited 在入堆时标记。每个格子入堆一次，\(O(mn \log(mn))\)。正确性与 Dijkstra 的”弹出即定终值”同源：弹出的是当前最矮的边界，它的水位不会再被更矮的边界改写。
-
给一个数字串（如
"228"）和一本词典，返回词典里所有能用手机九键拼出的单词（T9 联想）。怎样组合第 09 篇与第 13 篇？答案
第 09 篇 LC 17 的多阶段笛卡尔积：每层一个数字、候选是它对应的 3–4 个字母，不剪枝是 \(O(4^n)\)。第 13 篇的 Trie：把词典建成 Trie，回溯时带着当前 Trie 节点走——该字母不是当前节点的孩子就整支剪掉；走完最后一个数字时
node.end为真才收集。复杂度从 \(4^n\) 变成受 Trie 大小限制的路径数，与第 13 篇 LC 212”沿 Trie 走一次 DFS 匹配所有单词”是同一个想法，只是候选从网格四邻换成了数字对应的字母。追问”要求前缀联想（输入未结束）”时收集子树里所有end。 -
跳跃游戏 VI（LC 1696）：从下标 0 出发，每步最多向前跳 \(k\) 格，得分是经过的
nums之和，求最大得分，\(n \le 10^5\)。用哪两篇？答案
第 11 篇五步法：
f[i]= 到达 \(i\) 的最大得分，最后一步从 \(j \in [i - k, i - 1]\) 跳来，f[i] = nums[i] + max(f[i-k..i-1])，答案f[n-1]——朴素 \(O(nk)\)，\(n = 10^5\) 会超时。第 03 篇的单调队列把”窗口 \([i - k, i - 1]\) 上的最大值”降到均摊 \(O(1)\)：队列存下标、f值递减，新的f[i]入队前弹掉队尾比它小的，队首下标 \(< i - k\) 时弹掉，队首就是窗口最大。总 \(O(n)\)。第 03 篇题单里这道题的一句提示正是”DP + 单调队列优化窗口最大值”。 -
Llama-3-8B（bf16，每 token KV 128 KB）服务一个 100 token 的 prompt、采 4 个回答各 20 token，
block_size = 16。不共享时 KV 占多少显存？用第 19 篇的 paged + COW 占多少？答案
第 14 篇：每 token 128 KB，一个 16 token 的块 2 MB。不共享：4 条序列各 120 token，\(4 \times 120 \times 128\) KB = 60 MB。第 19 篇：prompt 100 token 占 7 块（6 满块 + 1 块 4 个 token），fork 三次后 4 条序列共享这 7 块、第 7 块
ref = 4。每条追加第一个 token 时检查最后一块：前三条看到ref > 1各 COW 一块，第四条看到ref == 1原地写；之后各自的第 7 块填到 16 个 token 再各申请 1 块放剩下 8 个。合计 \(6 + 4 \times 2 = 14\) 块 = 28 MB，前缀 96 个 token 只存一份；代价是内部碎片——每条序列最后一块只用了一半。
C. 面试题（8 题）
-
手写 LRU 缓存，
get/put都 \(O(1)\)。答案
思路要点：(1) 哈希表存
key → 节点做 \(O(1)\) 定位；(2) 双向链表按使用顺序排列，头部最近、尾部最久，摘中间节点要改前驱所以必须双向；(3) 两个哨兵head、tail免去空链 / 头尾特判；(4) 节点里存key，淘汰尾节点时才能从哈希表删掉它；(5)get命中与put更新都要”摘下再插头”。关键代码（
Node有key、val、prev、next）：class LRUCache: def __init__(self, cap): self.cap, self.map = cap, {} self.head, self.tail = Node(), Node() self.head.next, self.tail.prev = self.tail, self.head def _unlink(self, n): n.prev.next, n.next.prev = n.next, n.prev def _push_front(self, n): n.prev, n.next = self.head, self.head.next self.head.next.prev = self.head.next = n def get(self, k): if k not in self.map: return -1 n = self.map[k] self._unlink(n) self._push_front(n) return n.val def put(self, k, v): if k in self.map: self._unlink(self.map.pop(k)) elif len(self.map) == self.cap: lru = self.tail.prev self._unlink(lru) del self.map[lru.key] self.map[k] = n = Node(k, v) self._push_front(n)追问方向：换成单向链表哪一步做不到 \(O(1)\)；
OrderedDict/LinkedHashMap底层是什么；线程安全怎么做、get为什么也要锁（第 19 篇）；加过期时间；LFU 怎么改（第 13 篇频次桶 +min_freq）。好答案与一般答案的区别：一般答案能写出来但用
if堆叠处理头尾；好答案先画结构图、用哨兵统一所有情况，并主动说出”节点存 key 是为了淘汰时删哈希”。 -
手写带 causal mask 的 multi-head attention（NumPy），并说明每一步的形状。
答案
思路要点：(1)
x @ w_qkv得(B, T, 3D)后 split；(2)reshape(B, T, H, d)再transpose(0, 2, 1, 3)得(B, H, T, d)——先 reshape 再 transpose，反过来数全错；(3)q @ kᵀ / √d得(B, H, T, T)，下三角外填 \(-\infty\)，softmax 减最大值；(4)@ v得(B, H, T, d)，transpose 回(B, T, H, d)再 reshape(B, T, D)，最后@ w_o；(5) 参数 \(4D^2\)，多头不增加参数。关键代码：
def softmax(x): e = np.exp(x - x.max(-1, keepdims=True)) return e / e.sum(-1, keepdims=True) def mha(x, w_qkv, w_o, H): B, T, D = x.shape d = D // H q, k, v = np.split(x @ w_qkv, 3, axis=-1) # 各 (B, T, D) q, k, v = (t.reshape(B, T, H, d).transpose(0, 2, 1, 3) for t in (q, k, v)) s = q @ k.transpose(0, 1, 3, 2) / np.sqrt(d) # (B, H, T, T) s = np.where(np.tril(np.ones((T, T), dtype=bool)), s, -np.inf) # causal out = softmax(s) @ v # (B, H, T, d) return out.transpose(0, 2, 1, 3).reshape(B, T, D) @ w_o追问方向：为什么除 \(\sqrt{d}\)；mask 为什么不能用 0；一行全 mask 会怎样；改成 GQA 在哪一步
repeat；写推理时的 KV cache、增量解码为什么不用 mask；FLOPs \(8TD^2 + 4T^2D\) 何时 attention 项占主导；怎么和nn.MultiheadAttention对拍（权重转置、attn_mask语义取反）。好答案与一般答案的区别：一般答案写出公式；好答案每一行都能说出形状、解释先 reshape 再 transpose 的内存原因，并能顺着写出 online softmax。
-
数据流的中位数：支持
add_num与find_median。答案
思路要点：(1) 大顶堆
small存较小的一半、小顶堆large存较大的一半；(2) 不变量：small全部 \(\le\)large全部，且small的大小等于large或多一个；(3) 插入固定三步：先进small，再把small的最大倒到large，large多了就倒回一个——两次固定操作保证不变量，只剩一个方向的平衡判断；(4) 每次 \(O(\log n)\)，查询 \(O(1)\)；(5) Python 最大堆存负数。关键代码：
class MedianFinder: def __init__(self): self.small, self.large = [], [] # 大顶堆（存负数）/ 小顶堆 def add_num(self, x): heapq.heappush(self.small, -x) heapq.heappush(self.large, -heapq.heappop(self.small)) if len(self.large) > len(self.small): heapq.heappush(self.small, -heapq.heappop(self.large)) def find_median(self): if len(self.small) > len(self.large): return float(-self.small[0]) return (-self.small[0] + self.large[0]) / 2追问方向：滑动窗口中位数（懒删除或有序表）；数据范围 0–100 时用计数数组；99% 的数在 0–100、1% 极大时怎么混合；第 K 大的数据流版（大小为 K 的最小堆）；快速选择为什么不适合流。
好答案与一般答案的区别：一般答案”比
small顶小就进small否则进large再平衡”，分支多易错；好答案用两次固定操作维持不变量，并能说出为什么这样最少分支。 -
K 个一组反转链表，\(O(1)\) 额外空间，不足 \(k\) 的尾部保持原样。
答案
思路要点：(1) 哑节点让第一组与后面的组同一段代码；(2) 每轮先从
group_prev探 \(k\) 步找kth，不够就返回；(3) 三指针反转这一组，但prev的初值设为group_next = kth.next——反转后组尾自动接上下一组，不必再找尾；(4)group_prev.next = kth，group_prev前进到原组头（现在的组尾）；(5) 走查用[]、[1]、[1, 2]与k恰好整除 / 不整除。关键代码：
def reverse_k_group(head, k): dummy = group_prev = ListNode(0, head) while True: kth = group_prev for _ in range(k): kth = kth.next if not kth: return dummy.next # 不足 k 个，结束 group_next = prev = kth.next cur = group_prev.next while cur is not group_next: # 反转这一组 cur.next, prev, cur = prev, cur, cur.next group_prev.next, group_prev = kth, group_prev.next追问方向：递归写法与它的 \(O(n / k)\) 栈；不足 \(k\) 也反转怎么改；两两交换是 \(k = 2\) 的特例；区间反转（头插法）；Python 一行多重赋值为什么顺序安全、Java 为什么必须临时变量。
好答案与一般答案的区别：一般答案反转后再走一遍找组尾去接下一组，代码失控；好答案用
prev = group_next的初值让接口自动完成，并主动说出边界走查用哪三个输入。 -
手写 top-k / top-p / temperature 采样，并解释 top-p 的截断边界。
答案
思路要点：(1) 顺序：temperature 除 logits → softmax → top-k → top-p → 重归一化 → 采样；temperature 改分布形状所以在 softmax 前，截断砍概率尾巴所以在后；(2)
temperature == 0单独分支返回 argmax 避免除零；(3) top-p 按概率降序累加，”在这个元素之前累计已经 \(\ge p\)“的元素及其之后全部丢，首个越界项保留——否则top_p = 0.5、首项 0.6 时一个不剩；(4) 截断后必须重归一化，否则np.random.choice报和不为 1；(5) top-k 固定个数、top-p 自适应个数、min-p 相对阈值对”一个很确定 + 长尾”的分布更稳。关键代码：
def sample_logits(logits, temperature=1.0, top_k=0, top_p=1.0, rng=None): if temperature == 0: return int(logits.argmax()) probs = softmax(logits / temperature) if 0 < top_k < len(probs): kth = np.sort(probs)[-top_k] probs = np.where(probs >= kth, probs, 0.0) if top_p < 1.0: order = np.argsort(-probs) cum = np.cumsum(probs[order]) probs[order[cum - probs[order] >= top_p]] = 0.0 # 之前累计已 >= p 的：丢 probs = probs / probs.sum() return int(rng.choice(len(probs), p=probs))追问方向：repetition penalty 为什么正除负乘；beam search 为什么在 log 域相加、长度归一化、beam 大一定好吗；
probs = [0.6, 0.25, 0.1, 0.05]在top_p = 0.85下留几个（两个）；投机解码的接受规则与它为什么无偏；约束解码怎样把不合法 token 置 \(-\infty\)。好答案与一般答案的区别：一般答案能写 top-k；好答案说清 temperature 与截断的先后为什么不能换、top-p 边界差一个元素就是另一个算法，并给出 HF 实现的同一语义（
sorted_indices_to_remove右移一位）。 -
不用框架，写 softmax + 交叉熵的前向与反向，再用它训练一个两层 ReLU 网络一步。
答案
思路要点：(1)
loss = -mean(log p[y])，log_softmax写成 \(x - \text{logsumexp}(x)\) 不下溢；(2) 对 logits 的梯度是(p - onehot) / N——\(\log p_y = z_y - \log\sum e^{z_k}\) 求导，softmax 雅可比与 \(-1 / p_y\) 约掉；(3) Linear 反向dx = dout @ w.T、dw = x.T @ dout、db = dout.sum(0)，形状自查dw.shape == w.shape；(4) ReLU 的导数用激活前的z1判断；(5) 前向按层存中间量，反向严格倒序。关键代码：
def softmax_ce(logits, y): m = logits.max(-1, keepdims=True) lp = logits - m - np.log(np.exp(logits - m).sum(-1, keepdims=True)) N = len(y) loss = -lp[np.arange(N), y].mean() d = np.exp(lp) d[np.arange(N), y] -= 1 # p - onehot return loss, d / N def train_step(X, y, W1, b1, W2, b2, lr): z1 = X @ W1 + b1 a1 = np.maximum(z1, 0) # 前向 loss, dlogits = softmax_ce(a1 @ W2 + b2, y) dW2, db2 = a1.T @ dlogits, dlogits.sum(0) # 反向：倒序 dz1 = (dlogits @ W2.T) * (z1 > 0) dW1, db1 = X.T @ dz1, dz1.sum(0) W1 -= lr * dW1 b1 -= lr * db1 W2 -= lr * dW2 b2 -= lr * db2 return loss追问方向：loss 用
sum代替mean梯度怎么变、对 SGD 与 Adam 各有什么影响；He 初始化的方差 \(\sqrt{2 / \text{in}}\)；LayerNorm 的反向两个修正项从哪来；训练 FLOPs 为什么是前向的 3 倍；写一个最小自动求导时梯度为什么要+=。好答案与一般答案的区别：一般答案背 \(p - y\)；好答案能推导它、写对
/ N、用形状检查自证每一行，并说出框架把 softmax 与 CE 合成一个算子的原因。 -
用一把锁和条件变量写一个有界阻塞队列，支持多生产者多消费者。
答案
思路要点：(1) 一把锁 + 两个条件变量
not_full、not_empty共用这把锁；(2) 等待写成while：被唤醒到重新拿到锁之间条件可能已被别的线程改变，POSIX 还允许虚假唤醒；(3)put只叫消费者、get只叫生产者——只用一个条件变量可能叫醒错误的一方甚至死锁；(4) 每次只放 / 取一个元素用notify，条件复杂时notify_all；(5) 关闭用哨兵，每个消费者一个。关键代码：
class BoundedQueue: def __init__(self, cap): self.items, self.cap = collections.deque(), cap lock = threading.Lock() self.not_full, self.not_empty = threading.Condition(lock), threading.Condition(lock) def put(self, x): with self.not_full: while len(self.items) >= self.cap: # while，不是 if self.not_full.wait() self.items.append(x) self.not_empty.notify() def get(self): with self.not_empty: while not self.items: self.not_empty.wait() x = self.items.popleft() self.not_full.notify() return x追问方向：
put里误写not_full.notify()会怎样（死锁）；在它上面写线程池——worker 异常怎么传回 Future、关闭为什么每个 worker 一个None；Python 的 GIL 之下锁为什么仍然需要、CPU 密集为什么要进程池；死锁的四个条件与预防。好答案与一般答案的区别：一般答案写
if加notify_all碰运气；好答案能画出”A 被唤醒但 B 先拿到锁取走元素”的时序解释while，并说清两个条件变量各叫各的。 -
运送包裹的最低运力（LC 1011）/ 分割数组的最大值（LC 410）：\(n \le 5 \times 10^4\)，包裹重量到 \(500\)，\(D\) 天内送完的最小运力。
答案
思路要点：(1) 识别：最优化难、判定易、判定对答案单调——答案二分；(2) 范围
[max(w), sum(w) + 1)：下界是理论最小（最重的包裹必须能装），上界是一定可行的值加一；(3) 判定ok(cap)：贪心从左往右装、装不下开新段，段数 \(\le D\)；”能装就装”段数最少，提前开段只会让后面更挤（归纳证明）；(4)first_true模板：[lo, hi)、真收hi = mid、假收lo = mid + 1；(5) 复杂度 \(O(n \log V)\)，Java 求和用long。关键代码：
def first_true(lo, hi, pred): while lo < hi: mid = (lo + hi) // 2 if pred(mid): hi = mid else: lo = mid + 1 return lo def ship_within_days(weights, D): def ok(cap): parts, cur = 1, 0 for w in weights: if cur + w > cap: parts, cur = parts + 1, 0 cur += w return parts <= D return first_true(max(weights), sum(weights) + 1, ok)追问方向：为什么
mid向下取整不会死循环；”最大的 \(x\) 使得……”怎么改（对not ok找第一个真再减 1）；输出分割方案（用最终 cap 再跑一遍贪心）；DP 解 \(O(n^2 k)\) 为什么不选；同构题——吃香蕉、制作花束、两球磁力。好答案与一般答案的区别：一般答案对着
lo <= hi与mid ± 1现场纠结；好答案先说”谓词单调、区间左闭右开”，再用同一个first_true写完，并能证明贪心判定是对的。
D. 掌握判据
| 水平 | 表现 |
|---|---|
| 读过 | 能说出十九篇各讲哪种模式或哪个组件；知道前缀和、单调栈、first_true、大小为 K 的堆、KV cache、DPO 这些名词 |
| 掌握 | A 组能不翻书做对 8 题以上；B 组能说出每题用了哪两篇的什么；拿到一道没见过的中等题能在五分钟内说出模式、模板与复杂度，写完能用最小边界输入走查；AI 手撕题能写出实现并说出对拍方法与自检基准值 |
| 能教人 | C 组每题能给出全部要点并预判追问；能解释每个反直觉结论为什么成立（max_freq 不减也对、tails 不是 LIS、增量解码不需要 mask、分块反而慢、拒绝后要从残差重采）；能把一道题的两种解法与各自适用场景讲清 |
通关标准：A 组至少 8 题、B 组至少 4 题、C 组每题能说出一半以上要点并在 15 分钟内写出关键代码。没过的部分回到第二章对应篇的”必记”，再回该篇正文；然后按总纲的练法——每篇题单的每道题做两遍，第一遍限时 30 分钟独立做，第二遍一周后不看资料重写，卡点集中的模式回来重读。
六、下一步
这个系列只帮你把已经会的东西在面试里稳定地写出来，不教你学会一个方向。系列边界之外该去哪：
- 系统学习路线见《AI 全栈学习地图》，以及它下面的《AI 算法工程师学习地图》与《AI-Infra 工程师学习地图》——本系列不属于任何一张地图。
- Python 与 Java / C++ 的语言机制（GIL、内存模型、对象模型）不在本系列，见 Infra 地图的《Python 在 AI-Infra：从语言机制到生产交付》与《C++ 在 AI-Infra：从对象模型到算子扩展》。
- 模型组件”为什么这样设计”的原理——反向传播、归一化、优化器在《深度学习基础：从反向传播到残差》；attention 变体、KV cache 的账、参数量与算量在《Transformer 与 LLM：结构、算量与数值》；DPO、PPO、GRPO 的推导与评测在《后训练：从 SFT 到可验证奖励》。后六篇只讲”怎么正确地写出来”，推导与设计动机在这三个系列。
- 不讲的部分：困难难度的竞赛型题目（后缀自动机、网络流、FFT、平衡树）、系统设计面试、语言特性问答。
回到总纲：《面试手撕代码：从 LeetCode 中等题到 Transformer 组件》——两张图（题面到模式、四十分钟流程）与四条阅读路径都在那里。
-
三组。算法篇：看到题面里的信号能说出模式、模板与复杂度目标（哈希换循环、单调性换空间、弹出即结算、哑节点与快慢指针、递归三要素、visited 放哪、单调谓词、按什么键排序、做选择 → 递归 → 撤销、字符串特有技巧、状态定义五步法、倒序 = 一次 / 正序 = 无限、给瓶颈步骤加索引）；AI 篇：能从零写出 attention、GPT block 与三个算子的反向、BPE 与采样、DPO / GAE / PPO / AdamW / LoRA、k-means / AUC / conv2d，并说出对拍方法；Infra 篇：锁保护什么、条件变量为什么
while、allreduce 每 rank 发多少、paged KV 为什么 COW。详见第二章。 ↩ -
count[0] = 1；first_true的四条性质（左闭右开、lo < hi、真收hi = mid、mid向下取整）；排列 \(O(n \cdot n!)\)、子集 \(O(n \cdot 2^n)\)；\(n \le 20\) 想回溯、\(10^5\) 排除 \(O(n^2)\)、\(10^9\) 想值域二分；Floyd \(a = (k - 1)c + (c - b)\)；单调队列 \(O(n)\) 对堆 \(O(n \log k)\)；attention 参数 \(4D^2\)、FLOPs \(8TD^2 + 4T^2D\)、每 token KV \(2 L H_{kv} d \cdot \text{bytes}\)（Llama-3-8B 128 KB）；一层 \(12D^2\)、前向 \(2N\)、训练 \(6N\)、GPT-2 small 124,439,808；CE 梯度 \(p - y\)；DPO 初值 \(\ln 2\)；接受率 \(1 - \text{TV}(p, q)\)；AUC = 正样本秩和 \(- n_+(n_+ + 1) / 2\) 除 \(n_+ n_-\)；ring allreduce \(2\frac{N - 1}{N}V\)；ikj 比 ijk 快 11 倍。详见第一章、第三章。 ↩ -
用第五章的三段自测：A 组 10 题判断与计算（至少 8 题）、B 组 5 题跨篇综合（至少 4 题）、C 组 8 道手撕题（每题说出一半以上要点、15 分钟内写出关键代码）；D 组的表给出”读过 / 掌握 / 能教人”三级的表现。更硬的判据是总纲的练法：每篇题单的题一周后不看资料能重写出来才算过。详见第五章。 ↩
本文由 arganzheng 创作，采用 CC BY 4.0 许可协议。在保留原文作者、署名以及完整原文链接（https://arganzheng.life/coding-interview-series-recap-and-self-test.html）的前提下，欢迎各种形式的转载、翻译或商业引用。
COMMENTS
评论存放在 GitHub Discussions， 用 GitHub 账号登录即可发表，支持 Markdown。 想针对正文某句话说？选中那段文字，点浮出的「评论」即可划线评论；觉得哪里写错了，发表时勾上「同时提交 Issue」。 有人回复你时 GitHub 会按你的通知设置发邮件，不用守在这里。