2020校招算法岗笔试复盘：KMP、贪心与动态规划考点全解析

2019年秋天我投了猿辅导的算法岗参加的是2020届校招笔试的第三套卷子也就是很多人说的“算法岗三”。这套题给我的整体感受是不偏不怪但很考验基础功底的扎实程度。选择题里数据结构和机器学习概念都有涉及编程题则集中在经典算法模型的变体上比如字符串匹配、区间贪心、动态规划。今天把这场笔试完整复盘一遍包括题型设置、解题思路、常见陷阱和备考建议相信对准备校招算法岗的同学会有参考价值。我尽量还原当时的题目场景不保证每个字都和原卷一致但核心考法和需要具备的能力是一样的。你可以把这篇内容当成一套“带解析的模拟卷”来刷重点不是背答案而是理解每道题背后的出题逻辑和做题节奏。1. 2020校招算法岗笔试题型复盘与备考思路1.1 笔试整体结构与体验猿辅导2020届校招笔试用的是在线笔试系统算法岗三这套卷子整体时长我记得是90分钟题量不算轻松。题型分两个部分前面是选择题后面是编程题。选择题大概有十几道覆盖的面比较杂包括数据结构、算法设计策略、机器学习基础、深度学习基础甚至还有一两道类似“粒子群算法原理”“PID控制中的参数作用”这种听起来偏工程实际的题目。这部分其实很容易拉开分差因为很多人只刷剑指Offer和LeetCode对机器学习概念题准备不足。编程题一共三道难度梯度比较明显第一道偏基础第二道中等第三道需要一定的动态规划思维。在线编辑器的自动补全功能很弱也没有本地IDE顺手所以平时如果习惯在IDE里刷题到了笔试环境会有一段时间不适应。这里先提醒一句最好提前在牛客网、力扣的在线编辑器上练手感尤其是代码补全和调试方式。1.2 算法岗笔试到底在考什么从企业角度拆解猿辅导是教育科技公司主要业务涉及在线直播课、辅导产品、智能练习系统算法团队日常会接触搜索、推荐、用户行为分析、课程内容生成、自适应学习路径规划等场景。但笔试不会直接考业务而是把这些业务背后的通用能力抽象成算法题。所以说算法岗笔试本质考的是三件事第一能否用代码准确实现经典算法第二能否分析时间复杂度和空间复杂度第三能否在有限时间内识别题目的算法模型并处理边界条件。第三件事最高频的拦路虎就是KMP、贪心、动态规划这类有固定套路但又容易写错的题。我见过很多同学抱怨“题目刷了两百道还是过不了笔试”原因多半是只刷数量不总结模型。比如看到“求最大”“求最少”“求方案数”首先应该想的是贪心还是动态规划而不是直接上来暴力循环。校招笔试的判题系统只给少量示例不会提示你超时也不会告诉你错在哪个用例所以要想通过必须在写代码前把算法模型想清楚。2. KMP算法高频必考点与next数组破题2.1 KMP为什么反复出现在校招笔试里在整理热搜词时我看到有一条是“在 kmp 算法中对于模式串 pabacaba其 next 数组(next[i] 定义为...”这几乎就是把当年“算法岗三”的一道选择题原封不动搬出来了。可见这套题对KMP的考察非常直接。KMP是字符串匹配的经典算法网上资料很多但不少人只是背模板没有真正理解next数组的含义所以一旦题目换一种定义方式就容易算错。KMP能高频出现在笔试里是因为它同时考察了“对暴力匹配缺陷的理解”和“用已经匹配的信息避免重复比较”的优化思想这在校招面试官眼里是一项很基本的算法素养。2.2 题目原样与next数组的两种定义题目一般会给出一个模式串比如p abacaba然后让求next数组。但这里最大的坑在于不同的教材、不同题库对next数组的定义不一样。常见有两种定义一next[i] 表示p[0..i]这个子串中最长相等真前后缀的长度。这个其实就是字符串算法里常说的前缀函数prefix function。定义二next[i] 表示当p[i]失配时模式串应该跳回到哪个位置继续匹配。这种写法通常把 next[0] 设为 -1然后往前错一位。先说定义一也就是计算每个前缀子串的最长相等真前后缀长度。对p abacaba可以手算i0子串a真前后缀为空所以 next[0] 0。i1子串ab前缀a后缀b不相等next[1] 0。i2子串aba前缀a后缀a相等且长度为1长度2时前缀ab后缀ba不相等所以 next[2] 1。i3子串abac前缀、后缀逐个看长度为1时a和c不等更长的也不用看next[3] 0。i4子串abaca长度为1时a和a相等长度为2时ab和ca不等所以 next[4] 1。i5子串abacab长度为2时前缀ab后缀ab相等长度为3时前缀aba后缀cab不等所以 next[5] 2。i6子串abacaba长度3时前缀aba后缀aba相等长度4时前缀abac后缀caba不等所以 next[6] 3。所以定义一下最终结果是[0, 0, 1, 0, 1, 2, 3]。但如果你用的是考试系统里的模板看到next数组写法是[-1, 0, 0, 1, 0, 1, 2]也别慌这是定义二的写法它本质上是把前缀函数整体向右移动了一位并在开头补了-1。假如题目明确说“next[i]为失配时跳转的位置”你要会换算出这个结果。2.3 手算next数组的快速技巧很多同学觉得KMP难是因为每道题都从推导式开始算太慢。实际手算时可以用一个更直观的办法直接看对称性从长到短找最长相等前后缀。比如计算到abacaba时先看整个串有没有最长相等前后缀。明显首尾都是aba中间也刚好是同一个串的一部分所以最长就是3。如果首尾相等再往内看一级是否相等多试两次就能确定。注意“真前后缀”不能等于整个子串本身比如单字符子串最长相等前后缀一定是0。一个小建议考试时不要试图现场推KMP的完整代码先把next数组的值速算出来选择题就能拿分如果编程题真遇到KMP再套你背熟的模板。KMP的模板建议用C或Python各写一遍笔试时能更快适应环境。vectorint getNext(string p) { int m p.size(); vectorint pi(m, 0); for (int i 1, j 0; i m; i) { while (j 0 p[i] ! p[j]) j pi[j - 1]; if (p[i] p[j]) j; pi[i] j; } return pi; }上面这段计算的是前缀函数也就是定义一。如果你要的是定义二就先把pi计算出来再转成[ -1 ] pi[0..m-2]的形式。一定要看清题目给的是哪一种。3. 从一道贪心题看区间调度与排序的底层思维3.1 题目还原课程安排最少教室数量第二道编程题我印象里和“排课”有关。大致题意是一堆课程每门课有开始时间 start[i] 和结束时间 end[i]同一间教室同一时刻只能上一门课问要安排所有课程最少需要多少间教室。这其实是经典“会议室问题” (Meeting Rooms II)。放在猿辅导的场景里很自然因为在线教育平台确实需要调度直播课和老师资源。题目没有绕弯子看你能不能很快抽象出“区间重叠最大数”这个模型。3.2 为什么贪心可行排序的关键作用第一次见这类题可能会想用二维数组存所有区间再双重循环统计重叠但这样是O(n^2)的复杂度数据量一大就超时。正确的解法是贪心 最小堆。核心思路是先把所有课程按开始时间排序然后从左到右依次安排。使用一个小根堆维护当前已经占用教室的课程结束时间。遍历到新课时如果堆顶课程的结束时间小于等于当前课的开始时间说明最空闲的那间教室已经腾出来了可以复用否则说明当前所有正在上课的教室都无法空出来需要新开一间教室。为什么这里贪心是成立的因为按开始时间排序后我们每次处理的都是当前最早开始的课程使用堆顶得到的是“最早结束的占用教室”。只要最早结束的教室都没法复用那其他教室更不可能复用所以必须新开教室。这个逻辑是局部最优递推到全局最优的经典例子不需要回溯。3.3 代码实现与边界验证下面给出一个Python参考实现。注意区间端点重合的问题一门课是 [1, 5)另一门是 [5, 6)它们不冲突因为前一门在5点结束后一门在5点开始。所以判断条件是start heap[0]就可以复用。import heapq def minMeetingRooms(intervals): if not intervals: return 0 intervals.sort(keylambda x: x[0]) heap [] for start, end in intervals: if heap and start heap[0]: heapq.heappop(heap) heapq.heappush(heap, end) return len(heap)这个代码简洁但有几个易错点要自查输入为空直接返回0。排序时要按开始时间升序不是结束时间。比较的是start heap[0]还是start heap[0]取决于题目对“同时”的定义。如果结束的瞬间可以用来开始的下一门课用如果必须严格结束之后才能开始也就是不能在同一时刻重叠也通常用因为结束时刻和开始时刻相同不算占用。如果题目明确说明两个课程在同一时刻边缘也算冲突才需要用。小根堆中存的是结束时间不是教室编号。因为只有结束时间才能决定是否空闲。笔试现场写完主体后一定要自己造几个用例验证比如intervals [[0, 30], [5, 10], [15, 20]]期望答案是2。另外可以试一个全重叠的用例[[1, 4], [2, 5], [3, 6]]期望答案是3。这些边界测试在OJ系统里不会主动给你漏了就容易错。4. 动态规划另一道笔试真题的递推与优化4.1 题目场景化还原第三道编程题在“算法岗三”里是一道动态规划原题不一定完全出现在公开题库里但考法很经典。我把场景稍微包装一下假设有一串学习计划第i天如果学习某门课可以获得 values[i] 的收益但不能连续两天学习问一段连续日期内能获得的最大收益。实际上这就是“打家劫舍”的变体只是换了一个教育产品的壳。核心模型是一个数组每个元素可以选择拿或不拿但不能同时拿相邻两个元素求最大和。4.2 状态定义与转移方程推导动态规划的第一步永远是明确状态。设 dp[i] 表示从第0天到第i天能获得的最大收益。对于第i天只有两种情况选择学习第i天那么第i-1天不能学习收益是dp[i-2] values[i]。不选择学习第i天那么最大收益就是dp[i-1]。因此转移方程为dp[i] max(dp[i-1], dp[i-2] values[i])初始化要特别注意dp[0] values[0]因为只有一天时学这一天就是最大收益dp[1] max(values[0], values[1])前两天不能同时学只能取更大的一天。如果数组长度只有1直接返回 values[0]只有2返回前两天的较大值。这就是动态规划最典型的“选或不选”模型。很多同学能写出递归但写不出迭代是因为没有先把状态定义清楚导致边界一塌糊涂。笔试中时间紧建议先把dp数组的长度、初始值写出来再写循环。4.3 空间优化与易错点事实上这个题不需要O(n)的dp数组因为每次只依赖前两个状态用两个变量滚动即可。比如def maxStudyValue(values): if not values: return 0 n len(values) if n 1: return values[0] prev2 values[0] prev1 max(values[0], values[1]) for i in range(2, n): cur max(prev1, prev2 values[i]) prev2, prev1 prev1, cur return prev1这个版本空间复杂度是O(1)。我在笔试时容易犯的一个低级错误是写循环的时候忽略了n 1的分支导致在values[1]上越界。后来养成了习惯凡是动态规划题先处理空数组和长度为1的情况再进入主逻辑。动态规划的题目变化很多但“选或不选”这个套路覆盖了非常多的考题比如背包问题、最长上升子序列、股票买卖。备考时不需要把每种题都背一遍而是要训练自己从题目描述里抽出“选择”和“限制条件”。看到“不能相邻”“最多一次”“不超过容量”这类关键词立刻就能往状态转移上靠。5. 选择题考点速记与避坑清单5.1 机器学习与深度学习概念题算法岗三的选择题里机器学习概念占了不小的比例。这类题不涉及手推公式但需要你对常见算法有正确的理解。比如监督学习和无监督学习的区别有标签是监督无标签是无监督。过拟合的解决方式增加正则、增加数据、简化模型、交叉验证而不是盲目增大模型复杂度。Bagging和Boosting的区别Bagging是并行训练多个基模型再投票Boosting是串行训练并关注前面样本的错误。激活函数 Sigmoid、ReLU、Tanh之间的特点尤其是ReLU在正区间的梯度恒为1能缓解梯度消失。我建议你做一个速记表把高频概念分类整理。下面是部分内容概念一句话记忆过拟合训练集好、测试集差模型太复杂或数据太少正则化给损失函数加惩罚项限制参数大小交叉验证把训练集切分轮流做验证集KNN基于距离投票不需要显式训练K-Means无监督聚类迭代更新质心SVM找最大间隔超平面核函数处理非线性梯度下降沿负梯度方向更新参数随机森林Bagging 决策树这些概念在笔试中出现频率很高而且往往不是单纯问定义而是给一个场景让你判断该用什么算法。比如“有一批没有标签的学生行为数据想自动分成几类”答案就是聚类算法而不是分类算法。5.2 数据结构与经典算法概念题除了机器学习数据结构和经典算法更是重头。印象里选择题有考到排序算法的稳定性、堆排序建堆过程、二叉树的遍历顺序、哈希冲突解决方案等。下面这张表是排序算法的核心结论校招笔试百试百灵排序算法平均时间复杂度最坏时间复杂度空间复杂度稳定性冒泡排序O(n^2)O(n^2)O(1)稳定选择排序O(n^2)O(n^2)O(1)不稳定插入排序O(n^2)O(n^2)O(1)稳定快速排序O(n log n)O(n^2)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^2)但平均是O(n log n)。堆排序空间复杂度是O(1)但稳定性差。选择题如果要求“稳定且O(n log n)”就要选归并排序。另外KMP、二分查找、Dijkstra这类算法也会作为选择题出现但一般考复杂度或某个具体步骤不会真的让你写完整代码。比如KMP的next数组计算刚才已经详细讲过。二分查找则要注意循环条件是left right还是left right这直接影响是否漏判边界。5.3 工程优化算法小题这套卷子还出现了一些听起来像“从业务里摘出来的”算法概念题比如粒子群算法原理、音频重采样算法、PID算法在某个系统中的作用、规则引擎Drools的Rete算法等。这类题其实并不要求你会推导更多的是考察知识广度。我当时对粒子群算法只知道一个大概它模拟鸟群觅食每个粒子根据个体最优和全局最优更新速度和位置。但选择题偏偏问的是“粒子群算法中每个粒子的速度更新受哪些因素影响”如果你完全没听过就只能靠排除法蒙。这里给一个经验准备算法岗笔试时不要只看纯数据结构最好把常见优化算法和工程算法的“一句话原理”过一遍。比如卡尔曼滤波是递归状态估计、重采样是改变音频采样率、PID是比例积分微分控制、Rete是一种高效规则匹配算法。不需要会实现但看到名字不能空白。6. 限时答题的临场策略与复盘心得6.1 时间分配建议90分钟听起来不短但三到四道编程题加上一堆选择题时间其实很紧张。我当时的策略是先快速过一遍所有题目标记出哪些题有思路哪些题需要更多时间。选择题尽量控制在25分钟以内因为每道题平均不到两分钟纠结太久只会挤占后面编程题的时间。编程题分配上第一道基础题建议不超过15分钟第二道中等题不超过25分钟第三道难题可以给到30分钟。如果某道题卡了超过10分钟没有新思路先跳过做完其他题再回头。很多OJ系统可以反复提交所以即使不能保证满分先把能拿的用例过了也是好的。6.2 我踩过的坑和事后总结复盘时我发现有几个问题特别值得提基本都是“看起来不重要但实际丢分严重”的细节。第一KMP的next数组定义没有先确认。选择题里给的是“next[i]定义为最长相等前后缀长度”我却按失配跳转的结果去算差点选错。好在多看了一眼题干。笔试题里这类定义差异非常常见一定要把题目给出的定义读清楚再动手。第二贪心排序的边界。课程时间排序时如果开始时间相同需要额外考虑如何处理结束时间。有些变体会要求按结束时间排序但经典会议室问题按开始时间排序就够。如果你一开始用的是双重循环的暴力法即使逻辑正确遇到大数据量也可能超时所以最好直接用堆的解法。第三动态规划初始化遗漏。前面提到过dp[1]的处理很多人在纸上推公式很顺一到代码就忘。建议每道DP题都写一个固定模板空数组、长度1、长度2然后才是循环。6.3 给后来人的刷题建议如果你现在还在备考算法岗我建议不要盲目追求刷题数量而是分类刷题每类题总结出通用模板。按优先级排序校招笔试最常考的是数组与双指针字符串包括KMP、回文串排序与堆贪心算法动态规划背包、子序列、打家劫舍类二叉树遍历与递归图论基础Dijkstra、并查集、拓扑排序猿辅导这种互联网公司的算法岗还有一点与纯后端开发不同它会考一定比例的机器学习基础。所以你最好同时复习一下《统计学习方法》前几章的内容重点是感知机、KNN、朴素贝叶斯、决策树、SVM、集成学习。不需要会推导所有公式但要知道每种算法的适用场景、优势和劣势。最后再分享一个小技巧。在线笔试环境下输入输出格式经常出问题尤其是Java和C的同学很容易卡在解析一行多组数据上。建议提前背熟三种常用输入模板整数数组、字符串数组、二维数组。Python虽然方便但要注意strip()去掉行尾空格否则字符串比较会出现隐蔽bug。别小看这些细节很多同学栽了跟头之后才意识到算法题会做和能满分中间隔着一堆工程习惯。