阿甘的博客 | Arganzheng's Blog

面试手撕代码（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

面试手撕代码（07）：二分——只有一个模板

Binary Search: One Template, First Position Where the Predicate Holds

二分是”人人都会、人人都写错”的算法：lo <= hi 还是 lo < hi、mid 还是 mid + 1、返回 lo 还是 hi，每次都要现场想一遍。根源在于把二分当成”在有序数组里找一个值”——那只是它最窄的用法。二分的本质是：在一个”假假假……真真真”的单调谓词序列上，找第一个真的位置。用这一个定义写一个 first_true(lo, hi, pred)，所有二分题——找值、找边界、旋转数组、找峰值、”答案二分”、值域二分——都变成”写出那个谓词”。这一篇七道主讲题全部用同一个函数。本篇要回答的核心问题是：为什么”第一个使谓词为真的位置”这一个模板能覆盖全部二分题？1 “答案二分”（吃香蕉、运输包裹、分割数组）怎样把最优化问题变成判定...

Posted by arganzheng | December 8, 2025

面试手撕代码（06）：图——BFS / DFS / 拓扑排序 / 并查集 / 最短路

Graphs: BFS, DFS, Topological Sort, Union-Find and Dijkstra

面试里的图题很少给你一张”图”——给的是网格、课程依赖、单词列表、账户邮箱，第一步是看出它是图：格子是节点、四邻是边；课程是节点、先修关系是有向边；单词是节点、改一个字母能到达是边。看出来之后，可用的算法只有五个：BFS（最短步数、按层扩散）、DFS（连通块、路径存在性）、拓扑排序（有向无环图的依赖顺序）、并查集（动态连通性）、Dijkstra（带权最短路）。这一篇六道主讲题每种一到两道，重点是建图和visited 放在哪——图题的 bug 多半出在这两处。本篇要回答的核心问题是： BFS 的 visited 标记应该在入队时打还是出队时打？1 拓扑排序怎样同时判断有没有环？2 并查集的路径压缩和按大小合并各起什么作用，写哪一个就够？3 一、识别信号...

Posted by arganzheng | December 7, 2025

Arganzheng's Blog