阿甘的博客 | Arganzheng's Blog

面试手撕代码（17）：手撕损失函数与训练算法

Losses and Training Algorithms by Hand: CE, KL, InfoNCE, DPO, PPO/GAE, GRPO, AdamW, Schedules and LoRA

“写出 DPO 的损失函数”“PPO 的 clipped objective 是什么”“AdamW 一步更新怎么算”——这些题是算法岗面试的第二梯队手撕题，考的是能不能把论文里的公式落成十行正确的代码。它们的共同难点是细节：label smoothing 平滑的是哪个分布、KL 的两个参数谁是 target、DPO 的四个 log 概率怎么组合、GAE 的递推从哪一端开始、AdamW 的 weight decay 为什么不进动量、LoRA 的 B 为什么初始化为零。这一篇每个组件给出实现、与 PyTorch（或 trl 的公式）对拍、以及面试官会追的一两个”为什么”。推导与动机在算法地图：损失与优化器见深度学习基础（03），PPO / GRPO 见后训练（03）...

Posted by arganzheng | December 18, 2025

面试手撕代码（16）：手撕 tokenizer 与解码

Tokenizer and Decoding by Hand: BPE, Sampling, Beam Search, Reservoir Sampling and Speculative Acceptance

模型的两端——文本进去之前的 tokenizer、logits 出来之后的解码——是面试里”看起来简单、写起来处处是坑”的手撕题。BPE 的训练循环十几行，但”合并的优先级怎么定”“编码时按什么顺序应用 merge”两个细节决定了写出来的东西对不对；top-p 采样的截断位置差一个元素就是另一个算法；beam search 里”完成的序列怎么处理”“长度归一化”是必问；投机解码的接受-拒绝规则一行公式，但要能证明”最终分布等于目标分布”。这一篇把这五组东西从零写出来，每个都有数值验证。原理与取舍在算法地图里：分词见预训练（01），解码策略见高效推理（01），投机解码见（02）。本篇要回答的核心问题是： BPE 训练时”合并最频繁的相邻对”如何做到确定...

Posted by arganzheng | December 17, 2025

面试手撕代码（15）：手撕 Transformer block 与反向传播

Transformer Block and Backprop by Hand: LayerNorm, SwiGLU, Parameter Counting, Gradients and Micrograd

上一篇写完 attention，这一篇把它装进一个完整的 Transformer block，再往下挖一层：反向传播。面试里这两块常常连着问——”写一个 GPT block”之后是”LayerNorm 的反向怎么算”“交叉熵对 logits 的梯度是什么”“不用框架写一个两层网络的训练”，最后可能到”实现一个最小的自动求导”。这些题考的是对链式法则的操作性理解：每个算子的局部导数是什么、怎么和上游梯度相乘、形状怎么对上。参数量与 FLOPs 的口算也在这里——它们是面试里最容易拿分的”算术题”。原理与推导在算法地图里：反向传播见深度学习基础（01），归一化与残差见（02），参数量与算量见 Transformer 与 LLM（01）、（02）。本篇要回答的核心...

Posted by arganzheng | December 16, 2025

面试手撕代码（14）：手撕 attention 家族

Attention from Scratch: Softmax, SDPA, Multi-Head, GQA, RoPE, KV Cache and Online Softmax

“手写一个 multi-head attention”是 AI 岗面试的第一道手撕题，几乎每家都考。它筛的不是”会不会调 nn.MultiheadAttention“，而是四件事：形状（reshape 和 transpose 的顺序为什么是那样）、数值（softmax 为什么减最大值、mask 为什么用 \(-\infty\) 而不是 0）、变体（GQA 在哪一步复制、RoPE 旋转的是哪两个维度）、推理（KV cache 缓存的是什么、增量解码为什么不用 mask）。追问会一直深入到 online softmax——FlashAttention 一趟分块的核心。这一篇把这条链从零写完，每一步都和 PyTorch 的参考实现对拍。原理与设计动机不在这里展开：at...

Posted by arganzheng | December 15, 2025

面试手撕代码（13）：设计题与数据结构实现

Design Problems: LRU, LFU, Trie, O(1) Random Set and Fenwick Tree

设计题的题面是”实现一个类，支持这几个操作，每个操作 O(1) / O(log n)”。它考的不是算法，而是组合数据结构：单一结构做不到的复杂度，用两个结构互相索引来做到——LRU 是哈希表索引双向链表的节点，LFU 再加一层频次桶，O(1) 随机删除是数组配上”值到下标”的哈希，Trie 是把公共前缀共享的 26 叉树。这类题代码量比算法题大（三五十行），面试官看的是结构清不清楚、每个操作的每一步是不是都 O(1)、边界（容量为 0、key 已存在、删最后一个）有没有处理。这一篇五道主讲题是最高频的五个设计题，每道都先画结构图再写。本篇要回答的核心问题是： LRU 为什么必须是哈希表 + 双向链表，单用其中一个为什么做不到 O(1)？1 LFU 怎样在...

Posted by arganzheng | December 14, 2025

面试手撕代码（12）：动态规划（二）——背包、区间、状态机、树形

Dynamic Programming II: Knapsack, Interval, State Machine and Tree DP

上一篇的 DP 状态是”前 \(i\) 个”或”两个前缀”，这一篇是四种形状更特殊的状态：背包（前 \(i\) 个物品、容量 \(c\)——”选不选”的问题几乎都是它，包括分割等和子集、目标和、零钱兑换 II）、区间（区间 \([i, j]\) 的答案由更短的区间拼出——戳气球、最长回文子序列）、状态机（每个时刻处于有限几种状态之一——买卖股票全家族）、树形（子树的答案拼出父节点——打家劫舍 III）。再加两道字符串匹配（正则、通配符）——它们是二维 DP 里最容易写错转移的。这些题面试频率比第一篇低，但一旦考到区分度很高。本篇要回答的核心问题是： 0/1 背包和完全背包的一维写法只差”容量正序还是倒序”，为什么？1 区间 DP 的”枚举最后一个被处理的...

Posted by arganzheng | December 13, 2025

面试手撕代码（11）：动态规划（一）——线性与二维

Dynamic Programming I: Define the State, Then the Rest Follows

动态规划是面试里最让人紧张的一类题，但中等难度的 DP 只有两种形状：一维（状态是”前 \(i\) 个元素”或”到第 \(i\) 个位置”）和二维（状态是”前 \(i\) 个与前 \(j\) 个”或”格子 \((i, j)\)“）。这一篇讲这两种，下一篇讲背包、区间、状态机、树形。DP 题的难点从来不在代码——代码几乎都是两层循环加一个 max / min——而在状态的定义：定义对了转移是显然的，定义错了怎么凑都不对。所以这一篇先讲一套”五步法”，再用七道主讲题把它练熟。本篇要回答的核心问题是：怎样从题面推出 DP 的状态定义，而不是靠背题？1 最长递增子序列的 \(O(n \log n)\) 解法里 tails 数组存的是什么？2 编辑距离的三种操作...

Posted by arganzheng | December 12, 2025

面试手撕代码（10）：字符串

Strings: Palindromes, KMP, Parsing, Big Numbers and Custom Ordering

字符串题一半是前面几篇模式的字符版（滑动窗口、哈希计数、栈），另一半是这一篇要讲的字符串特有的技巧：回文的中心扩展与 Manacher、子串匹配的 KMP 失配表、手写解析（atoi）、大数的竖式运算、以及”拼起来最大”这类自定义排序。这些题代码都不长，但边界多——空串、前导零、符号、溢出、相等元素的排序稳定性——面试官正是靠这些边界筛人。本篇要回答的核心问题是：最长回文子串为什么中心扩展比区间 DP 更适合面试，Manacher 又改进了什么？1 KMP 的失配表 lps 到底存的是什么，为什么匹配失败时跳到 lps[k-1] 不会漏解？2 “拼接后最大的数”为什么排序比较器用 a+b 与 b+a 就是对的？3 一、识别信号 ...

Posted by arganzheng | December 11, 2025

面试手撕代码（09）：回溯

Backtracking: Choose, Recurse, Undo — and Prune

回溯是”枚举所有方案”的标准写法：排列、组合、子集、切分、棋盘放置。它的代码只有一个骨架——做选择、递归、撤销选择——所有题的差别只在三处：候选集合怎么定（从哪开始、能不能重复选）、怎么去重（排序后跳过同层相同值）、怎么剪枝（提前判断这条路不可能有答案）。这一篇把骨架和三处差别讲清，七组主讲题（排列 / 排列去重、子集 / 子集去重、组合总和 I / II、括号生成、回文切分、单词搜索、N 皇后）覆盖面试里能遇到的全部回溯形态。本篇要回答的核心问题是：排列、组合、子集三种题的递归参数差在哪里？1 “排序后跳过同层相同值”的去重为什么对排列要多加一个 not used[i-1] 条件？2 回溯的复杂度怎么估、剪枝能改变量级吗？3 一、识别信号 ...

Posted by arganzheng | December 10, 2025

面试手撕代码（08）：堆、Top-K、区间与贪心

Heaps, Top-K, Intervals and Greedy: Sort by the Right Key

这一篇把三类”看起来不同、写起来相似”的题放在一起：Top-K（第 K 大、前 K 个高频、数据流中位数）靠堆，区间（合并、插入、最少箭、会议室）靠按端点排序后一趟扫描，贪心（跳跃游戏、加油站、任务调度）靠一个能证明的局部最优选择。它们的共同点是——先决定按什么键排序或维护什么顺序，剩下的就是一趟循环。堆是”动态维护顺序”的工具；排序是”一次性确定顺序”；贪心是”证明这个顺序下的局部选择就是全局最优”。六道主讲题里，快速选择、双堆中位数、会议室 II 是面试的常客。本篇要回答的核心问题是：第 K 大用大小为 K 的最小堆还是快速选择？各在什么场景下更好？1 数据流中位数的两个堆怎样维持平衡、为什么每次插入要”先进一个堆再倒到另一个”？2 会议室 II ...

Posted by arganzheng | December 9, 2025

Arganzheng's Blog