大厂笔试刚结束那几天牛客网上全是吐槽帖。有人说猿辅导的算法笔试题目看着眼熟真动起手来却卡在边界条件上也有人觉得前面选择题偏基础编程题才是真正拉开差距的地方。我去年秋招投了猿辅导的算法岗正好赶上2023校园招聘笔试批次当时做的是“算法一”这套卷子。整体感受是考察范围不偏门但非常考验基本功扎不扎实尤其是对数据结构底层理解的深度。这篇就来复盘一下我准备这套笔试题的过程和心得围绕高频考点、做题策略、典型题目拆解以及考后反思这几个维度展开。如果你也在准备教育科技类公司的算法岗笔试希望这篇能帮你少走一些弯路。1. 猿辅导算法笔试的考察逻辑不刷偏题怪题专盯基础功底先聊聊这套笔试题给我的整体印象。猿辅导作为在线教育领域的头部公司技术栈和业务场景决定了他们的算法考察有自己的侧重点。教育业务涉及到大量的用户行为分析、题目推荐、课程调度、智能批改等场景所以笔试中出现的算法题往往不是单纯背模板就能过的。从我做过的“算法一”这套卷子来看整体结构大致分两部分第一部分是客观选择题涵盖数据结构、算法复杂度分析、计算机网络基础、操作系统基础知识第二部分是编程题通常两到三道难度从LeetCode中等题到困难题不等。有意思的是猿辅导的笔试很少出那种特别冷门的偏题怪题反倒是在基础算法上挖得很细。比如同一道排序题会追问不同数据规模下最优解法的变化同一个动态规划问题会考察状态转移方程的优化空间。这种出题思路其实和业务强相关——教育场景下的推荐系统、路径规划、资源分配问题说到底考验的就是这些基本功。我当时刷了不少历年校招笔试题发现猿辅导特别爱考这几类字符串相关的经典算法比如KMP、Trie树、字符串匹配变形题贪心策略与动态规划的边界判断尤其是“能不能贪”“怎么DP”这种思维层面的考察二叉树和图的遍历变体往往结合DFS和BFS的剪枝优化排序算法的理解和应用场景选择会问什么时候该用快排什么时候该用堆排这些知识点从名字上看都不陌生但真正的难点在于如何在有限时间内灵活运用。特别是“算法一”这套卷子编程题有一个共同特点数据规模给得比较大用暴力解法不仅会超时还会直接超出内存限制逼着你必须在算法设计上做出正确决策。所以我的第一条建议是准备猿辅导笔试重心放在基础算法的深度理解上不要花大量时间去刷冷门竞赛题。把握好这个方向笔试的复习效率会高很多。2. 从热门算法热搜词看高频考点哪些内容必须滚瓜烂熟翻一下最近算法类的热搜词能明显看出大家关注的重点集中在几个方向KMP算法、粒子群算法、PID算法、各种排序算法、机器学习与深度学习算法等。结合猿辅导笔试的真题特点我梳理了以下必须熟练掌握的知识点每一个都可能成为笔试中的得分点或失分点。2.1 字符串匹配KMP的next数组核心逻辑KMP算法是笔试中的“钉子户”几乎每年都会出现。热搜词里有一条很典型模式串pabacaba求next数组。这类题目考察的不是你能不能背出代码而是对next数组定义和求解逻辑的透彻掌握。先说next数组的定义笔试题里通常会明确next[i]表示模式串前i个子串中最长相等前后缀的长度注意具体定义不同试卷可能略有区别有的从0开始有的从-1开始。以abacaba为例我们需要对每个位置逐个分析位置0字符a前缀子串长度为1最长相等前后缀长度为0next[0]0位置1字符ab前缀a后缀b不相等next[1]0位置2字符aba前缀a后缀a相等最长前后缀长度为1next[2]1位置3字符abac前缀a和c不匹配长度为2时ab和ac不匹配next[3]0位置4字符abaca前缀a和后缀a匹配长度为2时ab和ca不匹配长度为3时aba和aca不匹配next[4]1位置5字符abacab前缀ab和后缀ab匹配长度为2再长就不匹配了next[5]2位置6字符abacaba前缀aba和后缀aba匹配长度为3next[6]3所以这个模式串的next数组是[0, 0, 1, 0, 1, 2, 3]。笔试如果考到这道题核心就是要理解“相等前后缀”这个概念——它决定了匹配失败后模式串可以安全跳过多少位置这是KMP相比暴力匹配效率提升的根本原因。我建议复习时把求next数组的代码自己手写一遍不要只看不写。笔试现场时间紧张如果对边界条件不够熟练很容易在while循环的判断逻辑上出错。2.2 排序算法的复杂度与稳定性笔试选择题的必考内容排序算法几乎占据了选择题的半壁江山。猿辅导的笔试题不会直接让你写快排代码而是会问不同场景下选择哪种排序更合适。从热搜词高频出现的“冒泡排序算法C”“堆排序算法”“快速排序”等来看大家比较关注的是具体实现但笔试真正考的是以下几个维度第一个维度是时间复杂度。冒泡排序、插入排序、选择排序平均都是O(n²)快排平均O(nlogn)但最坏会退化到O(n²)归并排序稳定在O(nlogn)堆排序也是O(nlogn)。第二个维度是空间复杂度。快排有递归栈的开销平均O(logn)最坏O(n)归并排序需要额外O(n)的辅助数组堆排序是原地排序空间复杂度O(1)。第三个维度是稳定性。什么是稳定性简单说就是相等的元素在排序前后相对位置不变。稳定的排序有冒泡、插入、归并不稳定的有选择、快排、堆排序。考试时容易混淆的是堆排序和归并排序。堆排序虽然空间表现好但它的比较和交换是跳跃式的不稳定归并排序借助额外空间换来了稳定性但空间开销大。今年笔试里我印象比较深的一道题是一个几乎有序的数组用什么排序效率最高答案是插入排序。因为插入排序在数组基本有序的情况下每次插入都比较接近最终位置整体时间复杂度接近O(n)。如果不理解这个场景很多同学会条件反射地选快排那就掉坑里了。2.3 动态规划与贪心策略编程题里的“分水岭”猿辅导的编程题基本是两道动态规划加上一道贪心算法的组合拳。难的不是识别出这道题该用DP而是状态定义和状态转移方程的设计。以“最长递增子序列”为例最经典的DP解法是定义dp[i]表示以第i个元素结尾的最长递增子序列长度。状态转移方程是dp[i] max(dp[j] 1)其中j i且nums[j] nums[i]。这个解法的时间复杂度是O(n²)。如果数据范围是10^5级别就必须优化到O(nlogn)——这是笔试中的一个关键分水岭。O(nlogn)的优化思路是维护一个“最小末尾值”数组tailstails[k]表示长度为k1的递增子序列中末尾元素的最小值。遍历每个数用二分查找在tails中找到第一个大于等于当前数的位置然后替换。这样tails的长度就是最长递增子序列的长度。笔试中如果没做过这个优化大概率会超时丢分非常可惜。再说贪心算法。贪心的难点不是实现而是证明“贪心策略是正确”的。笔试里常见的“区间调度问题”需要按结束时间排序每次选择最早结束且与当前区间不重叠的区间。这类题的代码往往不超过二十行但考察的是你对问题本质的理解。复习时一定要多问自己“为什么这个贪心策略是对的”多积累经典题目的证明思路遇到变形题才不会慌。2.4 机器学习与深度学习算法算法岗笔试的“隐藏加分项”现在很多公司算法岗笔试除了传统算法题还会在选择题中穿插ML/DL的基础题。猿辅导2023年这套卷子也不例外。热搜词里“机器学习算法”“深度学习算法”排得很靠前说明这是大家关注的焦点。从笔试角度看选择题中常考的知识点包括逻辑回归和线性回归的区别一个是分类模型一个是回归模型逻辑回归用了sigmoid函数输出概率过拟合的解决方法正则化、Dropout、数据增强、早停法梯度下降的几种变体批量梯度下降、随机梯度下降、小批量梯度下降常见激活函数的优缺点ReLU的死亡神经元问题、sigmoid的梯度消失问题这些内容在准备常规算法题之余必须花时间过一遍。我复习时看的是李航的《统计学习方法》加上吴恩达的课程笔记基本覆盖了大部分考点。不用贪多核心概念理解了、推导会了选择题就不会丢太多分。3. 编程题实战复盘从读题到AC的完整思考链路笔试最怕的不是不会做而是会做但没时间写完或者写完了但细节出错。这里复盘一下我当时做编程题时的完整思路过程重点分享在解题过程中的关键决策点和容易踩的坑。3.1 第一道题字符串压缩变形中等难度题目大致是给定一个字符串将连续重复的字符压缩成“字符出现次数”的形式比如aabcccccaaa压缩后变成a2b1c5a3如果压缩后的字符串长度不小于原字符串则返回原字符串。这题第一眼看起来非常简单很多人的第一反应就是遍历计数。但实际上它考察的核心细节有两个一个是压缩后长度与原字符串长度的比较逻辑另一个是“连续重复”这个条件相同字符不一定连续出现所以不能用一个全局计数器。我的解题思路def compress_string(s: str) - str: n len(s) if n 2: return s compressed [] count 1 for i in range(1, n): if s[i] s[i - 1]: count 1 else: compressed.append(s[i - 1] str(count)) count 1 compressed.append(s[n - 1] str(count)) result .join(compressed) return result if len(result) n else s这道题有个细节值得注意循环结束后最后一组字符需要在循环外手动处理因为循环只在字符发生变化时才输出前一段的统计结果。很多同学在笔试时漏掉最后一行导致最后一个字符的计数丢失白白丢分。另外一个隐藏考点是“压缩后字符串长度不小于原字符串则返回原字符串”这个条件的处理。有的同学会压缩之后再去比较长度这没问题但更高效的做法是在压缩过程中随时判断如果已经不可能短于原字符串了就提前终止。笔试时间紧张时这种微优化虽然不改变复杂度但能节省代码执行时间在测试用例较大时也更有保障。这道题属于“看似简单实则高分”的定位。多数笔试中等题都藏着一个关键思维点快速识别出它就能比其他候选人节省宝贵时间。3.2 第二道题课程表调度图论拓扑排序这道题来自经典OJ题变形给定若干课程的前置依赖关系判断是否可以完成所有课程。可以直接联想到LeetCode 207题“课程表”以及LeetCode 210题“课程表II”。题目描述接近后者除了判断可行性还要输出一种合法的学习顺序。如果输入是一个有向图节点表示课程边表示前置依赖关系那么问题本质上就是图的拓扑排序。拓扑排序的关键是层序删点每次找出所有入度为0的节点加入结果数组然后删除它们指向的边即对应邻接点的入度减1重复这个过程直到没有入度为0的节点。如果最终结果数组的长度不等于课程总数说明图中存在环无法完成全部课程。我当时的核心代码如下from collections import deque def find_order(num_courses: int, prerequisites: List[List[int]]) - List[int]: graph [[] for _ in range(num_courses)] indegree [0] * num_courses for course, pre in prerequisites: graph[pre].append(course) indegree[course] 1 queue deque([i for i in range(num_courses) if indegree[i] 0]) result [] while queue: node queue.popleft() result.append(node) for neighbor in graph[node]: indegree[neighbor] - 1 if indegree[neighbor] 0: queue.append(neighbor) return result if len(result) num_courses else []这道题的坑点主要在图的邻接表方向别搞反了有的题目给的是prerequisites[i] [a, b]表示学a之前必须先学b有的题目给的是a依赖b即b是先修课。读题时必须搞清楚边的方向否则拓扑排序出来的结果是反的甚至完全错误。另一个易错点是入度为0的节点可能不止一个此时可以按任意顺序处理不影响可行性判断但如果题目要求输出“字典序最小的学习顺序”就需要把队列换成优先队列最小堆。猿辅导这道题没有这个要求但我建议准备时顺手把最小堆版本练一下因为很多类似的题目会加这个条件。3.3 第三道题带约束的任务分配动态规划困难难度第三道编程题是整套卷子的压轴题难度明显上升。题目大致是有n个任务每个任务有不同的完成时间和收益每天只能做一个任务每个任务有一个截止日期求最大收益。这道题最直接的想法是按截止日期排序然后逐个考虑任务用动态规划状态表示“处理到某个任务时在某个时间点能获得的最大收益”。状态转移方程是dp[i][j] max(dp[i-1][j], dp[i-1][min(j - time_i, deadline_i - time_i)] profit_i)其中i表示第i个任务j表示当前时间点。但这里有个优化点如果直接用二维DP时间复杂度和空间复杂度都可能是O(n*m)在数据规模较大时很容易超时。优化思路是使用贪心堆的经典解法将所有任务按截止日期排序然后遍历每个任务维护一个当前已选任务的总耗时。如果加入新任务后总耗时超过当前任务的截止日期就把已选任务中收益最小的任务移除用当前任务替代前提是当前任务的收益更大。这个思路的本质是在满足截止日期约束的前提下尽量选择收益更高的任务组合。它用“最小堆”动态维护当前任务集合保证始终是一组可行且收益最大化的解。下面是核心代码import heapq def schedule_jobs(deadlines: List[int], times: List[int], profits: List[int]) - int: jobs sorted(zip(deadlines, times, profits), keylambda x: x[0]) heap [] current_time 0 total_profit 0 for deadline, time, profit in jobs: current_time time heapq.heappush(heap, (profit, time)) total_profit profit if current_time deadline: smallest_profit, smallest_time heapq.heappop(heap) total_profit - smallest_profit current_time - smallest_time return total_profit这里需要理解一个关键点为什么当前时间超出截止日期时移除的是收益最小的任务而不是耗时最长的任务因为我们的目标函数是收益最大化在总耗时不变或减小的情况下移除收益最小的任务对收益的损害最小。即便移除的任务耗时很短如果它收益最低也一样是最优的移除候选。这个“贪心堆”的组合在笔试题中出现频率极高建议重点掌握。很多类似的“安排任务最大收益”问题都可以用这个思路通杀。考试时如果时间充足也可以先用二维DP验证小数据规模下的正确性再改用堆优化处理大数据不过笔试时间有限直接写优化版本更划算。4. 笔试过程中的策略与细节如何稳住节奏多拿分很多同学笔试挂掉不是因为不会做题而是因为节奏乱、细节失误。这类主观因素其实完全可以通过策略调整来规避。这里分几个方面聊聊我的实战经验。4.1 时间分配选择和编程题各占多少时间合适猿辅导算法笔试的总时长一般是一个半小时到两个小时选择题大概有二十道左右编程题两到三道。我的策略是选择题不超过总时长的三分之一。选择题考察的知识点比较杂如果在一道题上卡住超过两分钟果断标记跳过先做后面的题最后如果有剩余时间再回头思考。编程题才是拉开差距的关键。我的建议是先花两三分钟把几道编程题都通读一遍判断题目的难度差异然后从最简单的那道开始动笔。这里有个容易犯的错误一上来就死磕最难的那道题结果最简单的都没时间写。个人的做题顺序原则是先把一道完整AC拿下来保证至少有一道题的分数到手再去做更难的题目。一道题AC的分数价值往往比“每道题都写了一半但全错”的价值高得多。4.2 调试技巧边界条件和数据范围是失分重灾区写代码时所有人都会在题目给出的示例用例上验证一遍但示例通常覆盖不到边界情况。根据我踩坑的经验这几个地方是高频失分点第一个是空输入。字符串为或数组为[]时很多代码会直接崩溃——要么数组越界要么返回错误值。规范的做法是在函数开头就处理空输入返回题目要求的默认值。第二个是单元素输入。比如字符串长度为1时压缩后的结果应该是什么数组只有一个元素时最长递增子序列的长度应该是1。这些看似简单的情况在代码里经常被漏掉分支。第三个是整数溢出。有的题目虽然用int存得下但中间过程比如乘法或者累加可能会溢出。建议在运算时统一用long long或Python的intPython int天然支持大数避免溢出导致的精度错误。第四个是大数据规模的超时。有些同学写的算法逻辑正确但时间复杂度是O(n²)当n跑到10^5时就会超时。笔试环境一般不会给太多运行时间所以提交前一定要估算复杂度如果明显过高就要考虑换更优算法。4.3 代码风格与注释虽然没有加分但能保命很多刚参加笔试的同学会忽略代码风格总觉得“能AC就行”但实际考试中代码风格影响的是你Debug的速度。变量名清晰、逻辑分层明确、关键步骤加注释能帮助你在回看代码时更快定位问题。我自己习惯用比较规范的方式写代码即使笔试时间紧张至少保证核心逻辑的注释写清楚。比如在写状态转移方程前先注释一行说明dp[i][j]的含义在贪心堆的更新步骤前注释说明“移除收益最小的任务以保持截止日期约束”。这样自己回看时能少花大量思考时间写错了也容易发现。5. 常见算法考点的横向对比一张表搞懂选择和填空题为了方便复习我把笔试中最常考的几组容易混淆的算法知识点整理成一张对比表帮助快速记忆和区分。算法时间复杂度平均空间复杂度稳定性典型应用场景冒泡排序O(n²)O(1)稳定数据量小、教学示范插入排序O(n²)O(1)稳定几乎有序的数组选择排序O(n²)O(1)不稳定简单但效率低快速排序O(nlogn)O(logn)不稳定通用排序大数据量首选归并排序O(nlogn)O(n)稳定外部排序、链表排序堆排序O(nlogn)O(1)不稳定需要快速找最值的场景DFSO(VE)O(V)-路径搜索、连通性判断BFSO(VE)O(V)-最短路无权图、层序遍历KMPO(mn)O(m)-单模式串匹配Trie树O(单词长度)O(字符数×字符集)-前缀匹配、词频统计贪心算法取决于具体实现取决于具体实现-最优子结构 贪心选择性质动态规划取决于状态数×转移代价可滚动数组优化-重叠子问题 最优子结构对比表中特别容易搞混的是DFS和BFS的适用条件。在求无权图最短路径时BFS天然适合因为BFS的层序特性保证了首次到达的点就是最短距离而DFS虽然也能做但往往需要额外记录路径长度并做全局比较效率明显不如BFS。排序算法里归并排序的“稳定性”来自合并过程中左半部分优先的规则快排的不稳定性则来自分区操作中元素的跳变。笔试选择题如果问“哪些排序算法是稳定的”核心记住四个字插、冒、归、基基数排序选择、快排、堆、希尔这四个不稳定的会自动被排除。6. 从笔试真题看教育科技公司的出题偏好与准备方向做到这里我们对猿辅导2023校招算法笔试题的考察逻辑已经有了比较全面的把握。接下来聊聊我从这套题反推出来的出题偏好以及针对性的准备方向。6.1 出题偏好一基础知识扎实冷门技巧很少涉及猿辅导的题目整体不会故意卡人不会出那种“没学过分块这题完全没法做”的情况。相反他们更喜欢把你熟悉的知识点翻出新花样考察你对底层原理的理解程度。比如拓扑排序那道题如果只是背过模板看到题也能做但它没有直接考模板而是加了一个“输出合法序列”的约束这需要你真正理解入度删除的逻辑。这就提醒我们刷题不能只追求数量。我见过不少同学把LeetCode前三百题刷了好几遍但真正笔试时一遇到变体就懵。根本原因在于他们只记住了答案模式而不是背后的思路。建议刷题时每道题做完后主动问自己三个问题为什么这个解法是对的能不能用其他方法做如果改一个条件解法会发生什么变化6.2 出题偏好二注重复杂度的权衡与优化三道编程题的难度梯度很明显第一道是基础操作题第二道是图论经典题第三道是动态规划/贪心优化题。越往后的题越考验对时间复杂度和空间复杂度的把控。这种出题方式和真实业务中的性能要求是呼应的——教育平台每天有大量用户同时在线算法如果不够高效直接影响产品体验。所以复习时不能只停留在“能解出来”的层面还要思考“如何让解法更高效”。比如动态规划的滚动数组优化、贪心问题中堆的引入、图遍历中剪枝的时机这些都是常见的优化手段笔试中能灵活运用上会和竞争对手拉开明显差距。6.3 准备方向形成自己的算法知识体系最后说一说长期准备的方向。我自己的心得是不要把算法岗笔试当成一次性突击任务而是要建立一套完整的算法知识体系然后反复打磨。体系分三个层次。第一层是基础数据结构包括数组、链表、栈、队列、哈希表、树、堆、图等第二层是核心算法思想包括排序与搜索、二分查找、双指针、滑动窗口、递归回溯、贪心、动态规划、分治第三层是专项算法主题包括字符串匹配、图论算法、并查集、线段树、数论基础等。按这个框架对每个大项做专项训练每个主题掌握十几道经典题并总结出解题套路形成条件反射。真正笔试时看到题目就能快速判断它属于哪个知识框架然后从套路库中调出合适的解法。这种“条件反射”不是靠临场发挥而是靠日常大量积累形成的。7. 考后复盘与经验沉淀这些坑希望你不用再踩笔试结束到收到面试通知的几天里我做了一次比较完整的复盘把选择题中不确定的题目和编程题的所有解法都重新捋了一遍。几个比较典型的坑分享出来给大家提个醒。第一个坑是选择题中关于复杂度计算的粗心。题目如果问“堆排序最坏时间复杂度的复杂度是多少”很多同学会对答O(nlogn)但如果问“在千万级数据中找出最大的K个数最优解法的时间复杂度是多少”不少人会写O(nlogn)。实际上最优解是维护一个大小为K的最小堆时间复杂度是O(nlogK)。这种题考察的就是对复杂度在不同约束条件下的理解。第二个坑是编程题中的前置依赖方向。拓扑排序那道题有些同学在做题时想当然认为prerequisites[i] [a, b]表示“a依赖b”但实际上不同题目描述不一样。正确做法是读题时把依赖关系的方向画出来宁可多花几秒钟画个简单示例也不要因为方向搞反导致整个图建反。这种错误一般很难自查出来因为逻辑上代码完全正确测试用例却过不了。第三个坑是贪心算法中“收益最小优先移除”还是“耗时最长优先移除”的选择。我笔试时也纠结过这个细节。这个问题的本质在于目标函数的权重分配。任务分配问题的目标是最大化收益所以移除时自然优先移除收益最小的任务。如果题目变成了“最小化完成时间”那策略就完全不一样了。核心原则是先明确优化目标再设计相应的贪心策略顺序不能乱。第四个坑也是我自己掉进去过的是用Python写算法时忽视了输入输出格式。有些笔试平台要求自己处理多行输入、输出换行等如果格式有偏差即使算法完全正确评测结果也会是“答案错误”。建议平时练习时就在在线评测平台上多提交熟悉平台的输入输出处理方式。最后再补一句备考心态上的经验校招笔试不像高考漏做一道题天也不会塌。遇到不会的题先跳过稳住心态把能拿到的分全部拿到手。算法笔试的容错率其实比想象中高只要基础扎实、节奏稳定正常发挥基本都能过。希望这篇复盘对正在准备猿辅导或其他教育科技公司算法岗笔试的你有点实际帮助。
大厂笔试刚结束那几天牛客网上全是吐槽帖。有人说猿辅导的算法笔试题目看着眼熟真动起手来却卡在边界条件上也有人觉得前面选择题偏基础编程题才是真正拉开差距的地方。我去年秋招投了猿辅导的算法岗正好赶上2023校园招聘笔试批次当时做的是“算法一”这套卷子。整体感受是考察范围不偏门但非常考验基本功扎不扎实尤其是对数据结构底层理解的深度。这篇就来复盘一下我准备这套笔试题的过程和心得围绕高频考点、做题策略、典型题目拆解以及考后反思这几个维度展开。如果你也在准备教育科技类公司的算法岗笔试希望这篇能帮你少走一些弯路。1. 猿辅导算法笔试的考察逻辑不刷偏题怪题专盯基础功底先聊聊这套笔试题给我的整体印象。猿辅导作为在线教育领域的头部公司技术栈和业务场景决定了他们的算法考察有自己的侧重点。教育业务涉及到大量的用户行为分析、题目推荐、课程调度、智能批改等场景所以笔试中出现的算法题往往不是单纯背模板就能过的。从我做过的“算法一”这套卷子来看整体结构大致分两部分第一部分是客观选择题涵盖数据结构、算法复杂度分析、计算机网络基础、操作系统基础知识第二部分是编程题通常两到三道难度从LeetCode中等题到困难题不等。有意思的是猿辅导的笔试很少出那种特别冷门的偏题怪题反倒是在基础算法上挖得很细。比如同一道排序题会追问不同数据规模下最优解法的变化同一个动态规划问题会考察状态转移方程的优化空间。这种出题思路其实和业务强相关——教育场景下的推荐系统、路径规划、资源分配问题说到底考验的就是这些基本功。我当时刷了不少历年校招笔试题发现猿辅导特别爱考这几类字符串相关的经典算法比如KMP、Trie树、字符串匹配变形题贪心策略与动态规划的边界判断尤其是“能不能贪”“怎么DP”这种思维层面的考察二叉树和图的遍历变体往往结合DFS和BFS的剪枝优化排序算法的理解和应用场景选择会问什么时候该用快排什么时候该用堆排这些知识点从名字上看都不陌生但真正的难点在于如何在有限时间内灵活运用。特别是“算法一”这套卷子编程题有一个共同特点数据规模给得比较大用暴力解法不仅会超时还会直接超出内存限制逼着你必须在算法设计上做出正确决策。所以我的第一条建议是准备猿辅导笔试重心放在基础算法的深度理解上不要花大量时间去刷冷门竞赛题。把握好这个方向笔试的复习效率会高很多。2. 从热门算法热搜词看高频考点哪些内容必须滚瓜烂熟翻一下最近算法类的热搜词能明显看出大家关注的重点集中在几个方向KMP算法、粒子群算法、PID算法、各种排序算法、机器学习与深度学习算法等。结合猿辅导笔试的真题特点我梳理了以下必须熟练掌握的知识点每一个都可能成为笔试中的得分点或失分点。2.1 字符串匹配KMP的next数组核心逻辑KMP算法是笔试中的“钉子户”几乎每年都会出现。热搜词里有一条很典型模式串pabacaba求next数组。这类题目考察的不是你能不能背出代码而是对next数组定义和求解逻辑的透彻掌握。先说next数组的定义笔试题里通常会明确next[i]表示模式串前i个子串中最长相等前后缀的长度注意具体定义不同试卷可能略有区别有的从0开始有的从-1开始。以abacaba为例我们需要对每个位置逐个分析位置0字符a前缀子串长度为1最长相等前后缀长度为0next[0]0位置1字符ab前缀a后缀b不相等next[1]0位置2字符aba前缀a后缀a相等最长前后缀长度为1next[2]1位置3字符abac前缀a和c不匹配长度为2时ab和ac不匹配next[3]0位置4字符abaca前缀a和后缀a匹配长度为2时ab和ca不匹配长度为3时aba和aca不匹配next[4]1位置5字符abacab前缀ab和后缀ab匹配长度为2再长就不匹配了next[5]2位置6字符abacaba前缀aba和后缀aba匹配长度为3next[6]3所以这个模式串的next数组是[0, 0, 1, 0, 1, 2, 3]。笔试如果考到这道题核心就是要理解“相等前后缀”这个概念——它决定了匹配失败后模式串可以安全跳过多少位置这是KMP相比暴力匹配效率提升的根本原因。我建议复习时把求next数组的代码自己手写一遍不要只看不写。笔试现场时间紧张如果对边界条件不够熟练很容易在while循环的判断逻辑上出错。2.2 排序算法的复杂度与稳定性笔试选择题的必考内容排序算法几乎占据了选择题的半壁江山。猿辅导的笔试题不会直接让你写快排代码而是会问不同场景下选择哪种排序更合适。从热搜词高频出现的“冒泡排序算法C”“堆排序算法”“快速排序”等来看大家比较关注的是具体实现但笔试真正考的是以下几个维度第一个维度是时间复杂度。冒泡排序、插入排序、选择排序平均都是O(n²)快排平均O(nlogn)但最坏会退化到O(n²)归并排序稳定在O(nlogn)堆排序也是O(nlogn)。第二个维度是空间复杂度。快排有递归栈的开销平均O(logn)最坏O(n)归并排序需要额外O(n)的辅助数组堆排序是原地排序空间复杂度O(1)。第三个维度是稳定性。什么是稳定性简单说就是相等的元素在排序前后相对位置不变。稳定的排序有冒泡、插入、归并不稳定的有选择、快排、堆排序。考试时容易混淆的是堆排序和归并排序。堆排序虽然空间表现好但它的比较和交换是跳跃式的不稳定归并排序借助额外空间换来了稳定性但空间开销大。今年笔试里我印象比较深的一道题是一个几乎有序的数组用什么排序效率最高答案是插入排序。因为插入排序在数组基本有序的情况下每次插入都比较接近最终位置整体时间复杂度接近O(n)。如果不理解这个场景很多同学会条件反射地选快排那就掉坑里了。2.3 动态规划与贪心策略编程题里的“分水岭”猿辅导的编程题基本是两道动态规划加上一道贪心算法的组合拳。难的不是识别出这道题该用DP而是状态定义和状态转移方程的设计。以“最长递增子序列”为例最经典的DP解法是定义dp[i]表示以第i个元素结尾的最长递增子序列长度。状态转移方程是dp[i] max(dp[j] 1)其中j i且nums[j] nums[i]。这个解法的时间复杂度是O(n²)。如果数据范围是10^5级别就必须优化到O(nlogn)——这是笔试中的一个关键分水岭。O(nlogn)的优化思路是维护一个“最小末尾值”数组tailstails[k]表示长度为k1的递增子序列中末尾元素的最小值。遍历每个数用二分查找在tails中找到第一个大于等于当前数的位置然后替换。这样tails的长度就是最长递增子序列的长度。笔试中如果没做过这个优化大概率会超时丢分非常可惜。再说贪心算法。贪心的难点不是实现而是证明“贪心策略是正确”的。笔试里常见的“区间调度问题”需要按结束时间排序每次选择最早结束且与当前区间不重叠的区间。这类题的代码往往不超过二十行但考察的是你对问题本质的理解。复习时一定要多问自己“为什么这个贪心策略是对的”多积累经典题目的证明思路遇到变形题才不会慌。2.4 机器学习与深度学习算法算法岗笔试的“隐藏加分项”现在很多公司算法岗笔试除了传统算法题还会在选择题中穿插ML/DL的基础题。猿辅导2023年这套卷子也不例外。热搜词里“机器学习算法”“深度学习算法”排得很靠前说明这是大家关注的焦点。从笔试角度看选择题中常考的知识点包括逻辑回归和线性回归的区别一个是分类模型一个是回归模型逻辑回归用了sigmoid函数输出概率过拟合的解决方法正则化、Dropout、数据增强、早停法梯度下降的几种变体批量梯度下降、随机梯度下降、小批量梯度下降常见激活函数的优缺点ReLU的死亡神经元问题、sigmoid的梯度消失问题这些内容在准备常规算法题之余必须花时间过一遍。我复习时看的是李航的《统计学习方法》加上吴恩达的课程笔记基本覆盖了大部分考点。不用贪多核心概念理解了、推导会了选择题就不会丢太多分。3. 编程题实战复盘从读题到AC的完整思考链路笔试最怕的不是不会做而是会做但没时间写完或者写完了但细节出错。这里复盘一下我当时做编程题时的完整思路过程重点分享在解题过程中的关键决策点和容易踩的坑。3.1 第一道题字符串压缩变形中等难度题目大致是给定一个字符串将连续重复的字符压缩成“字符出现次数”的形式比如aabcccccaaa压缩后变成a2b1c5a3如果压缩后的字符串长度不小于原字符串则返回原字符串。这题第一眼看起来非常简单很多人的第一反应就是遍历计数。但实际上它考察的核心细节有两个一个是压缩后长度与原字符串长度的比较逻辑另一个是“连续重复”这个条件相同字符不一定连续出现所以不能用一个全局计数器。我的解题思路def compress_string(s: str) - str: n len(s) if n 2: return s compressed [] count 1 for i in range(1, n): if s[i] s[i - 1]: count 1 else: compressed.append(s[i - 1] str(count)) count 1 compressed.append(s[n - 1] str(count)) result .join(compressed) return result if len(result) n else s这道题有个细节值得注意循环结束后最后一组字符需要在循环外手动处理因为循环只在字符发生变化时才输出前一段的统计结果。很多同学在笔试时漏掉最后一行导致最后一个字符的计数丢失白白丢分。另外一个隐藏考点是“压缩后字符串长度不小于原字符串则返回原字符串”这个条件的处理。有的同学会压缩之后再去比较长度这没问题但更高效的做法是在压缩过程中随时判断如果已经不可能短于原字符串了就提前终止。笔试时间紧张时这种微优化虽然不改变复杂度但能节省代码执行时间在测试用例较大时也更有保障。这道题属于“看似简单实则高分”的定位。多数笔试中等题都藏着一个关键思维点快速识别出它就能比其他候选人节省宝贵时间。3.2 第二道题课程表调度图论拓扑排序这道题来自经典OJ题变形给定若干课程的前置依赖关系判断是否可以完成所有课程。可以直接联想到LeetCode 207题“课程表”以及LeetCode 210题“课程表II”。题目描述接近后者除了判断可行性还要输出一种合法的学习顺序。如果输入是一个有向图节点表示课程边表示前置依赖关系那么问题本质上就是图的拓扑排序。拓扑排序的关键是层序删点每次找出所有入度为0的节点加入结果数组然后删除它们指向的边即对应邻接点的入度减1重复这个过程直到没有入度为0的节点。如果最终结果数组的长度不等于课程总数说明图中存在环无法完成全部课程。我当时的核心代码如下from collections import deque def find_order(num_courses: int, prerequisites: List[List[int]]) - List[int]: graph [[] for _ in range(num_courses)] indegree [0] * num_courses for course, pre in prerequisites: graph[pre].append(course) indegree[course] 1 queue deque([i for i in range(num_courses) if indegree[i] 0]) result [] while queue: node queue.popleft() result.append(node) for neighbor in graph[node]: indegree[neighbor] - 1 if indegree[neighbor] 0: queue.append(neighbor) return result if len(result) num_courses else []这道题的坑点主要在图的邻接表方向别搞反了有的题目给的是prerequisites[i] [a, b]表示学a之前必须先学b有的题目给的是a依赖b即b是先修课。读题时必须搞清楚边的方向否则拓扑排序出来的结果是反的甚至完全错误。另一个易错点是入度为0的节点可能不止一个此时可以按任意顺序处理不影响可行性判断但如果题目要求输出“字典序最小的学习顺序”就需要把队列换成优先队列最小堆。猿辅导这道题没有这个要求但我建议准备时顺手把最小堆版本练一下因为很多类似的题目会加这个条件。3.3 第三道题带约束的任务分配动态规划困难难度第三道编程题是整套卷子的压轴题难度明显上升。题目大致是有n个任务每个任务有不同的完成时间和收益每天只能做一个任务每个任务有一个截止日期求最大收益。这道题最直接的想法是按截止日期排序然后逐个考虑任务用动态规划状态表示“处理到某个任务时在某个时间点能获得的最大收益”。状态转移方程是dp[i][j] max(dp[i-1][j], dp[i-1][min(j - time_i, deadline_i - time_i)] profit_i)其中i表示第i个任务j表示当前时间点。但这里有个优化点如果直接用二维DP时间复杂度和空间复杂度都可能是O(n*m)在数据规模较大时很容易超时。优化思路是使用贪心堆的经典解法将所有任务按截止日期排序然后遍历每个任务维护一个当前已选任务的总耗时。如果加入新任务后总耗时超过当前任务的截止日期就把已选任务中收益最小的任务移除用当前任务替代前提是当前任务的收益更大。这个思路的本质是在满足截止日期约束的前提下尽量选择收益更高的任务组合。它用“最小堆”动态维护当前任务集合保证始终是一组可行且收益最大化的解。下面是核心代码import heapq def schedule_jobs(deadlines: List[int], times: List[int], profits: List[int]) - int: jobs sorted(zip(deadlines, times, profits), keylambda x: x[0]) heap [] current_time 0 total_profit 0 for deadline, time, profit in jobs: current_time time heapq.heappush(heap, (profit, time)) total_profit profit if current_time deadline: smallest_profit, smallest_time heapq.heappop(heap) total_profit - smallest_profit current_time - smallest_time return total_profit这里需要理解一个关键点为什么当前时间超出截止日期时移除的是收益最小的任务而不是耗时最长的任务因为我们的目标函数是收益最大化在总耗时不变或减小的情况下移除收益最小的任务对收益的损害最小。即便移除的任务耗时很短如果它收益最低也一样是最优的移除候选。这个“贪心堆”的组合在笔试题中出现频率极高建议重点掌握。很多类似的“安排任务最大收益”问题都可以用这个思路通杀。考试时如果时间充足也可以先用二维DP验证小数据规模下的正确性再改用堆优化处理大数据不过笔试时间有限直接写优化版本更划算。4. 笔试过程中的策略与细节如何稳住节奏多拿分很多同学笔试挂掉不是因为不会做题而是因为节奏乱、细节失误。这类主观因素其实完全可以通过策略调整来规避。这里分几个方面聊聊我的实战经验。4.1 时间分配选择和编程题各占多少时间合适猿辅导算法笔试的总时长一般是一个半小时到两个小时选择题大概有二十道左右编程题两到三道。我的策略是选择题不超过总时长的三分之一。选择题考察的知识点比较杂如果在一道题上卡住超过两分钟果断标记跳过先做后面的题最后如果有剩余时间再回头思考。编程题才是拉开差距的关键。我的建议是先花两三分钟把几道编程题都通读一遍判断题目的难度差异然后从最简单的那道开始动笔。这里有个容易犯的错误一上来就死磕最难的那道题结果最简单的都没时间写。个人的做题顺序原则是先把一道完整AC拿下来保证至少有一道题的分数到手再去做更难的题目。一道题AC的分数价值往往比“每道题都写了一半但全错”的价值高得多。4.2 调试技巧边界条件和数据范围是失分重灾区写代码时所有人都会在题目给出的示例用例上验证一遍但示例通常覆盖不到边界情况。根据我踩坑的经验这几个地方是高频失分点第一个是空输入。字符串为或数组为[]时很多代码会直接崩溃——要么数组越界要么返回错误值。规范的做法是在函数开头就处理空输入返回题目要求的默认值。第二个是单元素输入。比如字符串长度为1时压缩后的结果应该是什么数组只有一个元素时最长递增子序列的长度应该是1。这些看似简单的情况在代码里经常被漏掉分支。第三个是整数溢出。有的题目虽然用int存得下但中间过程比如乘法或者累加可能会溢出。建议在运算时统一用long long或Python的intPython int天然支持大数避免溢出导致的精度错误。第四个是大数据规模的超时。有些同学写的算法逻辑正确但时间复杂度是O(n²)当n跑到10^5时就会超时。笔试环境一般不会给太多运行时间所以提交前一定要估算复杂度如果明显过高就要考虑换更优算法。4.3 代码风格与注释虽然没有加分但能保命很多刚参加笔试的同学会忽略代码风格总觉得“能AC就行”但实际考试中代码风格影响的是你Debug的速度。变量名清晰、逻辑分层明确、关键步骤加注释能帮助你在回看代码时更快定位问题。我自己习惯用比较规范的方式写代码即使笔试时间紧张至少保证核心逻辑的注释写清楚。比如在写状态转移方程前先注释一行说明dp[i][j]的含义在贪心堆的更新步骤前注释说明“移除收益最小的任务以保持截止日期约束”。这样自己回看时能少花大量思考时间写错了也容易发现。5. 常见算法考点的横向对比一张表搞懂选择和填空题为了方便复习我把笔试中最常考的几组容易混淆的算法知识点整理成一张对比表帮助快速记忆和区分。算法时间复杂度平均空间复杂度稳定性典型应用场景冒泡排序O(n²)O(1)稳定数据量小、教学示范插入排序O(n²)O(1)稳定几乎有序的数组选择排序O(n²)O(1)不稳定简单但效率低快速排序O(nlogn)O(logn)不稳定通用排序大数据量首选归并排序O(nlogn)O(n)稳定外部排序、链表排序堆排序O(nlogn)O(1)不稳定需要快速找最值的场景DFSO(VE)O(V)-路径搜索、连通性判断BFSO(VE)O(V)-最短路无权图、层序遍历KMPO(mn)O(m)-单模式串匹配Trie树O(单词长度)O(字符数×字符集)-前缀匹配、词频统计贪心算法取决于具体实现取决于具体实现-最优子结构 贪心选择性质动态规划取决于状态数×转移代价可滚动数组优化-重叠子问题 最优子结构对比表中特别容易搞混的是DFS和BFS的适用条件。在求无权图最短路径时BFS天然适合因为BFS的层序特性保证了首次到达的点就是最短距离而DFS虽然也能做但往往需要额外记录路径长度并做全局比较效率明显不如BFS。排序算法里归并排序的“稳定性”来自合并过程中左半部分优先的规则快排的不稳定性则来自分区操作中元素的跳变。笔试选择题如果问“哪些排序算法是稳定的”核心记住四个字插、冒、归、基基数排序选择、快排、堆、希尔这四个不稳定的会自动被排除。6. 从笔试真题看教育科技公司的出题偏好与准备方向做到这里我们对猿辅导2023校招算法笔试题的考察逻辑已经有了比较全面的把握。接下来聊聊我从这套题反推出来的出题偏好以及针对性的准备方向。6.1 出题偏好一基础知识扎实冷门技巧很少涉及猿辅导的题目整体不会故意卡人不会出那种“没学过分块这题完全没法做”的情况。相反他们更喜欢把你熟悉的知识点翻出新花样考察你对底层原理的理解程度。比如拓扑排序那道题如果只是背过模板看到题也能做但它没有直接考模板而是加了一个“输出合法序列”的约束这需要你真正理解入度删除的逻辑。这就提醒我们刷题不能只追求数量。我见过不少同学把LeetCode前三百题刷了好几遍但真正笔试时一遇到变体就懵。根本原因在于他们只记住了答案模式而不是背后的思路。建议刷题时每道题做完后主动问自己三个问题为什么这个解法是对的能不能用其他方法做如果改一个条件解法会发生什么变化6.2 出题偏好二注重复杂度的权衡与优化三道编程题的难度梯度很明显第一道是基础操作题第二道是图论经典题第三道是动态规划/贪心优化题。越往后的题越考验对时间复杂度和空间复杂度的把控。这种出题方式和真实业务中的性能要求是呼应的——教育平台每天有大量用户同时在线算法如果不够高效直接影响产品体验。所以复习时不能只停留在“能解出来”的层面还要思考“如何让解法更高效”。比如动态规划的滚动数组优化、贪心问题中堆的引入、图遍历中剪枝的时机这些都是常见的优化手段笔试中能灵活运用上会和竞争对手拉开明显差距。6.3 准备方向形成自己的算法知识体系最后说一说长期准备的方向。我自己的心得是不要把算法岗笔试当成一次性突击任务而是要建立一套完整的算法知识体系然后反复打磨。体系分三个层次。第一层是基础数据结构包括数组、链表、栈、队列、哈希表、树、堆、图等第二层是核心算法思想包括排序与搜索、二分查找、双指针、滑动窗口、递归回溯、贪心、动态规划、分治第三层是专项算法主题包括字符串匹配、图论算法、并查集、线段树、数论基础等。按这个框架对每个大项做专项训练每个主题掌握十几道经典题并总结出解题套路形成条件反射。真正笔试时看到题目就能快速判断它属于哪个知识框架然后从套路库中调出合适的解法。这种“条件反射”不是靠临场发挥而是靠日常大量积累形成的。7. 考后复盘与经验沉淀这些坑希望你不用再踩笔试结束到收到面试通知的几天里我做了一次比较完整的复盘把选择题中不确定的题目和编程题的所有解法都重新捋了一遍。几个比较典型的坑分享出来给大家提个醒。第一个坑是选择题中关于复杂度计算的粗心。题目如果问“堆排序最坏时间复杂度的复杂度是多少”很多同学会对答O(nlogn)但如果问“在千万级数据中找出最大的K个数最优解法的时间复杂度是多少”不少人会写O(nlogn)。实际上最优解是维护一个大小为K的最小堆时间复杂度是O(nlogK)。这种题考察的就是对复杂度在不同约束条件下的理解。第二个坑是编程题中的前置依赖方向。拓扑排序那道题有些同学在做题时想当然认为prerequisites[i] [a, b]表示“a依赖b”但实际上不同题目描述不一样。正确做法是读题时把依赖关系的方向画出来宁可多花几秒钟画个简单示例也不要因为方向搞反导致整个图建反。这种错误一般很难自查出来因为逻辑上代码完全正确测试用例却过不了。第三个坑是贪心算法中“收益最小优先移除”还是“耗时最长优先移除”的选择。我笔试时也纠结过这个细节。这个问题的本质在于目标函数的权重分配。任务分配问题的目标是最大化收益所以移除时自然优先移除收益最小的任务。如果题目变成了“最小化完成时间”那策略就完全不一样了。核心原则是先明确优化目标再设计相应的贪心策略顺序不能乱。第四个坑也是我自己掉进去过的是用Python写算法时忽视了输入输出格式。有些笔试平台要求自己处理多行输入、输出换行等如果格式有偏差即使算法完全正确评测结果也会是“答案错误”。建议平时练习时就在在线评测平台上多提交熟悉平台的输入输出处理方式。最后再补一句备考心态上的经验校招笔试不像高考漏做一道题天也不会塌。遇到不会的题先跳过稳住心态把能拿到的分全部拿到手。算法笔试的容错率其实比想象中高只要基础扎实、节奏稳定正常发挥基本都能过。希望这篇复盘对正在准备猿辅导或其他教育科技公司算法岗笔试的你有点实际帮助。
![[光学原理与应用-521]：对光的错误理解与纠偏](http://pic.xiahunao.cn/yaotu/[光学原理与应用-521]：对光的错误理解与纠偏)
