前几天有个读者私信我，说自己在准备2020年的校招，正好在牛客网上翻到“猿辅导2020校招笔试(算法岗二)”这套题，希望我抽时间写个复盘。说实话，猿辅导的算法笔试在行业内算是比较有代表性的，题量不大但覆盖面很扎实，既考基础算法功底，也考机器学习/深度学习的理论基础，还夹杂一些让你措手不及的细节题。今天我就把这套题拆开聊一聊，把每一步的思路、原理、踩坑点都理清楚，给正在准备算法岗笔试的同学一个可直接参考的复习地图。
先说结论：这套笔试不是那种“背背书就能过”的考试，它更看重你对算法本质的理解、对时间复杂度的敏感度，以及对经典算法在不同场景下的灵活变通。题目风格偏向“基础但不平庸”——不考偏怪题，但每道题都有“陷阱选项”或者“边界条件”等着你。适合正在冲刺互联网大厂算法岗的应届生，以及准备跳槽、需要系统复习算法的社招候选人参考。
我会从四个维度来复盘这套题：整体出题思路、高频考点逐个击破、编程题实战拆解、选择题知识点扫盲，最后再分享一些我踩过的坑和复盘心得。每个部分我都会结合题目背后的原理讲清楚“为什么”，而不是只给你答案。
1. 笔试题型分布与出题逻辑分析
1.1 整卷结构回顾
猿辅导算法岗二笔大概的题量是：20道左右的选择题 + 2道编程题，考试时间90分钟到120分钟不等（批次不同略有差异）。选择题覆盖两大类：一是计算机基础算法与数据结构（大概占50%），二是机器学习/深度学习的基础理论（占40%左右），还有少量概率统计和线性代数相关的数学题（占10%左右）。
这个结构其实很能说明问题：猿辅导作为在线教育公司，其业务核心涉及个性化推荐、自适应学习路径规划、课程内容审核与分发等场景，所以算法岗不仅需要扎实的工程算法能力，还需要理解机器学习的底层原理，尤其是特征处理、模型评估、经典模型细节等。可以说，这套笔试题就是在模拟“你入职后写推荐系统、做学习效果预测时，到底有没有扎实的基本功”。
1.2 考点频率统计与优先级排序
我把这套题和同期其他大厂算法笔试题横向对比了一下，发现猿辅导的考点有非常明显的“偏好”：
- 高频考点：字符串匹配（KMP相关）、排序算法时间复杂度对比、动态规划（经典背包/区间DP）、图的最短路径（Dijkstra及其变体）、贪心算法证明思路、LRU缓存设计。
- 中频考点：二叉树遍历、堆排序建堆复杂度、快速排序退化条件、并查集、拓扑排序。
- 机器学习考点：SVM的核函数、决策树的划分依据与剪枝、逻辑回归的损失函数与梯度推导、经典CNN的结构脉络、Batch Normalization的原理与作用、过拟合的解决手段。
- 数学基础：贝叶斯公式、期望与方差计算、特征值与特征向量的几何意义。
如果你只有72小时复习时间，请优先盯住上面“高频”里的内容，尤其是KMP的next数组计算和动态规划的“状态设计”部分，这两类几乎是每场笔试的必客。
1.3 这套题和别家大厂的区别在哪
和字节、腾讯的算法笔试相比，猿辅导的题更“学院派”一些。没有特别偏门的数据结构（比如平衡树、跳表的手写），也没有变态的压轴图论题。它更倾向于让你在经典算法上展示理解的深度，而不是广度。
举个例子：它不会直接问你“请实现红黑树的插入”，而是问“在KMP算法中，对于模式串p="abacaba"，其next数组（next[i]定义为...）是多少？”——这考的是你对next数组本质的理解，不是背模板。这种考法对基础扎实的人非常友好，但对“背题党”就是一记重锤。
2. 经典算法考点逐个击破
2.1 KMP算法：next数组到底怎么来的
KMP几乎是所有算法岗笔试的“钉子户”，猿辅导也不例外。最经典的一道题就是让你求模式串的next数组或nextval数组。
先说一个容易混淆的点：next数组的定义有几种版本。
- 版本一（考研/教材版）：
next[i]表示当模式串中第i个字符与主串不匹配时，下一次模式串跳到第几个位置进行比较。规定next[1] = 0（下标从1开始时）。 - 版本二（LeetCode/工程版）：
next[i]表示p[0...i]这个子串的最长相等前后缀长度（不包括整个子串本身）。
给你一个串p = "abacaba"，无论用哪个版本，核心都是找“最长相等前后缀”。以版本二为例，我们手推一下：
next[0]：子串"a"，没有前后缀，为0。next[1]：子串"ab"，前缀有"a"，后缀有"b"，不相等，为0。next[2]：子串"aba"，前缀"a"与后缀"a"相等，但前缀"ab"与后缀"ba"不等，所以最长相等前后缀长度为1。next[3]：子串"abac"，前缀"a"与后缀"c"不等，前缀"ab"与后缀"ac"不等，前缀"aba"与后缀"bac"不等，为0。next[4]：子串"abaca"，前缀"a"与后缀"a"相等，长度1；前缀"ab"与后缀"ca"不等，为1。next[5]：子串"abacab"，前缀"a"与后缀"b"不等；前缀"ab"与后缀"ab"相等，长度2；前缀"aba"与后缀"cab"不等，所以最长相等前后缀为2。next[6]：子串"abacaba"，前缀"a"与后缀"a"相等，长度1；前缀"ab"与后缀"ba"不等；前缀"aba"与后缀"aba"相等，长度3；前缀"abac"与后缀"caba"不等。所以最长相等前后缀为3。
所以版本二的next数组就是[0, 0, 1, 0, 1, 2, 3]。如果笔试中给出的是next[i]从1开始计数的版本，那就是[0, 0, 0, 1, 0, 1, 2]这种形式。
为什么KMP要搞这个数组？因为我们希望当匹配失败时，模式串不必从头开始重新匹配，而是跳到“已经匹配成功的最长后缀”对应的位置，从而把时间复杂度从O(m*n)降到O(m+n)。理解了这个动机，你就不需要死记代码了——你只需要记住：next[i]存的是“前i个字符组成的子串中，最长的、既是前缀又是后缀的那一段长度”。笔试时如果时间充裕，推荐用暴力方法手推一遍，比背模板更稳，因为在紧张状态下背错一位的可能性太高。
2.2 排序算法复杂度对比：选哪个、为什么
排序算法是选择题的常客，猿辅导爱考的形式有几种：给一个序列，问使用某种排序算法第一趟后的结果；问快速排序在什么情况下退化到O(n²)；问堆排序建堆的时间复杂度；问归并排序的额外空间复杂度。
这里我整理一张表，建议贴在电脑前反复看：
| 排序算法 | 平均时间复杂度 | 最坏时间复杂度 | 额外空间复杂度 | 稳定性 |
|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(n²) | O(1) | 稳定 |
| 快速排序 | O(n log n) | O(n²) | O(log n) | 不稳定 |
| 归并排序 | O(n log n) | O(n log n) | O(n) | 稳定 |
| 堆排序 | O(n log n) | O(n log n) | O(1) | 不稳定 |
| 插入排序 | O(n²) | O(n²) | O(1) | 稳定 |
| 希尔排序 | O(n^1.3) | O(n²) | O(1) | 不稳定 |
| 计数排序 | O(n+k) | O(n+k) | O(k) | 稳定 |
几个容易出坑的点：
- 快速排序最坏情况发生在“每次划分都极端不均”的时候，典型场景是序列已经有序（正序或逆序），且每次选择的基准都是第一个或最后一个元素。此时每次规模只减1，递归深度O(n)，总体O(n²)。
- 堆排序建堆有两种思路：自上而下逐个插入O(n log n)，自下而上siftDown建堆O(n)。严谨的建堆时间复杂度是O(n)，不是O(n log n)，选择题里常考这个。
- 归并排序的额外空间是O(n)，不是O(1)，原因是merge阶段需要一个与原数组等长的辅助数组。
- 计数排序适合数据范围较小的非负整数排序，它在某些场景下是O(n+k)的线性复杂度，但笔试选择题里经常用“时间复杂度和空间复杂度都很低”来迷惑你，要看清问的是哪个。
我的经验：排序题不要只背结论，一定要手动画一遍快排的分区过程。我之前在模拟面试中见过很多同学，能背出“快排平均O(n log n)”，但一让写partition的代码就出错，笔试题稍微换个问法就懵。核心其实是那个“挖坑填数法”或者“双指针交换法”，建议两种都练熟。
2.3 贪心算法：会算还不够，得会证明
猿辅导笔试里有一类题我很喜欢：它给你一个“显然可以用贪心”的题目，但选项里藏着“反例”。比如经典的“活动选择问题”或“钱币找零问题”。
Activity Selection的标准解法是“按结束时间最早排序”，这个大多数人都知道。但选择题会这样出：有若干活动和开始/结束时间，问按照“持续时间最短”来贪心是否可行？正确答案当然是不可行，还要你选出反例。这个考法其实就是在提醒你：贪心算法不是拍脑袋，必须要有“贪心选择性质”和“最优子结构性质”的证明。
我自己的判断技巧：当你在考场上想快速验证一个贪心策略是否成立，可以尝试构造一个极小反例。比如两个活动的区间是[1,5]和[2,3]和[4,6]，如果按“最早开始”贪心，会选择[1,5]，但最优解是[2,3]和[4,6]，这就是反例。一旦找到反例，基本可以断定该选项错误。
贪心本身不是难点，难的是“什么时候该用贪心”。在笔试读题时，如果题目限定“每个物品只能取一次”且要求“最大化价值”，那大概率是0-1背包（DP），而不是贪心。如果题目说“可以分割物品”，那么才考虑贪心（按单位重量价值排序）。
2.4 Dijkstra算法：堆优化的坑
图论在猿辅导笔试中占比不高，但Dijkstra出现的概率不低，尤其是与“有权图最短路径”相关。最常考的是复杂度对比：
- 朴素Dijkstra：O(V²)
- 优先队列（堆）优化后的Dijkstra：O((V+E) log V)
还有一个容易错的点：Dijkstra不能处理负权边。选择题经常给出一个带负权边的图，问“从源点到各点的最短路径，以下哪种算法不能使用”，答案就是Dijkstra。原因是Dijkstra的贪心策略基于“当前已经确定最短路的点不会被后续更新得更短”，但负权边会打破这个假设。此时要用Bellman-Ford或SPFA。
实操心得：复习Dijkstra时不要光看代码，要在草稿纸上跑一遍完整的松弛过程。我见过太多人写堆优化时忘了visited数组，结果同一个节点被多次推入堆，虽然最终结果仍然正确，但复杂度已经劣化，笔试如果要求分析“最多入堆几次”，就需要你真正理解堆优化的流程。节点最多入堆E次，因此在最坏情况下复杂度仍为O(E log V)。
2.5 动态规划：状态设计是灵魂
如果一套算法笔试题没有DP，那它是不完整的。猿辅导的DP题往往不会给“裸的背包问题”，而是穿上一层业务外衣，比如“课程学习路径规划”或者“积分类励最大化”。DP考的是状态定义、转移方程、初始条件和边界处理。
我举一个经典的简化版本：假设你在刷题，每个题目有一个难度d[i]和一个收益w[i]，要求选出的题目难度必须递增，求最大总收益。这个问题的状态定义是dp[i]表示以第i题结尾的最大收益，转移方程是dp[i] = max(dp[j] + w[i])，其中j < i且d[j] < d[i]，初始dp[i] = w[i]。这是一个典型的LIS（最长递增子序列）变体。
做题节奏建议：笔试题里DP如果第一眼没有思路，先跳到下一题，不要硬磕。因为DP的调试成本很高，尤其在线上笔试的编辑器里，你没有本地IDE的调试器。先把能拿的分数拿满，最后再回头啃DP。
3. 编程题实战拆解
3.1 编程题一：字符串相关，考察滑动窗口
我记得猿辅导这套笔试的编程题第一道，风格比较安全，是一道字符串类的题目，本质是“最长无重复字符子串”的变体。题目会给一个字符串，要求找出其中不含重复字符的最长子串长度。
这道题的标准解法是滑动窗口，时间复杂度O(n)，空间复杂度O(字符集大小)。核心思路：维护左右两个指针，右指针不断向右扩展，把字符加入窗口；如果遇到重复字符，左指针就移动到“上一次出现该字符的位置的下一个位置”，同时更新答案。
def length_of_longest_substring(s: str) -> int: last_pos = {} left = 0 ans = 0 for right, ch in enumerate(s): if ch in last_pos and last_pos[ch] >= left: left = last_pos[ch] + 1 last_pos[ch] = right ans = max(ans, right - left + 1) return ans这里的细节是：last_pos存的是每个字符最近一次出现的位置，当遇到重复且该位置在窗口内部时，左指针才移动。如果重复字符在窗口外部（即last_pos[ch] < left），说明这个“重复”已经在窗口之外了，不影响当前窗口的合法性。
为什么这道题适合作为算法岗笔试第一题？因为它考的是最基本的“双指针维护区间信息”思想，难度中等偏下，能快速区分“有没有写过代码”和“代码熟不熟”。我踩过的坑是忘记更新last_pos[ch] = right，导致后续字符全部错乱。笔试时一定要注意每个分支下都要更新字符的最新位置。
3.2 编程题二：图或DP的进阶题
第二道编程题通常会拉高难度。我印象里猿辅导有一套笔试的第二题和“课程依赖关系”有关——给定若干课程和它们的前置课程关系，问是否存在一种学习顺序能完成所有课程，如果有，输出一种合法顺序。这本质上就是拓扑排序，也可以用Kahn算法解。
Kahn算法思路：
- 统计每个节点的入度。
- 把所有入度为0的节点加入队列。
- 弹出队首节点，将其加入结果序列，并把它的所有邻接节点的入度减1。
- 如果某个邻接节点入度变为0，加入队列。
- 如果最终结果序列长度不等于节点总数，说明图中有环，无法完成所有课程。
from collections import deque def find_order(num_courses: int, prerequisites: list) -> list: adj = [[] for _ in range(num_courses)] indeg = [0] * num_courses for cur, pre in prerequisites: adj[pre].append(cur) indeg[cur] += 1 q = deque([i for i in range(num_courses) if indeg[i] == 0]) res = [] while q: node = q.popleft() res.append(node) for nxt in adj[node]: indeg[nxt] -= 1 if indeg[nxt] == 0: q.append(nxt) return res if len(res) == num_courses else []这个题的关键考点是“环检测”。很多人知道拓扑排序，但忘了判断结果长度是否等于总节点数，导致样例通过但提交全错。我在实际做这道题时，第一版代码就忘了加最后的长度判断，白白丢了一次提交机会。说实话，线上笔试的编译/运行次数有时是有限制的，这种低级错误非常致命。
进阶变体：如果题目改成“要求输出字典序最小的拓扑序列”，就不能用普通队列，而要用优先队列（小顶堆）。这种变体近几年越来越常见，因为它在原题基础上多考了一个“贪心+堆”的组合思路。
3.3 时间分配策略
如果90分钟做2道编程题+20道选择题，我的建议是：
- 前25分钟：快速过一遍选择题，遇到不会的先标记，不要恋战。
- 中间35分钟：主攻第一道相对简单的编程题。
- 之后25分钟：主攻第二道编程题，如果卡住5分钟没思路，先写暴力版拿部分分。
- 最后5分钟：回头检查之前标记的选择题，同时确保编程题无语法错误、无数组越界。
有很多人会把时间平均分配，这其实很危险。在线笔试的编程题，通常会按照“通过的测试用例占比”给分，暴力解通常能过一部分基础用例，所以“先保底、再优化”是性价比最高的策略。
4. 选择题隐藏知识点扫盲
4.1 机器学习基础：不只是背概念
猿辅导作为在线教育公司，对机器学习理论的要求不是“了解”，而是“理解”级。我记得有几道选择题特别能说明问题：
- 关于逻辑回归，问“为什么逻辑回归的损失函数是交叉熵而不是均方误差？”看了热搜词里也有“kl elbo算法原理详解”这种题目，说明猿辅导的ML题偏爱“原理推导”。交叉熵和MSE的对比在于：交叉熵配合sigmoid是凸函数，梯度更新稳定；MSE配合sigmoid会导致梯度消失，收敛极慢。
- 关于SVM，问“为什么引入核函数？”这考察的是对“低维线性不可分时映射到高维空间”这个过程的认知。核函数的作用就是在不显式计算高维特征的情况下，直接计算高维空间的内积，从而避免了维数灾难。
这里我强烈建议，准备笔试时不要只背“逻辑回归是分类模型”这种常识，要能自己推导一遍梯度下降更新公式。虽然笔试答题不要求默写推导，但在两个选项之间犹豫时，懂原理的人会瞬间排除错误项。
4.2 优化算法：从SGD到Adam
机器学习题里常出现“以下哪种优化算法引入了动量（momentum）的概念”“Adam结合了哪两种方法的优点”这类题。答案是：
- Momentum：在SGD的基础上引入历史梯度的指数加权平均，加速收敛并减少震荡。
- RMSProp：对梯度平方做指数加权平均，自适应调整学习率。
- Adam：同时使用一阶动量和二阶动量，相当于Momentum + RMSProp。
这是高频考点，但很多同学会混淆RMSProp和AdaGrad的区别。AdaGrad是累积全部历史梯度的平方，会导致学习率单调递减到0；RMSProp只累积最近一段时间窗口的梯度平方，缓解了这个问题。选择题问你“Adam等同于哪两个算法的结合”，你要先想到Momentum和RMSProp，而不是AdaGrad。
4.3 数据结构细节：二叉树和堆
有一类选择题非常“阴险”：给一个数组，问它是否满足“大顶堆”或“小顶堆”的性质。判断方法很简单——对于下标i（从0开始），其左孩子下标为2*i+1，右孩子下标为2*i+2，需要每个父节点都大于等于（或小于等于）两个子节点。
还有一类题是关于“堆排序建堆复杂度”的。很多人直接背“建堆O(n log n)”，但正确答案是O(n)。原因在于build_heap采用从最后一个非叶子节点开始向上调整（siftDown）的方式，大部分节点所在的子树高度很小，总调整次数是O(n)。如果你要严谨地推到O(n)这个结论，可以用“各层节点数 × 该层节点的调整次数”累加，得到的是一个收敛于线性阶的级数。
4.4 概率统计与贝叶斯
贝叶斯公式是必考的，通常以这样的形式出现：已知某疾病的患病率、检测的敏感度和特异度，问“检测结果为阳性时，真正患病的概率是多少”。
我做题的经验是：不要套公式硬算，要“建一个10000人的虚拟人群”来推导。假设10000人中有1%患病，则100人患病、9900人健康；假设敏感度99%（患病者中99%检测阳性），特异度99%（健康者中1%检测阳性），那么检测阳性的人数 = 100×0.99 + 9900×0.01 = 99 + 99 = 198人，而其中真正患病的只有99人，所以阳性者真正患病的概率是99/198 = 0.5。这类题一旦用“虚拟人群”法，几乎不可能算错，比直接套贝叶斯公式直观得多。
4.5 场景化算法应用：LRU、并查集、位运算
猿辅导的选择题也偏爱“场景化”考察。比如“在设计一个课程推荐缓存系统时，希望最近访问的内容保留在缓存中、超出容量后淘汰最久未使用的条目，应该采用哪种数据结构？”答案是LRU Cache，实现方式是哈希表 + 双向链表。哈希表保证O(1)查找，双向链表保证O(1)移动和删除。
这种题考的不是数据结构本身，而是“在具体业务场景中选择合适数据结构”的能力。我建议复习时多做一个动作：把每个数据结构的“擅长场景”列出来。比如：
- 哈希表：O(1)查找，适合“键值对快速访问”。
- 双向链表：O(1)插入删除，适合“频繁在头部/尾部操作”。
- 优先队列（堆）：O(log n)插入和取最值，适合“动态取最大/最小值”。
- 单调栈：适合“找下一个更大/更小元素”。
- Trie：适合“前缀匹配、词频统计”。
5. 避坑指南与备考心态
5.1 线上笔试的几个隐形坑
我参加过的线上笔试不少，猿辅导这套使用的是国内常见的在线笔试平台。有几个隐形坑想特别提醒一下：
输入输出的坑：在线笔试平台对输入格式要求很严格。比如一次给多个测试用例、每行数据格式不同等，读错一个字符就是0分。建议提前熟悉
sys.stdin.read()和sys.stdin.readline()的区别，以及strip()和split()的配合使用。数组越界与边界值：DP题特别容易在
dp[0]或dp[n-1]上出问题。如果样例通过但提交只有部分通过，先用几个小范围极端值自测（如空数组、只有一个元素、全是相同字符等）。“我印象最深的一次，是写滑动窗口时没有考虑空字符串，直接报IndexError，白白浪费了5分钟。”不要贪心先做难题：有些人一看第二道编程题就兴奋，非要先啃硬骨头，结果做了40分钟没AC，回头发现第一道简单题都没时间写。先易后难是最稳的策略，笔试分数是按用例比例算的，暴力解拿到的部分分也是分。
5.2 我的复盘心得与后续建议
我帮读者复盘这套题时，最大的感受是：猿辅导的算法笔试不考“偏题”，但每一道题都值得你深挖一步。比如KMP的next数组，如果你只是背模板，确实能算出答案，但遇到nextval变体时就会崩溃。如果你理解了“最长相等前后缀”的含义，不管它怎么变你都能应对。
刷题建议上，我不推荐每天无脑刷5道新题，而是推荐“刷1道题 + 写一版题解 + 分析时间空间复杂度 + 思考最少3种变体”的模式。这个模式能让你在有限时间内覆盖最多的考点。
另外，有一点想特别强调：笔试结束后一定要复盘。哪怕你全AC了，也要去搜一下别人对这题的更优解法。很多题你用了O(n²)的DP，但标准解可能是O(n log n)的贪心+二分。校招的面试官是会看你的笔试记录的，如果你当场提交的解法不够高效，即使AC了也可能在面试中被追问优化方案。
如果你正在准备算法岗校招，我给最后几条粗糙但实用的建议：
- 把KMP、Dijkstra、拓扑排序、滑动窗口、背包类DP这五类问题练到“不假思索”的程度，它们是每次笔试的保底分。
- 机器学习的复习不要只停留于概念，至少能手推一遍逻辑回归的梯度、理解Batch Normalization为什么能加速收敛。
- 做题时养成“先想清楚边界条件再写代码”的习惯。边界条件是编译通过但提交失分的第一大原因。
- 多参加模拟笔试，适应倒计时和无法Debug的环境。
这套题本身不难，难的是你在紧张状态下能不能保持冷静，把平时练的东西稳定输出。希望这篇复盘能帮你少走一些弯路，祝笔试顺利。
