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 题目原貌模式串 pabacaba 的 next 数组这道题的原题大概是这样的“在KMP算法中对于模式串 pabacaba其 next 数组next[i] 定义为模式串前 i 个字符组成子串的最长相等前后缀长度是多少请写出求解过程。”这题看似简单但有一个大坑next数组的定义在不同教材里并不完全一样。有的定义是“最长相等前后缀长度”有的定义是“失配时模式串指针跳转的位置”。如果不看题目给出的定义直接按记忆写很可能整道题全错。我当时就停顿了一下确认题目使用的是“前i个字符的最长相等前后缀长度”这个口径才开始往下算。这里顺便解释一下什么叫“最长相等前后缀”。对于字符串ababa它的前缀有a、ab、aba、abab后缀有baba、aba、ba、a其中相等且长度最长的是aba长度3。注意前后缀都不能取整个字符串本身这是KMP的next数组里最容易搞错的地方。2.2 前缀函数口径下的手算过程我按题目给的定义把模式串 pabacaba 的每一位都拆开计算了一遍。为了清楚我把过程整理成了表格i当前子串前i个字符最长相等前后缀长度简要说明00初始位置通常定01a0只有一个字符前后缀为空2ab0前缀a后缀b不匹配3aba1前缀a后缀a4abac0前缀a后缀c不等其他更不可能5abaca1前缀a后缀a6abacab2前缀ab后缀ab7abacaba3前缀aba后缀aba所以按“前缀函数”口径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[i]前i个字符最长相等前后缀长度[0, 0, 0, 1, 0, 1, 2, 3]失配跳转next[i]失配时跳转位置[-1, 0, 0, 0, 1, 0, 1, 2]笔试时如果题目没有明确定义最好在答题区域写一句“这里采用××定义”这样即使和官方答案的表示形式不同改卷老师也明白你的思路是对的。这个题最大的易错点有两个一是没有把子串本身排除在前后缀之外导致 next[7] 误算成7二是对“相等”的判断不够仔细比如abacab里最长相等前后缀是ab不是a如果只看到前后都是a就写1那就掉进陷阱了。2.4 代码实现细节手算next数组只是第一步编程题通常还要求写出完整的KMP匹配代码。我现场写的版本是这样Cvectorint buildNext(const string p) { int m p.size(); vectorint 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; vectorint 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数组时外层循环从 i1 开始因为 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(vectorint 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(vectorint 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 一维滚动数组与完全背包空间优化后的代码是vectorint 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等号当且仅当PQ二是不对称KL(P||Q) ! KL(Q||P)所以它不满足距离的定义。纸上谈兵不容易理解我现场给自己举了个小例子。假设有两个伯努利分布P(0)0.8、P(1)0.2Q(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(t1) w * v_i(t) c1 * r1 * (pbest_i - x_i(t)) c2 * r2 * (gbest - x_i(t))x_i(t1) x_i(t) v_i(t1)这里 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 推导写一遍比看十遍都管用。