猿辅导算法岗笔试复盘：贪心、KMP、Dijkstra与动态规划全解析

2020年秋招那阵子我在牛客网上刷到猿辅导的算法岗笔试邀请系统提示“猿辅导2020校招笔试(算法岗一)”一共三道编程题加若干选择题限时两小时。说实话看到这个配置我反而松了口气——没有上来就让人写一个大项目而是老老实实考算法基本功。这场笔试给我留下的印象是题型设计比较典型基本覆盖了算法岗笔试最常考的那几类问题——贪心、字符串匹配、图论最短路、动态规划外加一些机器学习基础。回头复盘这套卷子虽然不算难但陷阱不少值得好好拆一拆。这篇文章不打算只贴答案我想从“为什么这么考”“考场上容易踩什么坑”“下次遇到同类题怎么秒反应”三个角度把这份笔试题完整复盘一遍。无论你是在准备秋招、春招还是单纯想检验一下自己的算法功底这篇复盘应该都能派上用场。1. 笔试概览与题型分布算法岗笔试到底考什么1.1 整体结构与时间分配我当时参加的这场考试整体结构是“单选题 多选题 编程题”但编程题占大头总分大概在100分。选择题主要围绕数据结构、操作系统、网络但算法岗的卷子里穿插了相当比例的机器学习内容比如KNN、K-Means、贝叶斯这些概念题。编程题三道限时总共两小时。这里要给所有准备笔试的同学一个建议拿到试卷先花三分钟通读所有题目确认每道题的分值和难度然后决定答题顺序。不要一上来就死磕第一题。我自己的经验是“先易后难先拿能拿的分”如果一道题看了两分钟还没有思路先跳过把后面的基础题做完再回来看。另外要注意的是选择题里往往会埋一些“看似多选题、实际单选”的题目或者反过来题干里不写“多选”但选项明显不止一个正确答案。这种题在牛客网等在线笔试系统上很常见要仔细看清楚题目要求别凭直觉答题。1.2 题目难度阶梯与得分策略从这场笔试来看猿辅导的题目设计其实有很明显的难度阶梯——不难但层层递进。第一道编程题是常规的贪心排序属于送分题第二道是字符串匹配考察KMP算法的理解第三道是图论最短路需要堆优化Dijkstra或者DP拓扑的思路。整体来说如果基本功扎实两小时内做完是来得及的。这里要强调一下“AC率”这个概念。笔试系统里能看到自己的提交状态很多人会反复提交一个超时的代码白白浪费大量时间。正确的做法是先把暴力解法写出来确保正确如果数据规模允许就提交如果明显会超时再去优化。我见过太多同学在TLE之后反复调试同一个思路而不愿意换个角度想最后时间全耗在上面。考察方向典型题目核心考点时间复杂度要求贪心任务调度排序关键字选择O(nlogn)字符串KMP求next数组next数组定义与求法O(n)图论单源最短路径堆优化DijkstraO((nm)logn)动态规划最长上升子序列状态设计与优化O(nlogn)这道题的难度分布其实在提醒所有求职者算法岗笔试不是竞赛不需要你掌握什么高深莫测的冷门算法而是希望你在限时压力下能快速识别题目背后的模型并写出足够高效的解法。如果连基础的数据结构和经典算法都没吃透那基本告别算法岗笔试了。2. 编程题复盘四类高频题型的思路与实现2.1 贪心任务调度的排序关键字陷阱笔试里这道题大概是这样有n个任务每个任务有一个开始时间和结束时间同一时刻只能做一个任务问最多能完成多少个任务。这个问题的经典解法已经烂大街了——按结束时间从小到大排序然后依次选择结束时间最早且不冲突的任务。但笔试里真正刷人的地方在于为什么不是按开始时间排序为什么不是按时长排序大多数人靠背答案能写对但一旦题目变形就垮。比如把问题改成“最少需要多少台设备才能完成所有任务”答案就变成“按开始时间排序最小堆维护当前设备的最早空闲时间”和第一问完全相反。如果第一问你按开始时间排序第二问你按结束时间排序那两题都得挂。这类变形题在笔试里特别常见考的就是你有没有真正理解贪心的取舍逻辑。我贴一段最基础的任务调度代码大家重点看排序关键字的处理def max_tasks(tasks): # tasks: [(start, end), ...] tasks.sort(keylambda x: x[1]) # 按结束时间升序 count 0 current_end float(-inf) for start, end in tasks: if start current_end: count 1 current_end end return count当时我在考场上做这道题大概只花了5分钟但旁边的同学跟我交流时说他卡了很久——因为他第一反应是按开始时间排然后局部最优和全局最优对不上越改越乱。这就是典型的“知道贪心但不知道贪心贪的是哪个维度的值”。2.2 字符串KMP的next数组是“背了也会错”的考点第二道题印象很深题目直接给了模式串pabacaba让计算next数组。这里就有一个非常大的坑next数组在不同教材里有两种定义一种是“最长相等前后缀长度”一种是“失配时跳转位置”。如果不先看清楚题目给的公式定义直接套自己背过的模板结果一定会错。我用最长相等前后缀这一定义来算一遍。所谓next[i]表示模式串前i个字符下标从0开始组成的前缀子串中最长的相等前后缀长度。因为前缀和后缀不能是子串本身所以next[0]通常规定为-1或0看题目。pabacaba逐位计算next[0] -1约定值或有的题设为0next[1]前缀子串a最长相等前后缀长度为0next[2]前缀子串ab无相等前后缀0next[3]前缀子串aba最长相等前后缀是a长度为1next[4]前缀子串abac0next[5]前缀子串abaca最长相等前后缀是a1next[6]前缀子串abacab最长相等前后缀是ab2next[7]前缀子串abacaba最长相等前后缀是aba3如果题目里定义的next[i]是“当第i位失配时模式串应该跳转到的位置”那通常在经典next数组的基础上整体右移一位并且把next[0]设为-1。KMP的匹配过程就依赖这个跳转数组。笔试时一定要仔细看题面给出的定义不要想当然。def build_next(p): m len(p) nxt [0] * m j 0 for i in range(1, m): while j 0 and p[i] ! p[j]: j nxt[j - 1] if p[i] p[j]: j 1 nxt[i] j return nxt p abacaba print(build_next(p)) # 输出: [0, 0, 1, 0, 1, 2, 3]这段代码输出的是以“最长相等前后缀长度”为语义的next数组next[0]0如果题目用的是“失配跳转位置”的语义需要在前面补一个-1再整体右移。很多人在这一步踩坑就是因为没有分清这两种定义。2.3 图论堆优化Dijkstra的写法与适用边界第三道编程题是典型的单源最短路径问题给定n个节点、m条边求从起点到终点的最短距离。n和m的数量级大概是10^5所以Floyd肯定不行朴素Dijkstra的O(n^2)也危险必须上堆优化Dijkstra复杂度O((nm)logn)。堆优化的核心思路是用优先队列维护“当前已知最短距离最小的未确定节点”每次从堆顶取出一个节点如果它已经被松弛过就跳过否则用它去更新相邻节点的距离。这里有一个很容易写错的细节优先队列默认是大顶堆存距离时要存负值或者用自定义比较器否则取出来的就是“最远”而不是“最近”的节点整个算法直接废掉。import heapq def dijkstra(n, edges, start): graph [[] for _ in range(n)] for u, v, w in edges: graph[u].append((v, w)) dist [float(inf)] * n dist[start] 0 pq [(0, start)] while pq: d, u heapq.heappop(pq) if d dist[u]: continue for v, w in graph[u]: nd d w if nd dist[v]: dist[v] nd heapq.heappush(pq, (nd, v)) return dist这里要注意Dijkstra只适用于边权非负的图。如果题目出现负权边哪怕只有一条Dijkstra也会给出错误结果应该改用Bellman-Ford或SPFA。笔试里经常故意在题面里埋“边权可能为负数”这个条件来筛选那些只会背模板的人。另外如果你判断出图满足“有向无环”这个条件那也可以用拓扑排序动态规划做最短路按拓扑序处理每个节点用当前节点的dist去松弛所有出边。这个做法在DAG上比Dijkstra更简洁也更容易证明正确性。笔试中多掌握一种解法就多一层保险。2.4 动态规划为什么LIS的O(nlogn)解法值得掌握动态规划题在算法岗笔试里几乎是必考的。这道题考的是最长上升子序列LIS。最经典的解法是O(n^2)的DP状态转移方程是dp[i] max(dp[j] 1)其中j i且nums[j] nums[i]但一旦n达到10^5O(n^2)直接TLE必须用“贪心二分”优化到O(nlogn)。优化的核心思路是维护一个数组tailstails[len]表示长度为len的上升子序列中最小的末尾元素值。这个数组是单调递增的所以可以二分查找当前元素应该替换的位置。整个过程本质上是“贪心地把每个元素放到它该放的位置”理解这一点比背代码重要得多。def length_of_lis(nums): import bisect tails [] for x in nums: pos bisect.bisect_left(tails, x) if pos len(tails): tails.append(x) else: tails[pos] x return len(tails)笔试里LIS的变形非常多比如“最长不下降子序列”“最长公共子序列”“最少拦截系统”等本质上都是同一个模型加上一点改动。能在考场上快速识别出“这是LIS模型”远比会背一种解法更有价值。比如“最少拦截系统”那道经典题问的是按顺序拦截导弹最少需要几套系统本质上就是求最长不下降子序列的长度。熟悉模型你就能在考场上省下大量推公式的时间。3. 高频考点补全数据结构基础决定笔试下限3.1 排序算法从冒泡到堆排序的理解层次热搜词里“冒泡排序算法c”“堆排序算法”“快速幂算法c”这些词说明一个事实算法岗笔试对排序算法的考察往往不是让你手写快排而是考你“对排序算法的理解层次”。比如选择题经常问堆排序建堆的时间复杂度是多少快排的最坏情况发生在什么输入下归并排序的额外空间复杂度是多少这些问题的答案光靠背是不够的。堆排序建堆是O(n)而不是很多人以为的O(nlogn)快排最坏情况出现在基准选择极度不均衡时比如对已经有序的数组每次都选第一个元素作为基准退化成O(n^2)归并排序的额外空间是O(n)这些细节都是高频考点。我建议准备笔试时把每种排序算法整理成一张表写清楚时间复杂度最好、平均、最坏、空间复杂度、是否稳定、适用场景。比如数据规模小且基本有序时插入排序可能比快排还快需要稳定排序时归并排序是首选需要原地排序时堆排序和快排更合适。这些判断在实际工作中选型也很有用。3.2 树与图遍历、拓扑排序与并查集树和图的题目在笔试选择题里几乎是必出的。树的遍历前序、中序、后序、层序是基本功图的部分拓扑排序、并查集、二分图判定染色法都是热门考点。特别是“拓扑排序”和“有向无环图”的关系很多选择题喜欢在“有环图无法拓扑排序”这个结论上做文章。并查集则是“团伙问题”“连通分量问题”等场景的标准解法。有的同学觉得并查集不重要但事实上笔试里“判断两个节点是否连通”“求连通分量个数”这类题目用并查集写起来比DFS/BFS更简洁也不会超时。如果让我给一个优先级判断我会说树的三种遍历必须闭着眼睛能写图论里面拓扑排序、并查集、最短路这三板斧是你必须掌握的底线。贪心算法和二分图匹配这些高级内容笔试里出现的频率相对低一些但一旦出现会的人就能拉开差距。3.3 查找与二分边界条件是最容易翻车的地方二分查找是笔试里“看起来简单、写起来全错”的重灾区。多少人写二分查找都遇到过死循环或答案差1的问题原因几乎都出在边界条件的处理上while循环用left right还是left right更新区间时mid要不要加1或减1一个我个人的经验是每次写二分前先在注释里写清楚“我要找的是第一个满足条件的值还是最后一个满足条件的值”然后根据这个语义去定边界。语义明确了代码就不会错乱了。这个经验帮我避免了很多次“看似AC、实际WA”的尴尬。下面这个模板我建议直接背熟# 找第一个 target 的位置 def lower_bound(nums, target): left, right 0, len(nums) # [left, right) while left right: mid (left right) // 2 if nums[mid] target: left mid 1 else: right mid return left这里用的是左闭右开区间好处是退出循环时left一定等于right不用纠结该返回哪一个。如果题目要求的是“最后一个 target 的位置”把判断条件反过来写返回left - 1即可。记住这一个模板比死记多个版本的代码可靠得多。4. 算法岗特有的机器学习与模型考察4.1 KNNk值选择、距离度量与特征归一化算法岗笔试和开发岗最大的区别就在机器学习这部分。KNN是最常考的基础算法之一原因不是它有多难而是它最能考出“你有没有真正理解机器学习的基本流程”。比如选择题会问KNN中的k值过大会导致什么答案是模型过于平滑、决策边界粗糙容易欠拟合。KNN还有两个非常容易被忽略的细节一是距离度量欧氏距离、曼哈顿距离、余弦相似度的适用场景不同二是特征必须归一化否则量纲差异会直接扭曲距离计算。笔试里常有一道选择题给出两个特征比如年龄和收入问为什么不直接跑KNN答案就是“特征量纲差异过大需要归一化”。如果你在笔试或者面试中遇到KNN的题目建议多往“懒惰学习”“非参数方法”“基于实例的学习”这些概念上靠这些词能侧面体现你的知识广度。KNN本身没有显式训练过程所有计算都发生在预测时这也导致了它在样本量大时预测速度非常慢。4.2 K-Means与聚类K值怎么选、为什么怕初始中心聚类算法里K-Means的出镜率极高。笔试常考的点有K-Means的迭代流程、K值的选择方法肘部法则、K-Means对初始中心敏感、K-Means不适合处理非凸簇。选择题还会把K-Means和KNN放在一起考让大家区分K-Means是无监督学习KNN是有监督学习一个是聚类一个是分类。这两个名字太像了不理解的考生很容易混。K-Means的迭代流程大致是随机选K个初始中心然后把每个样本分配到距离最近的中心接着根据分配结果重新计算中心反复迭代直到中心不再变化。这中间有两个细节容易被问一是初始中心的选择对结果影响很大所以实际工程中经常用K-Means来初始化或者跑多次取最优二是聚类的评价指标比如轮廓系数是笔试和面试都可能延伸考的点。4.3 BM25与信息检索算法搜索场景的入门考点因为猿辅导是教育科技公司招聘算法岗时偶尔也会涉及搜索、推荐方向的基础。BM25这个算法在热搜词里出现了说明很多算法岗位确实会考察信息检索相关的知识。BM25的核心思想是一个词在文档中出现的频率越高、文档越短、且这个词在整个文档集合中越稀有这个词对当前文档的评分贡献就越大。理解这个思路比背公式重要因为笔试很少让你手推BM25公式但会给你一个场景让你判断“文档相关性排序”。当年我准备这块时是把BM25、TF-IDF、向量空间模型放一起对比着记的。TF-IDF是BM25的简化版BM25引入了文档长度归一化和词频饱和效应实际效果通常更好。如果你时间有限优先把BM25和TF-IDF的区别搞清楚就足够应付大多数笔试了。4.4 智能优化算法粒子群、模拟退火的概念级考察智能优化算法粒子群、模拟退火、遗传算法在笔试里通常以概念题出现比如问“模拟退火的温度T的作用是什么”“粒子群算法的速度和位置更新公式中惯性权重的作用是什么”。这类题不需要你能从头实现但要知道它们解决什么问题、基本流程是什么、关键参数有什么含义。如果时间有限优先掌握模拟退火和粒子群的概念即可。模拟退火的核心是“以一定概率接受更差的解”这个概率由温度T控制T越高接受差解的概率越大随着迭代次数增加T降低算法逐渐收敛到稳定解。这个“前期允许乱跳、后期逐渐收敛”的思路在很多优化问题里都有应用。粒子群的核心则是“每个粒子根据自身历史最优和全局最优来更新速度”惯性权重越大全局搜索能力越强越小则局部搜索能力越强。能把这些关键词串起来说清楚笔试小题基本就能拿分。5. 踩坑实录我在笔试中实际遇到的那些送命题5.1 读题不仔细把升序看成降序把非递减看成递增这是我参加笔试时的真实经历。有一道题题目里明确写了“非递减序列”我直接当成“上升序列”做结果一半的测试用例没过。后来我复盘发现很多同学在笔试中不是不会做而是读题时漏掉了关键限定词。“非递减”和“递增”差了一个等号答案差了一个二分查找的边界条件。“最多”“最少”“恰好”这些词的限定也直接决定你用的是贪心、DP还是二分。读题花30秒比提交后debug半小时划算得多。这里给一个实用建议拿到编程题先把题目里出现的限定词全部圈出来尤其注意“非递减/递增”“不重叠/重叠”“最多/最少/恰好”“可以/不可以重复使用”。这些词每一个都可能让解法完全不同。我后来养成了“读完题先在草稿纸上把关键条件抄一遍”的习惯看似浪费时间实际上大大降低了写错方向的风险。5.2 时间复杂度估算失误O(n^2)在10^5面前就是TLE有一道题我一开始用O(n^2)写的本地样例全过提交后直接TLE。原因很简单n10^5O(n^2)10^10在只给2秒的OJ上是绝对跑不完的。这是算法岗笔试最高频的“送命题”。我后来养成了一个习惯看完数据范围先估算复杂度如果O(n^2)过不了立刻去想O(nlogn)或O(n)的解法绝不在暴力解上浪费时间。有一个快速判断方法1秒大概能跑10^8次简单运算2秒就是2×10^8。如果n10^5O(n^2)是10^10超了100倍如果n10^4O(n^2)是10^8勉强能过如果n10^6O(nlogn)大约是2×10^7很轻松。每次写完代码先拿这个标准卡一下自己可以有效避免“本地跑得动OJ超时”的尴尬。5.3 KMP的next数组定义混乱同一道题可以有两套答案我在第2章提过next数组有两种常见定义。笔试时如果题面没给公式纯粹说“计算next数组”那它可能采用我们常用的“最长相等前后缀长度”定义但如果题面里写了“next[i]表示失配时跳转的位置”那数组的值会整体不同。我见过很多同学因为没看定义直接套模板白白丢了一道送分题。所以遇到这类概念题第一件事永远是确认题面中的定义。如果你在网上刷题你会发现不同平台的KMP模板有的返回next数组时第一位是-1有的第一位是0甚至有的把数组取名为prefix、pi、fail。这都不是Bug而是定义不同。备考时最好把两种定义都准备一套写法并且能快速转换这样无论在哪个平台笔试都不会慌。5.4 优先队列的大顶堆陷阱与Dijkstra的负权坑有一道与Dijkstra相关的题我在考场上因为贪图快直接用了一个普通的数组来保存距离导致时间复杂度飙升。而堆优化的时候如果不小心把优先队列当成大顶堆用取出的节点永远是距离最大的那个整个算法会得到一个错误答案而且本地小数据样例还看不出来。这是我在实际写代码时踩过最深的坑之一。优先队列存距离时一定要记得用“负值取反”或者自定义比较器。另外还要注意Dijkstra的适用边界负权边出现时Dijkstra直接失效。我当时在复习时专门做了个对比实验用一个带负权的三节点图去跑Dijkstra结果发现它给出了一个错误的“最短路径”。这个实验让我彻底记住了Dijkstra的适用范围比死记结论有效得多。笔试里出现“负权边”“负环”这些词时基本可以断定考的是Bellman-Ford或者SPFA。5.5 二分查找死循环一个看似无解的Bug二分查找中还有一个经典坑当更新区间时用了left mid和right mid如果区间长度收缩到1时就会陷入死循环。正确的做法是在left mid的场景下计算mid时要向上取整mid (left right 1) // 2。这个细节笔试不会直接考但如果你在编程题里写了二分查找它极有可能成为隐藏的Bug来源。我记得有一次做“旋转数组的最小值”这类题就因为没注意向上取整还是向下取整本地测试死循环了十分钟最后才发现是mid的计算方式导致left永远不会推进。从那以后我总结出一个口诀如果你在二分里用了left mid那就把mid向上取整如果你用的是left mid 1那mid向下取整。这个口诀帮我解决了一类非常容易卡住的Bug。6. 复盘后的备战建议如果让我重新准备一次6.1 夯实基础数据结构是算法岗的底线算法岗笔试到最后拼的几乎都是数据结构的基本功。数组、链表、栈、队列、哈希表、树、堆、图这八大结构必须能随手写出代码。我个人建议把每个数据结构的基本操作插入、删除、查找、遍历都整理成自己的模板笔试时直接调用而不是现场去推。比如树的三种非递归遍历我建议至少写一遍完整的实现。为什么很多同学觉得树的非递归遍历难因为要用栈模拟递归的过程一旦写错就容易死循环。但如果平时把模板整理好了笔试就能直接默写。我当时整理了一整套模板包括链表反转、快排、归并、二分查找、堆排序、Dijkstra、KMP、并查集、拓扑排序考试时遇到类似的题直接往模板上套省下大量思考时间。6.2 系统刷题不在于多而在于归类刷题这件事量确实重要但更重要的一定是归类。我建议按“题型”刷而不是按“难度”刷贪心、二分、双指针、动态规划、图论、字符串、数学每类题型刷透20~30题总结出这类题的常见套路。比我当初漫无目的地按LeetCode题号顺序刷效率高得多。这里分享一个我后来一直在用的刷题方法每做完一道题不急着刷下一道而是在题目的注释里写下“这道题属于什么模型关键突破口是什么如果题目改一个条件解法会怎么变”这样做三遍以上你会发现很多题目其实是同一个模型的马甲。比如“接雨水”和“柱状图最大矩形”一个用单调栈一个也可以用单调栈比如“最长上升子序列”的贪心二分优化和“俄罗斯套娃信封”问题几乎一模一样。6.3 笔试环境模拟从会写代码到会考试有一件很多同学忽略的事笔试环境和你平时写代码的环境差别很大。牛客网的笔试系统大多是ACM模式需要自己处理输入输出而LeetCode是核心代码模式只写函数就可以。差距看起来不大但一旦你习惯了LeetCode的输入输出到了牛客网笔试时光是处理输入格式就能耗费大量时间。建议提前去牛客网刷几套真题适应一下“读入多组数据”“处理空行”“判断EOF”这些细节。我自己就吃过这个亏。第一次在牛客网上做模拟笔试时一道很简单的“两数之和”题目我因为不会处理input().strip()的边界情况提交了三次才过。从那以后我把常用的输入输出模板单独存了一个文件包括读整数、读一行数组、读多行每个模板都测过笔试直接复制粘贴基本不会出错。6.4 算法原理深度机器学习部分别只背公式猿辅导这类互联网公司的算法岗笔试机器学习考点一般不会太深但一定会考“理解”。与其死记硬背KNN、K-Means、贝叶斯的公式不如理解每个算法的前提假设、适用范围、优缺点。笔试选择题最喜欢出的就是“下列哪种场景下KNN不适用”这类需要理解的问题。我备考时做了一个很笨但很有用的练习拿一张白纸不看任何资料把每个算法的流程、公式、适用场景、优缺点写出来然后和资料对照补上遗漏的点。这样做一轮之后我对K-Means和KNN的区别、决策树和信息增益的关系、朴素贝叶斯为什么“朴素”这些概念都清晰了很多笔试遇到相关题目基本不用犹豫。印象很深的是这场笔试让我意识到一件事算法岗笔试真正的分水岭不在于你掌握了多少奇技淫巧而在于基础是否扎实、读题是否仔细、复杂度估算是否准确。很多同学把大量精力花在钻研难题上结果在KMP的next数组定义、Dijkstra的适用边界、二分查找的边界条件这些基础细节上翻车非常可惜。如果让我给准备秋招的同学一个最实际的建议就是从现在开始每周固定做两三场完整的模拟笔试严格按照考试时间来然后认真复盘每一道错题。光看不练永远不知道自己哪里不会只有真正在限时压力下写过代码、踩过坑、改过Bug笔试题对你的杀伤力才会真正降下来。