猿辅导算法岗笔试复盘：KMP、背包与ELBO推导全解析

2020年秋招投猿辅导算法岗的时候，我把这场笔试当成一次重要的“摸底考试”。猿辅导这套笔试卷子出得不算偏，但特别能筛人，因为它考的几乎都是算法岗必须吃透的基础内容：字符串匹配、排序、动态规划、机器学习推导，甚至还有粒子群这类优化算法的原理题。考完出来很多人吐槽“题目看着都会，写起来全是坑”，我自己也踩了几个。这篇复盘我尽量把当时卷子里出现的核心考点、我给出的解题思路、考场上的易错点都还原出来，给准备校招算法岗的同学做个参考。

1. 笔试复盘：猿辅导算法岗一到底在考什么

1.1 试卷结构与核心考察点

猿辅导2020校招算法岗一这套笔试试卷，整体结构比较典型：4道编程题加1道简答题，时长大概90分钟。编程题覆盖了字符串、排序、动态规划这几个高频板块，简答题则侧重机器学习基础，尤其喜欢考概率和贝叶斯相关的内容。

这里要特别说一句：校招笔试里的“算法岗”和“研发岗”考察侧重点不太一样。研发岗更看重代码能不能AC，而算法岗除了代码正确性，还会关注你对数据结构背后的复杂度、算法适用场景、模型原理的把握。猿辅导这套卷子就很明显，代码题里会夹杂“请说明时间复杂度”“为什么这样优化”这类问题，简答题更是直接上KL散度和ELBO的推导。如果只是埋头刷LeetCode，没有系统梳理过机器学习基础，很容易在这块卡住。

所以准备这套笔试的时候，不能只刷题，还得把《统计学习方法》里那几章经典内容过一遍，尤其是KMP、快排、背包这几个老邻居，再加上变分推断的基本推导，基本就能覆盖大部分考点。

1.2 难度曲线与得分策略

整体的难度曲线不是从易到难直线上升的，而是“起伏式”的。第一道题是KMP的next数组，属于送分题，但很多人对next的定义记忆模糊，容易在边界条件上翻车。第二道排序题难度中等，考堆排手写。第三道动态规划开始上强度，0-1背包问你空间优化。第四道代码题和第五道简答题考查机器学习推导，时间紧张的情况下很容易写不完。

我在考场上的策略是：发卷后先花2分钟通读所有题目，心里给每道题标一个“估计耗时”。先做最稳的KMP next数组，接着写堆排序，再写0-1背包，最后才碰KL散度和ELBO推导。简答题不要跳过，哪怕只能写出前半段推导，也能拿到部分分数。如果你碰到一道题卡了超过15分钟，先跳过做后面的，别跟一道题死磕，这是校招笔试最重要的一条时间守则。

2. 字符串算法：KMP next 数组手算与代码细节

2.1 题目原貌：模式串 p="abacaba" 的 next 数组

这道题的原题大概是这样的：“在KMP算法中，对于模式串 p="abacaba"，其 next 数组（next[i] 定义为模式串前 i 个字符组成子串的最长相等前后缀长度）是多少？请写出求解过程。”

这题看似简单，但有一个大坑：next数组的定义在不同教材里并不完全一样。有的定义是“最长相等前后缀长度”，有的定义是“失配时模式串指针跳转的位置”。如果不看题目给出的定义直接按记忆写，很可能整道题全错。我当时就停顿了一下，确认题目使用的是“前i个字符的最长相等前后缀长度”这个口径，才开始往下算。

这里顺便解释一下什么叫“最长相等前后缀”。对于字符串"ababa"，它的前缀有"a"、"ab"、"aba"、"abab"，后缀有"baba"、"aba"、"ba"、"a"，其中相等且长度最长的是"aba"，长度3。注意，前后缀都不能取整个字符串本身，这是KMP的next数组里最容易搞错的地方。

2.2 前缀函数口径下的手算过程

我按题目给的定义，把模式串 p="abacaba" 的每一位都拆开计算了一遍。为了清楚，我把过程整理成了表格：

所以按“前缀函数”口径，next数组为 [0, 0, 0, 1, 0, 1, 2, 3]。

这里我特别想强调一下 next[6]=2 这个位置。前6个字符是"abacab"，最长相等前后缀是"ab"，长度2，不是1。很多人惯性思维看到后缀是"ab"就写2，但如果没认真比对"abac"和"acab"，很容易漏算。手算的时候不要跳步，一位一位抠。

2.3 失配跳转口径与易错点

如果你用的教材里next[i]表示“模式串第i位失配时，模式串指针应该跳转到的位置”，那答案又不一样了。这种口径通常是把前缀函数整体右移一位，然后在最前面补一个-1。我把两种口径的差异也列一下，方便大家对照：

笔试时如果题目没有明确定义，最好在答题区域写一句“这里采用××定义”，这样即使和官方答案的表示形式不同，改卷老师也明白你的思路是对的。

这个题最大的易错点有两个：一是没有把子串本身排除在前后缀之外，导致 next[7] 误算成7；二是对“相等”的判断不够仔细，比如"abacab"里最长相等前后缀是"ab"不是"a"，如果只看到前后都是"a"就写1，那就掉进陷阱了。

2.4 代码实现细节

手算next数组只是第一步，编程题通常还要求写出完整的KMP匹配代码。我现场写的版本是这样（C++）：

vector<int> buildNext(const string& p) { int m = p.size(); vector<int> next(m, 0); int j = 0; for (int i = 1; i < m; i++) { while (j > 0 && p[i] != p[j]) { j = next[j - 1]; } if (p[i] == p[j]) { j++; } next[i] = j; } return next; } int kmpMatch(const string& s, const string& p) { int n = s.size(), m = p.size(); if (m == 0) return 0; vector<int> next = buildNext(p); int j = 0; for (int i = 0; i < n; i++) { while (j > 0 && s[i] != p[j]) { j = next[j - 1]; } if (s[i] == p[j]) { j++; } if (j == m) { return i - m + 1; } } return -1; }

这里有个细节值得注意：构建next数组时，外层循环从 i=1 开始，因为 next[0] 固定为0。内层while循环用 next[j-1] 来回退，而不是 j--，这是KMP高效的关键。很多人在写的时候容易把p[i]和p[j]的索引搞混，导致数组越界或者死循环。笔试时间紧，这类代码最好在草稿纸上先画一遍流程，确认边界没问题再提交。

3. 排序与Top K：高频手写题怎么做

3.1 从“快排最坏情况”看排序选型

第二道题我记得和排序有关，考的是“快速排序的最坏情况是什么？请实现堆排序，并说明两者的时间复杂度与稳定性”。

这类题在算法岗笔试里出现频率极高，因为它能一次性考查好几个维度：会不会写经典排序、知不知道退化场景、能不能根据场景选算法。快速排序最坏情况是O(n^2)，典型场景是输入已经有序或逆序，而每次选取的基准都是当前区间的最大或最小元素，导致分区极度不平衡。解法也很经典：随机选择基准，或者三数取中法，能把最坏情况的概率降得非常低。

堆排序则没有快排这种退化问题，最坏、平均、最好都是O(n log n)。但要注意，堆排序是不稳定的排序，这跟归并排序的“稳定”形成对比。笔试题里经常问“要稳定排序选什么”，标准答案是归并排序，但如果要求原地排序，那就要在时间、空间、稳定性之间做取舍。没有一种排序在所有维度上都占优，这就是排序选型题的价值所在。

3.2 堆排序手写与堆化细节

我现场写了堆排序，核心是建堆和堆化两个过程。升序排序用最大堆，每次把堆顶元素换到数组末尾，缩小堆的范围再重复堆化。代码大致如下：

void heapify(vector<int>& a, int n, int i) { int largest = i; int l = 2 * i + 1; int r = 2 * i + 2; if (l < n && a[l] > a[largest]) largest = l; if (r < n && a[r] > a[largest]) largest = r; if (largest != i) { swap(a[i], a[largest]); heapify(a, n, largest); } } void heapSort(vector<int>& a) { int n = a.size(); for (int i = n / 2 - 1; i >= 0; i--) { heapify(a, n, i); } for (int i = n - 1; i > 0; i--) { swap(a[0], a[i]); heapify(a, i, 0); } }

有几个容易写错的地方。第一个是建堆起点，必须从 n/2-1 开始，因为最后一个非叶子节点的下标就是 n/2-1，从它往前逐个堆化，才能保证整个数组满足堆性质。第二个是第二次循环里，每次堆化传入的数组长度是 i 而不是 n，因为 i 之后的元素已经排好序，不能再动。第三个是递归堆化的参数 largest，交换之后，largest 位置可能被破坏，需要继续往下调整。这几个细节在笔试手写代码时非常容易漏，建议平时多默写几遍。

3.3 Top K 问题的两种最优解

考排序肯定会连带问Top K，猿辅导这套题里有一问就类似这样：“一个非常大的数组，取前K个最大的元素，你会怎么做？”

两个主流方案，现场我都写了：

方案一：全局排序，直接排完取前K个，时间复杂度 O(n log n)，适合 n 不太大的情况。方案二：维护一个大小为 K 的小顶堆，遍历数组，只要当前元素比堆顶大，就弹出堆顶再加入当前元素。遍历结束后堆里的 K 个元素就是前K大的。时间复杂度 O(n log K)，内存占用 O(K)，适合海量数据。

如果把内存限制也放宽、允许修改原数组，用快速排序的 partition 思路去做，平均时间复杂度能降到 O(n)，这就是“基于快排的快速选择”。不过这属于附加的高阶解法，笔试时优先把堆方案写出来，再提快速选择作为优化，会显得思路非常完整。我当时是三个方案都提了一下，并且用表格对比了复杂度和适用场景，这种回答方式在笔试简答部分特别加分。

4. 动态规划：背包问题的变体

4.1 0-1背包题目建模

第三道编程题是0-1背包，题干大意是：有 n 件物品，第 i 件物品重量 w[i]，价值 v[i]，背包容量 W，每件物品只能选一次，求能装下的最大总价值。

这题在算法岗笔试里属于“必背题”，但越是这样，越容易被出题人挖细节。我印象很深的是，题目在最后加了两个小问：一是要求用一维数组优化空间，二是说明为什么容量遍历要倒序。这两个小问恰恰是区分“背过模板”和“真的理解”的关键。

4.2 状态定义、转移方程与边界

先写最朴素的定义：dp[i][j] 表示前 i 件物品中选取若干件，放入容量为 j 的背包时能获得的最大价值。转移方程是：

dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])，其中 j >= w[i]。

这个方程的含义很直白：对第 i 件物品，要么不选，继承前 i-1 件在容量 j 下的最优值；要么选，那就要腾出 w[i] 的空间，然后在容量 j-w[i] 的情况下加上第 i 件物品的价值。初始状态 dp[0][j] = 0，表示没有物品可选时价值恒为0。

复杂度为 O(nW)，其中 W 是背包容量。这里要注意，如果题目里 W 的数据范围很大（比如 10^9），二维数组根本开不下，那就得换个思路，比如按价值做 DP 或者使用搜索剪枝。笔试时先算一下空间复杂度，再决定要不要开二维数组，是非常好的习惯。

4.3 一维滚动数组与完全背包

空间优化后的代码是：

vector<int> dp(W + 1, 0); for (int i = 0; i < n; i++) { for (int j = W; j >= w[i]; j--) { dp[j] = max(dp[j], dp[j - w[i]] + v[i]); } }

关键就是内层循环要从 W 往小遍历。为什么？因为 dp[j - w[i]] 在计算 dp[j] 之前如果已经被本轮更新过，那就等于第 i 件物品被选了多次，这正好是“完全背包”里的语义。0-1背包要求每件物品最多选一次，所以必须保证在更新 dp[j] 时，dp[j - w[i]] 还停留在上一轮的状态，也就是还没被当前物品污染。

很多同学会问，那完全背包怎么办？很简单，把内层循环改成从 w[i] 到 W 正序遍历即可。这个“一逆一正”的区别，就是0-1背包和完全背包最核心的差异，笔试简答如果考到，一定要把这个逻辑讲清楚。我还在代码下面补充了一句边界说明：如果题目要求“恰好装满背包”，初始化时 dp[0]=0、dp[j]=-INF，这样只有能恰好凑出的容量才会被更新，否则最终结果是负无穷。这种细节写上去，哪怕是笔试卷，也会让面试官觉得你基础非常扎实。

5. 机器学习基础：KL散度与ELBO推导

5.1 算法岗笔试为什么考这些

第五道简答题直接给了一个概率推导题：写出 KL 散度的定义，然后推导变分推断中的 ELBO 表达式。乍一看有点突兀，一个面向校招的笔试怎么会考贝叶斯推断？但仔细想想，教育公司算法团队日常做模型评估、用户建模，经常要跟生成模型和贝叶斯方法打交道。KL散度和ELBO是变分自编码器（VAE）、变分推断等一系列模型的理论地基，考这个非常合理。

这类题目对“刷题型选手”很不友好，因为它不靠背模板，而是考察你对概率公式的变形能力和数学直觉。我当时在最后几分钟把它写了出来，但推导过程比较乱。现在复盘，我觉得有两条主线可以讲清楚。

5.2 KL散度定义与计算实例

KL散度用来衡量两个概率分布P和Q之间的差异，离散形式为：

KL(P || Q) = Σ P(x) log(P(x)/Q(x))

它的两个性质很重要：一是非负，KL(P||Q) >= 0，等号当且仅当P=Q；二是不对称，KL(P||Q) != KL(Q||P)，所以它不满足距离的定义。

纸上谈兵不容易理解，我现场给自己举了个小例子。假设有两个伯努利分布，P(0)=0.8、P(1)=0.2，Q(0)=0.6、Q(1)=0.4。那么：

KL(P||Q) = 0.8 * ln(0.8/0.6) + 0.2 * ln(0.2/0.4) ≈ 0.092

而反过来：

KL(Q||P) = 0.6 * ln(0.6/0.8) + 0.4 * ln(0.4/0.2) ≈ 0.105

两个值不一样，这就直观说明了KL散度不是对称的。笔试时如果能举一个这样的数字例子，会增加不少印象分，因为推导题最忌讳干巴巴写公式，阅卷人希望看到你真的理解了。

5.3 ELBO推导：一行一行写出来

ELBO全称是Evidence Lower Bound，证据下界。推导的核心场景是：我们要计算后验分布 p(z|x)，但通常无法直接求解，于是用一个近似分布 q(z|x) 来逼近。这时，对数边际似然可以写成：

log p(x) = log ∫ p(x, z) dz

引入 q(z|x) 后，可以变形为：

log p(x) = E_{q(z|x)}[log p(x, z)] - E_{q(z|x)}[log q(z|x)] + KL(q(z|x) || p(z|x))

其中前两项合起来就是 ELBO，即：

ELBO = E_{q(z|x)}[log p(x, z)] - E_{q(z|x)}[log q(z|x)]

最后一项是 KL(q(z|x) || p(z|x))。因为KL非负，所以：

log p(x) >= ELBO

也就是说，ELBO是对数边际似然的下界。我们无法直接最大化 log p(x)，就转而最大化 ELBO，这同时会压缩近似后验和真实后验之间的 KL 散度，让 q(z|x) 越来越接近 p(z|x)。

这套推导在VAE里被反复使用。如果你只背结论“ELBO = E_q[log p(x,z)] - E_q[log q(z|x)]”，不掌握一步步变形的逻辑，遇到“请说明为什么优化ELBO等价于最小化KL”这种追问就很容易答不上来。所以我建议准备这套笔试时，把这套推导在白纸上自己推两遍，推顺了之后遇到类似简答题都会很轻松。

6. 附加题考点：粒子群算法与模拟退火速览

6.1 粒子群算法的核心原理

我印象里猿辅导这次笔试还有一个附加题板块，或者说是面试追问时可能出现的扩展考点，其中提到了粒子群算法。这个算法属于群体智能优化算法，灵感来自鸟群觅食行为，核心思想是让每个“粒子”在解空间里飞行，通过个体历史最优和群体历史最优来更新自己的速度和位置。

速度更新公式是粒子群算法的灵魂，必须能默写：

v_i(t+1) = w * v_i(t) + c1 * r1 * (pbest_i - x_i(t)) + c2 * r2 * (gbest - x_i(t))

x_i(t+1) = x_i(t) + v_i(t+1)

这里 w 是惯性权重，控制粒子继续沿原方向飞行的趋势；c1 和 c2 是学习因子，分别控制向个体最优和群体最优学习的强度；r1、r2 是 [0,1] 之间的随机数。记忆技巧很简单：速度更新 = 上一步速度 + 个体认知项 + 社会认知项。如果题目问“粒子群算法和遗传算法区别”，核心答法是：粒子群每个粒子都保留自己的解和搜索方向，遗传算法则通过交叉变异产生新解，两者机制完全不同。

6.2 模拟退火速记

模拟退火也是这类扩展题里的常客。核心思想来自金属退火：温度高时分子运动剧烈，温度慢慢降低后趋于稳定。算法用一个温度 T 来控制接受更差解的概率，接受概率为：

P = exp(-ΔE / T)

其中 ΔE 是新解和目标值的差。如果 ΔE < 0，说明新解更好，肯定接受；如果 ΔE > 0，则以 P 的概率接受差解，这样能跳出局部最优。随着温度 T 下降，接受差解的概率越来越小，最终收敛。

笔试遇到这种简答题，直接把流程分四步写清即可：初始化解和温度，产生邻域新解，按概率选择是否接受，降温迭代。这个考点的价值不在代码，而在你是否理解“随机跳出局部最优”的通用思想，它和经典贪心算法的思路完全不同。

7. 现场踩坑与补救：复盘中的关键教训

7.1 定义不明确一定要先写假设

KMP那道题，我做完回想起来最危险的一点就是 next 数组的定义。如果题目没给准确定义，你不能默认自己背过的那种口径，最好的做法是在答卷开头写一句“这里我采用的定义是……”。这样就算和题目预期不一致，也能让阅卷人知道你是理解题意的，只是口径不同，不会直接给零分。我后来参加其他公司笔试也沿用了这个习惯，非常管用。

7.2 手写代码宁可慢也别漏边界

堆排序的代码我在考场上写快了，差点漏掉第二次循环里堆化长度从 i 开始这个细节。手写代码和IDE里写代码不一样，没有编译器帮你检查数组越界，你要自己心里“模拟运行”一遍。特别是这种递归函数，我会在草稿纸上画一个简单的堆，比如[4,10,3,5,1]，手动推一遍 heapify 的过程。看似浪费几分钟，但能避免交上去之后因为边界问题直接0分。

7.3 时间分配参考：前60分钟做代码，后25分钟写推导，留5分钟检查

这是我多次笔试下来觉得最稳妥的节奏。代码题需要头脑清醒，适合在刚开始体力最足的时候做；简答题只要时间够就能写，放后面不慌。前60分钟如果卡题，超过15分钟先跳过；后25分钟把所有能写的推导、思路、复杂度分析都补上；最后5分钟检查有没有漏题和明显笔误。用这个节奏，我在那场笔试里基本把所有题目都写到了“有思路+部分实现”的程度，没有出现交卷前才发现漏做的情况。

如果让我说这场笔试最大的收获，我觉得不是多会了几道算法题，而是终于明白算法岗笔试考的不只是“会不会写代码”，更是“能不能解释清楚每一步为什么”。KMP回退为什么用 next[j-1]，背包容量为什么要倒序遍历，ELBO为什么能作为优化目标，这些“为什么”反复出现在猿辅导的笔试题里。平时刷题多问自己几个“为什么”，考试时就能少踩几个坑。准备校招的同学，建议把这篇里提到的每道题都亲手写一遍，尤其是手算 next 数组和 ELBO 推导，写一遍比看十遍都管用。