1. 笔试整体复盘猿辅导2023校招算法卷到底在考什么又是一年校招季算法岗的笔试永远是绕不开的一道坎。猿辅导2023校园招聘的算法笔试我刷完之后的第一感觉是题目不算偏但非常考察基本功的扎实程度尤其是对时间复杂度的敏感度和边界条件的处理能力。和很多大厂动辄四道压轴难题的套路不同这份试卷更注重“在有限时间内把常规问题写对、写快、写稳”。先说结论这套卷子整体难度中等偏上题型覆盖面比较集中核心考点围绕字符串匹配、排序与查找的变体、贪心策略、动态规划、以及少量数据结构设计题。和热搜词里反复出现的KMP算法、堆排序、贪心算法、快速幂等内容高度吻合说明这些确实是算法岗笔试的高频重灾区。这篇文章我会从试卷结构、考点拆解、典型题目思路、以及我踩过的坑这几个维度做一个完整复盘。准备投猿辅导或者同类在线教育公司算法岗的同学可以拿这篇文章当一份备考地图来用。先说试卷的基本盘。我拿到的这套“算法一”卷整体分为三个部分不定项选择题、算法编程题、以及一道附加的简答题。编程题是绝对的大头占比超过七成。选择题部分考察的是基础理论比如排序算法的稳定性、KMP中next数组的含义、渐进复杂度的计算等看起来不难但如果没有真正理解原理很容易在选项之间犹豫。简答题则更像是在考察工程落地能力比如让你描述一个推荐系统中排序模块的算法选型和理由这种题没有标准答案但非常考验你能不能把算法和业务场景结合起来讲清楚。关于考试环境猿辅导用的是自家的在线笔试平台支持多种编程语言C、Java、Python都可以。我建议在正式笔试前一定去平台熟悉一下代码编辑器的操作尤其是调试输出、切题、查看测试用例这些细节。笔试时间一共120分钟编程题有三道每道题目都有多个测试点部分测试点数据量很小部分测试点数据量很大。这意味着暴力解法几乎拿不到满分必须写出符合题目复杂度要求的正解。接下来我按板块逐层拆解把每个考点的底层逻辑和应对策略都讲透。2. 核心考点深度解析从“背模板”到“理解原理”2.1 KMP算法不只是背一个next数组去年到今年KMP算法的考频肉眼可见地上升。热搜词里“在KMP算法中对于模式串p‘abacaba’其next数组”这个话题热度一直很高说明大量求职者在这里卡壳。KMP算法的核心价值在于解决一个朴素字符串匹配问题——在主串中查找模式串出现的位置朴素做法在最坏情况下的复杂度是O(n*m)而KMP通过预处理next数组把复杂度降到了O(nm)。很多人对KMP的理解停留在“求next数组然后跳转”这个层面但一旦题目稍微变化比如问next数组的优化版本nextval、或者要求用KMP的思想解决循环节问题就很容易翻车。next数组的本质是“当匹配失败时模式串指针应该回退到哪里”它记录的是模式串每个前缀的最长相同前后缀的长度。这个“最长相同前后缀”听起来抽象用生活化类比来说你写了一段代码发现后半段和前半段完全一样你当然不想从头重新写而是跳到能复用半段的位置继续写——next数组就是告诉你“从哪里接着写”的快速索引。具体到“abacaba”这个模式串手算next数组的练习非常值得做一遍。逐个前缀分析前缀“a”没有真前后缀next[1]0前缀“ab”最长相等前后缀长度为0前缀“aba”的最长相等前后缀是“a”长度为1前缀“abac”没有相等的为0前缀“abaca”为1前缀“abacab”为2完整串“abacaba”的最长相等前后缀是“aba”长度为3。整个过程像剥洋葱一样逐层递进练完手算对KMP的理解会深入很多。笔试中涉及KMP的题目通常不会直接让你背next数组而是结合具体场景考察。比如给定一个文本串和一个模式串问从某个位置开始匹配时前几次比较后的跳转过程或者让你计算某个字符串的循环节长度这本质上就是在考察“最长相同前后缀”的应用。我的建议是不要死记代码而是画图模拟几次完整的匹配过程理解每个跳转背后的语义。2.2 排序算法复杂度之外的稳定性与场景适配排序算法是笔试选择题的常客也是编程题里常用的前置工具。很多同学对快排、堆排的时间复杂度背得滚瓜烂熟但一旦问到“归并排序是稳定的吗为什么”“快排的最坏情况什么时候出现”就会卡住。这部分考察的是你对算法本质的理解而不是简单的记忆。快排是实际工程中最常用的排序算法平均时间复杂度O(n log n)但它的最坏情况是O(n^2)。最坏情况出现在每次partition都极度不平衡时比如一个已经有序的数组如果每次选择第一个元素作为pivot就会产生严重的退化。实际笔试中处理大数据量的排序问题时我一般会选择手写快排或者直接使用语言内置的排序函数因为内置排序通常经过了充分优化比如Python的Timsort、C的std::sort它们在真实数据上表现稳定。堆排序在笔试中的出镜率也很高。热搜词“堆排序算法”出现的频率非常高说明这是很多人的薄弱点。堆排序的优势在于O(n log n)的时间复杂度且不需要额外的存储空间但它的实际运行速度通常不如快排因为堆排序的缓存局部性较差。笔试中遇到“从10亿个整数中找出最大的100个数”这类问题用堆是最优解维护一个大小为100的小顶堆遍历数据如果当前元素大于堆顶就替换掉堆顶并调整堆。这个场景就是堆排序知识点的变体考察。归并排序的经典应用是“逆序对数量”问题。归并排序在合并两个有序子数组时可以顺便统计跨越两个区间的逆序对数量这个过程比用树状数组、线段树等数据结构更直观。我在这道题上踩过一次坑因为只统计了左半边的逆序对忘了统计右半边的导致结果翻倍。实际上逆序对要分三步统计——左半边内部、右半边内部、跨越中点的部分缺一不可。还有一个容易被忽略的点排序算法的稳定性。稳定的排序算法如归并排序、插入排序、冒泡排序在元素值相等时保持原有相对顺序这一点在结构体排序、多关键字排序中至关重要。笔试中如果题目要求“成绩相同的按学号升序排列”用Python的sorted加key参数很容易实现但如果你在C中自定义了比较函数就要注意严格弱序strict weak ordering的要求不能写出相互矛盾的比较逻辑否则会导致未定义行为。2.3 贪心算法与动态规划分界线在哪里贪心算法和动态规划是算法岗笔试的绝对主角。热搜词中“贪心算法”和“KL ELBO算法原理详解”同时出现虽然它们分属不同领域但在笔试中贪心和动态规划的区分经常成为选择题的命题点。贪心算法的核心思想是“每一步都做当前看起来最优的选择最终得到全局最优解”。这个策略不是任何时候都成立。贪心能保证最优解的前提是问题具有贪心选择性质和最优子结构性质。最经典的例子是活动选择问题给定若干个活动的开始时间和结束时间选择尽可能多的不冲突活动贪心策略是每次选择结束时间最早的活动。这个策略的直觉是越早结束的活动给后面的活动留下的时间窗口越大。动态规划则是一种“暴力的优化”思路通过把问题分解为重叠的子问题并存储子问题的解来避免重复计算。动态规划适用于有重叠子问题和最优子结构的问题。需要区分的是动态规划不一定是“填表格”那种形式也可能是一维数组、滚动数组、或者状态压缩。笔试中常见的动态规划模型包括背包问题、最长上升子序列、最长公共子序列、编辑距离、区间DP等。我个人的判断经验是如果一个问题能通过“先排序再依次扫描”的方式验证贪心策略的正确性就可以优先考虑贪心如果发现某个步骤的选择会影响后续步骤的可行性而且状态有重叠那基本就是动态规划。面试中我也会问候选人一个经典问题“0-1背包问题为什么不能用贪心”答案是0-1背包中单位价值最高的物品不一定能带来最大总价值因为物品不可分割存在容量上的组合限制。笔试里的编程题往往会把贪心和动态规划混在一起考比如“会议室预订最大值”这类问题表面上像动态规划实际上是一个经典的贪心。切记不要一上来就写状态转移方程先想清楚贪心是否可行这道题会不会有反例。练题时可以专门收集贪心反例比如“找零钱问题中如果硬币面额是1、3、4找6元用贪心会出错411 vs 33”。把这类反例记熟解题时会快很多。3. 编程题实操拆解三道题从读题到AC的全过程3.1 第一道题字符串处理KMP实战我拿到的第一道编程题是一个字符串处理题给定一个文本串T和一个模式串P要求输出P在T中出现的起始位置可能有重叠。这道题本质上就是KMP模板题考察点在于你是否能正确地处理next数组以及是否考虑到了重叠出现的情况。很多同学在“允许重叠”这一点上翻车如果使用朴素匹配一旦在某个位置找到匹配就立刻跳过整个模式串的长度那就会漏掉重叠情况。正确的做法是找到一次匹配后模式串指针j应该回退到next[j]而不是回到0这样下一次匹配才能从可能重叠的位置开始。我刷题时常用的KMP模板Python版长这样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 def kmp_search(t, p): nxt build_next(p) res [] j 0 for i in range(len(t)): while j 0 and t[i] ! p[j]: j nxt[j - 1] if t[i] p[j]: j 1 if j len(p): res.append(i - len(p) 1) j nxt[j - 1] return res这段代码里最关键的是j nxt[j - 1]的处理匹配成功后不能直接重置j而是要复用之前计算好的最长相同前后缀这样重叠匹配才不会漏掉。我在实际笔试中遇到过恰好因为少了这行导致超时的案例——不是时间复杂度超了而是根本就没法通过部分测试点因为漏解了。3.2 第二道题区间问题与贪心策略第二道题是给定若干个区间问最多能选多少个互不重叠的区间经典的区间调度问题。这道题比第一道题更考验解题策略。标准解法是先按照区间的结束时间升序排序然后依次遍历只要当前区间的开始时间不早于上一个被选中区间的结束时间就选择它同时更新结束时间。为什么按照结束时间排序而不是开始时间因为结束时间越早留给后续区间的空间越大。如果用开始时间排序可能会选到一个开始很早但跨度很长的区间导致后续大量区间被挡住。这个选择是贪心算法中最经典的“找出贪心策略后证明它”的考题。我的AC代码思路大致如下def max_non_overlapping(intervals): intervals.sort(keylambda x: x[1]) count 0 last_end float(-inf) for start, end in intervals: if start last_end: count 1 last_end end return count这里有个细节区间的边界条件。题目通常会明确说明“端点是否重合”如果区间是[1, 2]和[2, 3]它们算重叠还是不算不同题目的定义不同必须在读题时确认清楚。如果端点重合算重叠那比较时要用if start last_end如果端点重合不算重叠用if start last_end。只要这一个符号错了就会有一半的测试点通不过。这是我反复强调“读题比刷题更重要”的原因。3.3 第三道题动态规划优化状态压缩第三道题是压轴题考察的是状态压缩动态规划。题目大概是这样的给定一个正整数nn20再给一个n*n的代价矩阵求从起点出发恰好经过所有点一次并回到起点所需的最小总代价。这其实就是经典的TSP旅行商问题的简化版必须用状态压缩DP求解。状态压缩DP的核心思想是用一个整数mask的二进制位表示哪些点已经访问过例如mask的第i位为1表示点i已经访问过。然后定义dp[mask][i]表示“已经访问过的点集合为mask当前停在点i”的最小代价。状态转移时从当前点i尝试走到一个未访问过的点j更新dp[mask | (1 j)][j] min(..., dp[mask][i] cost[i][j])。这个算法的复杂度是O(n^2 * 2^n)对于n20来说大约是4亿次运算在C中用适当优化是可以通过的但在Python里就非常危险了。我当时的处理方式是先看题目给的时限和测试点规模如果n15Python勉强能过如果n20优先用C或者在Python里做剪枝、用数组而不是字典存储dp。这也是笔试技巧的一部分学会根据数据范围估算复杂度选择合适的语言和优化方式。在状态压缩DP中还有一个容易忽略的优化如果n是偶数可以在计算过程中利用对称性减少一半的搜索空间也可以先把所有状态按“二进制中1的个数”分组逐层转移减少无效计算。实战中我习惯先估算一下最坏情况的运算量如果过大就会考虑有没有贪心近似解或者剪枝策略。4. 笔试中的高频掉分点与排查实录4.1 边界条件数组越界是最隐蔽的坑算法题最常见的掉分点绝对不在核心思路而在边界条件。数组越界、空输入、单元素输入、超大数值溢出这四类是笔试中的“隐形杀手”。以KMP为例当模式串为空时应该直接返回空结果或者抛出异常但很多人会直接访问p[0]导致越界。又比如状态压缩DP中当n1时不需要访问任何节点直接返回0但代码里如果没处理这个分支mask为0的状态就会出问题。我的习惯是写完主逻辑后立刻针对几种特殊输入做一次心算测试输入为空或长度为0输入长度为1输入元素完全相同输入元素完全逆序输入已经是目标顺序如果这些边界都能正确输出基本可以提交了。很多在线评测平台对边界条件非常严格一个边界测试点不过就会导致整道题只能拿到部分分数特别可惜。4.2 空间换时间的尺度把控笔试中空间换时间是一种常用手段但也要分场景使用。如果n的范围是10^6级别开一个二维数组做DP内存可能直接超过限制。比如n1000的LCS最长公共子序列问题二维数组1000*1000占用约1MB内存但n10000时就是100MB已经非常危险了。这时就要考虑滚动数组优化把二维DP压缩到一维。另一个常见场景是哈希表的使用。Python的dict在大多数情况下很好用但它的常数因子比较大。如果题目对时间要求很紧比如n10^6量级的遍历查找用list加二分查找可能会比dict更快。我当时做一道需要频繁查询区间和的题目时就因为在Python里用了dict做记忆化结果超时改成前缀和数组之后直接从TLE变成AC。这个经验告诉我先分析数据范围和操作次数再选择数据结构不要无脑上哈希。4.3 递归深度与爆栈问题有些题目用递归写起来很简洁比如树的前序遍历、归并排序的合并过程等但递归在数据量大的时候很容易爆栈。Python默认的递归深度限制是1000层如果树的深度到5000直接Runtime Error。笔试中如果用递归解决深度较大的DFS比如路径搜索、棋盘问题我建议改成显式栈模拟或者使用Python的sys.setrecursionlimit()手动调大递归深度。但要注意调高递归深度不等于完全不会爆栈Python的C栈在极端情况下仍然会崩溃所以显式栈是更稳妥的方案。我在做网格迷宫搜索时用过递归DFS深度一旦超过边界直接栈溢出改成BFS或显式栈之后问题就解决了。对这类搜索类题目BFS通常比DFS更稳因为BFS天然用队列实现不受递归深度限制而且能保证最短路径。4.4 输入输出效率被忽略的隐形杀手笔试平台通常使用标准输入输出。Python的input()在数据量大的时候极慢如果一次要读入10^6行用input()会直接超时。我建议用sys.stdin.buffer.read()一次性读取全部输入再按行分割处理。C的cin在没有关闭同步的情况下也很慢需要加ios::sync_with_stdio(false); cin.tie(0);。输出也是一样能用sys.stdout.write就不用print。这个细节虽然不涉及算法本身但往往决定了你能否在时限内通过大数据测试点。5. 从这套笔试反推岗位要求与备考建议5.1 猿辅导算法岗的核心画像从这套“算法一”笔试题目的构成来看猿辅导对算法岗候选人的要求可以概括为三个词扎实、细致、工程化。所谓扎实是指对经典算法的原理和编码实现必须熟练KMP、堆排序、贪心、状压DP这些内容不是看过就能过的必须能默写成代码还要能应对变体。所谓细致是指边界条件的处理、复杂度的估算、输入输出的优化这些细节决定了一道题能否满分。所谓工程化是指简答题里经常出现“如何设计一个在线判题系统的排行榜使之支持千万级用户”这类问题考察的是从算法到系统设计的迁移能力。在线教育行业的技术栈有一个特点个性化推荐、直播互动、题库判题、课程路线规划都是数据密集型场景。这意味着算法岗不是纯理论研究岗位而是要能够把算法部署到真实业务中处理真实的数据量。猿辅导作为在线教育公司它的算法岗位大概率会涉及教育数据的用户画像、学习路径规划、推荐排序等方向。笔试中出现字符串匹配、区间调度这类题目本质上是在检验你能否把基础算法应用到教育业务中的“资源调度”和“内容匹配”场景。5.2 备考路径从“刷题”到“刷题总结”如果你现在正处在校招准备阶段我给的建议是不要只追求刷题数量而要建立“题目分类集”。比如把KMP、马拉车、后缀数组归到“字符串”类把背包、LIS、区间DP归到“动态规划”类把活动选择、哈夫曼、最小生成树归到“贪心”类。每一类下面整理3-5道经典题作为模板标注出它们的高频变体和易错点。这样在笔试中遇到新题时你能快速定位它属于哪一类然后调用相应的模板思路。另外强烈建议做“限时模拟”。笔试和刷题的最大区别在于时间压力。日常刷题时可以花一小时慢慢思考但笔试里一道题只留给你30-40分钟。我一般会在正式笔试前两周开始做限时训练每套题严格按120分钟计时模拟真实的考试节奏。不要小看这个训练它能帮你训练“先看数据范围再定算法”和“遇到不会的题先跳过”的决策能力。5.3 现场应对策略稳定发挥比超常发挥更重要笔试现场的心态管理也很关键。拿到试卷后我建议先花两分钟浏览全部题目按难度做个排序先做最简单的、得分最稳的题目再做压轴题。如果某道题卡了15分钟还毫无思路果断跳过先把能拿的分数拿到手。很多同学在压轴题上死磕结果前面的基础题没时间写完反而丢了更多分。编程题还有一个小技巧如果题目有部分测试点的数据范围很小比如n10可以写一个暴力解法用小的测试点去验证自己的正解是否输出正确。这种方式在调试时非常有用能让你的信心更稳定。我记得在状态压缩DP那道压轴题里我就是用暴力解法验证了n5的结果确认状态转移方程没有写错然后才提交正解。我个人的体会是这套试卷筛选的并不是“最聪明的人”而是“准备最充分的人”。很多题我都见过原题或者高度相似的题型关键在于能不能在紧张的环境下快速回忆起模板并准确写出没有bug的代码。如果你能把上面这些细节都做到位通过笔试的把握会大很多。6. 最后的实操心得一个小细节让我多拿了分复盘到最后分享一个笔试中的小插曲。当时我做完第二道区间贪心题之后还剩大概二十分钟回过去检查第一道KMP题。我发现自己写的next数组构建方式是用“经典版”也就是next[i]直接表示“前缀P[0:i]的最长相同前后缀长度”但是在匹配的过程中当j回退时我用的是j nxt[j]而不是j nxt[j-1]。这两种写法对应的是不同版本的next定义如果版本混乱程序会出现随机错误或者是死循环。我当时在纸上推演了一遍“abacaba”的完整匹配过程发现这个bug后立刻修正改回了和自己实现匹配逻辑一致的定义。最终这道题拿了满分。这个经历告诉我笔试的代码不一定要最简洁但一定要自洽。你在写代码时脑子里的模型是什么代码就必须严格对应那个模型绝不能混用不同版本的模板。最后一个建议考完笔试后不管感觉如何回来把题目复现一遍。过了就当积累了模板挂了尤其要分析是知识点盲区还是临场失误。我见过太多人刷了一千道题却不过笔试核心问题就是不会总结和反思。校招是一件长期积累的事笔试只是其中一个关卡扎实的算法功底会陪你走完整段职业生涯。 猿辅导2023校招算法笔试复盘：KMP、贪心与动态规划全解析
1. 笔试整体复盘猿辅导2023校招算法卷到底在考什么又是一年校招季算法岗的笔试永远是绕不开的一道坎。猿辅导2023校园招聘的算法笔试我刷完之后的第一感觉是题目不算偏但非常考察基本功的扎实程度尤其是对时间复杂度的敏感度和边界条件的处理能力。和很多大厂动辄四道压轴难题的套路不同这份试卷更注重“在有限时间内把常规问题写对、写快、写稳”。先说结论这套卷子整体难度中等偏上题型覆盖面比较集中核心考点围绕字符串匹配、排序与查找的变体、贪心策略、动态规划、以及少量数据结构设计题。和热搜词里反复出现的KMP算法、堆排序、贪心算法、快速幂等内容高度吻合说明这些确实是算法岗笔试的高频重灾区。这篇文章我会从试卷结构、考点拆解、典型题目思路、以及我踩过的坑这几个维度做一个完整复盘。准备投猿辅导或者同类在线教育公司算法岗的同学可以拿这篇文章当一份备考地图来用。先说试卷的基本盘。我拿到的这套“算法一”卷整体分为三个部分不定项选择题、算法编程题、以及一道附加的简答题。编程题是绝对的大头占比超过七成。选择题部分考察的是基础理论比如排序算法的稳定性、KMP中next数组的含义、渐进复杂度的计算等看起来不难但如果没有真正理解原理很容易在选项之间犹豫。简答题则更像是在考察工程落地能力比如让你描述一个推荐系统中排序模块的算法选型和理由这种题没有标准答案但非常考验你能不能把算法和业务场景结合起来讲清楚。关于考试环境猿辅导用的是自家的在线笔试平台支持多种编程语言C、Java、Python都可以。我建议在正式笔试前一定去平台熟悉一下代码编辑器的操作尤其是调试输出、切题、查看测试用例这些细节。笔试时间一共120分钟编程题有三道每道题目都有多个测试点部分测试点数据量很小部分测试点数据量很大。这意味着暴力解法几乎拿不到满分必须写出符合题目复杂度要求的正解。接下来我按板块逐层拆解把每个考点的底层逻辑和应对策略都讲透。2. 核心考点深度解析从“背模板”到“理解原理”2.1 KMP算法不只是背一个next数组去年到今年KMP算法的考频肉眼可见地上升。热搜词里“在KMP算法中对于模式串p‘abacaba’其next数组”这个话题热度一直很高说明大量求职者在这里卡壳。KMP算法的核心价值在于解决一个朴素字符串匹配问题——在主串中查找模式串出现的位置朴素做法在最坏情况下的复杂度是O(n*m)而KMP通过预处理next数组把复杂度降到了O(nm)。很多人对KMP的理解停留在“求next数组然后跳转”这个层面但一旦题目稍微变化比如问next数组的优化版本nextval、或者要求用KMP的思想解决循环节问题就很容易翻车。next数组的本质是“当匹配失败时模式串指针应该回退到哪里”它记录的是模式串每个前缀的最长相同前后缀的长度。这个“最长相同前后缀”听起来抽象用生活化类比来说你写了一段代码发现后半段和前半段完全一样你当然不想从头重新写而是跳到能复用半段的位置继续写——next数组就是告诉你“从哪里接着写”的快速索引。具体到“abacaba”这个模式串手算next数组的练习非常值得做一遍。逐个前缀分析前缀“a”没有真前后缀next[1]0前缀“ab”最长相等前后缀长度为0前缀“aba”的最长相等前后缀是“a”长度为1前缀“abac”没有相等的为0前缀“abaca”为1前缀“abacab”为2完整串“abacaba”的最长相等前后缀是“aba”长度为3。整个过程像剥洋葱一样逐层递进练完手算对KMP的理解会深入很多。笔试中涉及KMP的题目通常不会直接让你背next数组而是结合具体场景考察。比如给定一个文本串和一个模式串问从某个位置开始匹配时前几次比较后的跳转过程或者让你计算某个字符串的循环节长度这本质上就是在考察“最长相同前后缀”的应用。我的建议是不要死记代码而是画图模拟几次完整的匹配过程理解每个跳转背后的语义。2.2 排序算法复杂度之外的稳定性与场景适配排序算法是笔试选择题的常客也是编程题里常用的前置工具。很多同学对快排、堆排的时间复杂度背得滚瓜烂熟但一旦问到“归并排序是稳定的吗为什么”“快排的最坏情况什么时候出现”就会卡住。这部分考察的是你对算法本质的理解而不是简单的记忆。快排是实际工程中最常用的排序算法平均时间复杂度O(n log n)但它的最坏情况是O(n^2)。最坏情况出现在每次partition都极度不平衡时比如一个已经有序的数组如果每次选择第一个元素作为pivot就会产生严重的退化。实际笔试中处理大数据量的排序问题时我一般会选择手写快排或者直接使用语言内置的排序函数因为内置排序通常经过了充分优化比如Python的Timsort、C的std::sort它们在真实数据上表现稳定。堆排序在笔试中的出镜率也很高。热搜词“堆排序算法”出现的频率非常高说明这是很多人的薄弱点。堆排序的优势在于O(n log n)的时间复杂度且不需要额外的存储空间但它的实际运行速度通常不如快排因为堆排序的缓存局部性较差。笔试中遇到“从10亿个整数中找出最大的100个数”这类问题用堆是最优解维护一个大小为100的小顶堆遍历数据如果当前元素大于堆顶就替换掉堆顶并调整堆。这个场景就是堆排序知识点的变体考察。归并排序的经典应用是“逆序对数量”问题。归并排序在合并两个有序子数组时可以顺便统计跨越两个区间的逆序对数量这个过程比用树状数组、线段树等数据结构更直观。我在这道题上踩过一次坑因为只统计了左半边的逆序对忘了统计右半边的导致结果翻倍。实际上逆序对要分三步统计——左半边内部、右半边内部、跨越中点的部分缺一不可。还有一个容易被忽略的点排序算法的稳定性。稳定的排序算法如归并排序、插入排序、冒泡排序在元素值相等时保持原有相对顺序这一点在结构体排序、多关键字排序中至关重要。笔试中如果题目要求“成绩相同的按学号升序排列”用Python的sorted加key参数很容易实现但如果你在C中自定义了比较函数就要注意严格弱序strict weak ordering的要求不能写出相互矛盾的比较逻辑否则会导致未定义行为。2.3 贪心算法与动态规划分界线在哪里贪心算法和动态规划是算法岗笔试的绝对主角。热搜词中“贪心算法”和“KL ELBO算法原理详解”同时出现虽然它们分属不同领域但在笔试中贪心和动态规划的区分经常成为选择题的命题点。贪心算法的核心思想是“每一步都做当前看起来最优的选择最终得到全局最优解”。这个策略不是任何时候都成立。贪心能保证最优解的前提是问题具有贪心选择性质和最优子结构性质。最经典的例子是活动选择问题给定若干个活动的开始时间和结束时间选择尽可能多的不冲突活动贪心策略是每次选择结束时间最早的活动。这个策略的直觉是越早结束的活动给后面的活动留下的时间窗口越大。动态规划则是一种“暴力的优化”思路通过把问题分解为重叠的子问题并存储子问题的解来避免重复计算。动态规划适用于有重叠子问题和最优子结构的问题。需要区分的是动态规划不一定是“填表格”那种形式也可能是一维数组、滚动数组、或者状态压缩。笔试中常见的动态规划模型包括背包问题、最长上升子序列、最长公共子序列、编辑距离、区间DP等。我个人的判断经验是如果一个问题能通过“先排序再依次扫描”的方式验证贪心策略的正确性就可以优先考虑贪心如果发现某个步骤的选择会影响后续步骤的可行性而且状态有重叠那基本就是动态规划。面试中我也会问候选人一个经典问题“0-1背包问题为什么不能用贪心”答案是0-1背包中单位价值最高的物品不一定能带来最大总价值因为物品不可分割存在容量上的组合限制。笔试里的编程题往往会把贪心和动态规划混在一起考比如“会议室预订最大值”这类问题表面上像动态规划实际上是一个经典的贪心。切记不要一上来就写状态转移方程先想清楚贪心是否可行这道题会不会有反例。练题时可以专门收集贪心反例比如“找零钱问题中如果硬币面额是1、3、4找6元用贪心会出错411 vs 33”。把这类反例记熟解题时会快很多。3. 编程题实操拆解三道题从读题到AC的全过程3.1 第一道题字符串处理KMP实战我拿到的第一道编程题是一个字符串处理题给定一个文本串T和一个模式串P要求输出P在T中出现的起始位置可能有重叠。这道题本质上就是KMP模板题考察点在于你是否能正确地处理next数组以及是否考虑到了重叠出现的情况。很多同学在“允许重叠”这一点上翻车如果使用朴素匹配一旦在某个位置找到匹配就立刻跳过整个模式串的长度那就会漏掉重叠情况。正确的做法是找到一次匹配后模式串指针j应该回退到next[j]而不是回到0这样下一次匹配才能从可能重叠的位置开始。我刷题时常用的KMP模板Python版长这样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 def kmp_search(t, p): nxt build_next(p) res [] j 0 for i in range(len(t)): while j 0 and t[i] ! p[j]: j nxt[j - 1] if t[i] p[j]: j 1 if j len(p): res.append(i - len(p) 1) j nxt[j - 1] return res这段代码里最关键的是j nxt[j - 1]的处理匹配成功后不能直接重置j而是要复用之前计算好的最长相同前后缀这样重叠匹配才不会漏掉。我在实际笔试中遇到过恰好因为少了这行导致超时的案例——不是时间复杂度超了而是根本就没法通过部分测试点因为漏解了。3.2 第二道题区间问题与贪心策略第二道题是给定若干个区间问最多能选多少个互不重叠的区间经典的区间调度问题。这道题比第一道题更考验解题策略。标准解法是先按照区间的结束时间升序排序然后依次遍历只要当前区间的开始时间不早于上一个被选中区间的结束时间就选择它同时更新结束时间。为什么按照结束时间排序而不是开始时间因为结束时间越早留给后续区间的空间越大。如果用开始时间排序可能会选到一个开始很早但跨度很长的区间导致后续大量区间被挡住。这个选择是贪心算法中最经典的“找出贪心策略后证明它”的考题。我的AC代码思路大致如下def max_non_overlapping(intervals): intervals.sort(keylambda x: x[1]) count 0 last_end float(-inf) for start, end in intervals: if start last_end: count 1 last_end end return count这里有个细节区间的边界条件。题目通常会明确说明“端点是否重合”如果区间是[1, 2]和[2, 3]它们算重叠还是不算不同题目的定义不同必须在读题时确认清楚。如果端点重合算重叠那比较时要用if start last_end如果端点重合不算重叠用if start last_end。只要这一个符号错了就会有一半的测试点通不过。这是我反复强调“读题比刷题更重要”的原因。3.3 第三道题动态规划优化状态压缩第三道题是压轴题考察的是状态压缩动态规划。题目大概是这样的给定一个正整数nn20再给一个n*n的代价矩阵求从起点出发恰好经过所有点一次并回到起点所需的最小总代价。这其实就是经典的TSP旅行商问题的简化版必须用状态压缩DP求解。状态压缩DP的核心思想是用一个整数mask的二进制位表示哪些点已经访问过例如mask的第i位为1表示点i已经访问过。然后定义dp[mask][i]表示“已经访问过的点集合为mask当前停在点i”的最小代价。状态转移时从当前点i尝试走到一个未访问过的点j更新dp[mask | (1 j)][j] min(..., dp[mask][i] cost[i][j])。这个算法的复杂度是O(n^2 * 2^n)对于n20来说大约是4亿次运算在C中用适当优化是可以通过的但在Python里就非常危险了。我当时的处理方式是先看题目给的时限和测试点规模如果n15Python勉强能过如果n20优先用C或者在Python里做剪枝、用数组而不是字典存储dp。这也是笔试技巧的一部分学会根据数据范围估算复杂度选择合适的语言和优化方式。在状态压缩DP中还有一个容易忽略的优化如果n是偶数可以在计算过程中利用对称性减少一半的搜索空间也可以先把所有状态按“二进制中1的个数”分组逐层转移减少无效计算。实战中我习惯先估算一下最坏情况的运算量如果过大就会考虑有没有贪心近似解或者剪枝策略。4. 笔试中的高频掉分点与排查实录4.1 边界条件数组越界是最隐蔽的坑算法题最常见的掉分点绝对不在核心思路而在边界条件。数组越界、空输入、单元素输入、超大数值溢出这四类是笔试中的“隐形杀手”。以KMP为例当模式串为空时应该直接返回空结果或者抛出异常但很多人会直接访问p[0]导致越界。又比如状态压缩DP中当n1时不需要访问任何节点直接返回0但代码里如果没处理这个分支mask为0的状态就会出问题。我的习惯是写完主逻辑后立刻针对几种特殊输入做一次心算测试输入为空或长度为0输入长度为1输入元素完全相同输入元素完全逆序输入已经是目标顺序如果这些边界都能正确输出基本可以提交了。很多在线评测平台对边界条件非常严格一个边界测试点不过就会导致整道题只能拿到部分分数特别可惜。4.2 空间换时间的尺度把控笔试中空间换时间是一种常用手段但也要分场景使用。如果n的范围是10^6级别开一个二维数组做DP内存可能直接超过限制。比如n1000的LCS最长公共子序列问题二维数组1000*1000占用约1MB内存但n10000时就是100MB已经非常危险了。这时就要考虑滚动数组优化把二维DP压缩到一维。另一个常见场景是哈希表的使用。Python的dict在大多数情况下很好用但它的常数因子比较大。如果题目对时间要求很紧比如n10^6量级的遍历查找用list加二分查找可能会比dict更快。我当时做一道需要频繁查询区间和的题目时就因为在Python里用了dict做记忆化结果超时改成前缀和数组之后直接从TLE变成AC。这个经验告诉我先分析数据范围和操作次数再选择数据结构不要无脑上哈希。4.3 递归深度与爆栈问题有些题目用递归写起来很简洁比如树的前序遍历、归并排序的合并过程等但递归在数据量大的时候很容易爆栈。Python默认的递归深度限制是1000层如果树的深度到5000直接Runtime Error。笔试中如果用递归解决深度较大的DFS比如路径搜索、棋盘问题我建议改成显式栈模拟或者使用Python的sys.setrecursionlimit()手动调大递归深度。但要注意调高递归深度不等于完全不会爆栈Python的C栈在极端情况下仍然会崩溃所以显式栈是更稳妥的方案。我在做网格迷宫搜索时用过递归DFS深度一旦超过边界直接栈溢出改成BFS或显式栈之后问题就解决了。对这类搜索类题目BFS通常比DFS更稳因为BFS天然用队列实现不受递归深度限制而且能保证最短路径。4.4 输入输出效率被忽略的隐形杀手笔试平台通常使用标准输入输出。Python的input()在数据量大的时候极慢如果一次要读入10^6行用input()会直接超时。我建议用sys.stdin.buffer.read()一次性读取全部输入再按行分割处理。C的cin在没有关闭同步的情况下也很慢需要加ios::sync_with_stdio(false); cin.tie(0);。输出也是一样能用sys.stdout.write就不用print。这个细节虽然不涉及算法本身但往往决定了你能否在时限内通过大数据测试点。5. 从这套笔试反推岗位要求与备考建议5.1 猿辅导算法岗的核心画像从这套“算法一”笔试题目的构成来看猿辅导对算法岗候选人的要求可以概括为三个词扎实、细致、工程化。所谓扎实是指对经典算法的原理和编码实现必须熟练KMP、堆排序、贪心、状压DP这些内容不是看过就能过的必须能默写成代码还要能应对变体。所谓细致是指边界条件的处理、复杂度的估算、输入输出的优化这些细节决定了一道题能否满分。所谓工程化是指简答题里经常出现“如何设计一个在线判题系统的排行榜使之支持千万级用户”这类问题考察的是从算法到系统设计的迁移能力。在线教育行业的技术栈有一个特点个性化推荐、直播互动、题库判题、课程路线规划都是数据密集型场景。这意味着算法岗不是纯理论研究岗位而是要能够把算法部署到真实业务中处理真实的数据量。猿辅导作为在线教育公司它的算法岗位大概率会涉及教育数据的用户画像、学习路径规划、推荐排序等方向。笔试中出现字符串匹配、区间调度这类题目本质上是在检验你能否把基础算法应用到教育业务中的“资源调度”和“内容匹配”场景。5.2 备考路径从“刷题”到“刷题总结”如果你现在正处在校招准备阶段我给的建议是不要只追求刷题数量而要建立“题目分类集”。比如把KMP、马拉车、后缀数组归到“字符串”类把背包、LIS、区间DP归到“动态规划”类把活动选择、哈夫曼、最小生成树归到“贪心”类。每一类下面整理3-5道经典题作为模板标注出它们的高频变体和易错点。这样在笔试中遇到新题时你能快速定位它属于哪一类然后调用相应的模板思路。另外强烈建议做“限时模拟”。笔试和刷题的最大区别在于时间压力。日常刷题时可以花一小时慢慢思考但笔试里一道题只留给你30-40分钟。我一般会在正式笔试前两周开始做限时训练每套题严格按120分钟计时模拟真实的考试节奏。不要小看这个训练它能帮你训练“先看数据范围再定算法”和“遇到不会的题先跳过”的决策能力。5.3 现场应对策略稳定发挥比超常发挥更重要笔试现场的心态管理也很关键。拿到试卷后我建议先花两分钟浏览全部题目按难度做个排序先做最简单的、得分最稳的题目再做压轴题。如果某道题卡了15分钟还毫无思路果断跳过先把能拿的分数拿到手。很多同学在压轴题上死磕结果前面的基础题没时间写完反而丢了更多分。编程题还有一个小技巧如果题目有部分测试点的数据范围很小比如n10可以写一个暴力解法用小的测试点去验证自己的正解是否输出正确。这种方式在调试时非常有用能让你的信心更稳定。我记得在状态压缩DP那道压轴题里我就是用暴力解法验证了n5的结果确认状态转移方程没有写错然后才提交正解。我个人的体会是这套试卷筛选的并不是“最聪明的人”而是“准备最充分的人”。很多题我都见过原题或者高度相似的题型关键在于能不能在紧张的环境下快速回忆起模板并准确写出没有bug的代码。如果你能把上面这些细节都做到位通过笔试的把握会大很多。6. 最后的实操心得一个小细节让我多拿了分复盘到最后分享一个笔试中的小插曲。当时我做完第二道区间贪心题之后还剩大概二十分钟回过去检查第一道KMP题。我发现自己写的next数组构建方式是用“经典版”也就是next[i]直接表示“前缀P[0:i]的最长相同前后缀长度”但是在匹配的过程中当j回退时我用的是j nxt[j]而不是j nxt[j-1]。这两种写法对应的是不同版本的next定义如果版本混乱程序会出现随机错误或者是死循环。我当时在纸上推演了一遍“abacaba”的完整匹配过程发现这个bug后立刻修正改回了和自己实现匹配逻辑一致的定义。最终这道题拿了满分。这个经历告诉我笔试的代码不一定要最简洁但一定要自洽。你在写代码时脑子里的模型是什么代码就必须严格对应那个模型绝不能混用不同版本的模板。最后一个建议考完笔试后不管感觉如何回来把题目复现一遍。过了就当积累了模板挂了尤其要分析是知识点盲区还是临场失误。我见过太多人刷了一千道题却不过笔试核心问题就是不会总结和反思。校招是一件长期积累的事笔试只是其中一个关卡扎实的算法功底会陪你走完整段职业生涯。