2020年秋招季我投了猿辅导的后端研发岗。笔试通知来得比较突然当天下午还在实验室调模型看到邮件后草草翻了翻题就上了考场。这套笔试二做完之后我印象很深不是因为难而是因为它的出题风格和很多大厂一上来就三道hard压垮你的方式完全不同。它把算法题套在在线教育的业务场景里整体有梯度第一题热身第二题核心第三题稍微烧脑。当时没有写题解的习惯好些细节考完就忘了最近翻做题记录又重新过了一遍把题目还原、解题思路、完整代码和考场上踩过的坑都整理出来了。对准备投在线教育方向、或者想了解2020年校招笔试风格的同学这篇应该能给你一些参考。1. 笔试总体印象三道编程题业务外壳下的经典内核1.1 考试环境与时间安排猿辅导2020校招笔试二是在在线笔试平台上完成的我记得限时90分钟题型以编程题为主。语言可以从C、Java、Python里选这点对平时用Python刷题的人很友好。整套题共三道难度是明显的阶梯状第一道偏基础15分钟左右能拿下第二道是图论里的经典模型需要注意细节第三道压轴需要想到二分答案否则容易卡在O(n^2)的暴力里。笔试开始前有几分钟试机器、调整摄像头的时间建议把这段时间用来确认代码编译环境。这套题没有选择题全部是编程题题目描述里给了样例输入输出但数据范围提示得比较模糊需要自己根据题意估算复杂度。这也算在线笔试的老传统了——范围写得含糊逼着你往更优解想。1.2 出题风格把经典题套上业务壳这是我想重点说的一点。猿辅导的笔试题目不是纯粹的LeetCode硬核题它更喜欢把经典算法放到自己的业务场景里直播课时间段合并、课程依赖关系排课、作业批改分配这些背景一眼就能看出是在线教育公司的日常工作。好处是你不会觉得题目莫名其妙坏处是容易被业务描述带偏忽略底层的经典模型。三道题的核心考点分别是排序贪心、拓扑排序、二分答案。这三个点放在2020年的校招笔试里不算冷门但组合在一起就很有代表性。我把整体印象整理成了一张表题号业务场景核心算法参照模型建议用时第一题直播课时间段合并排序贪心合并区间15分钟第二题课程依赖排课拓扑排序课程表II25分钟第三题助教作业分批二分答案分割数组的最大值35分钟这张表也说明了一个备考思路与其漫无目的地刷题不如按区间处理、拓扑排序、二分答案这类高频考点去专项突破在线教育公司的笔试题基本都能落回这几个经典模型。2. 第一题直播课时间段合并排序后一遍扫描2.1 题面还原题目大概是这样直播平台每天会有很多节课每节课有固定的开始时间和结束时间。如果两节课的时间段有重叠它们就会占用同一批直播资源所以需要把相互重叠的时间段合并成一个连续的大时间段。输入是n个区间输出合并后的区间数量以及这些合并区间里最长的那个持续时长。样例形式我记不太准但核心意思就是给一批[s, e]求合并后的区间数和最大长度。n的规模题目没有明确说但从多种解法推测应该在10^5级别所以O(n^2)是过不了的。这道题对应到LeetCode就是经典的合并区间只不过多问了一个最大长度。2.2 为什么排序后一遍扫描就能解决区间合并问题的直觉是这样的如果区间乱序排列你根本不知道某个区间会和哪些区间重叠。排序之后左端点从小到大问题就变成了当前已经合并到哪、下一个区间进来是接上还是另起一段。具体来说按开始时间升序遍历所有区间维护一个当前合并段的右边界。遇到新区间时如果新区间的开始时间 当前右边界说明两个区间有重叠把它并进来右边界取两者结束时间的较大值如果新区间的开始时间 当前右边界说明当前合并段已经结束记录一下长度然后开一个新的合并段。这里有个细节为什么按左端点排序而不是右端点因为合并的方向是从左往右推每次关心的是下一个区间从哪开始左端点排序能保证你永远不会漏掉某个更早开始的区间。如果按右端点排遍历过程中可能出现过去的区间又接回来的情况逻辑会很别扭。2.3 代码实现def merge_intervals(intervals): if not intervals: return 0, 0 intervals.sort(keylambda x: (x[0], x[1])) count 1 max_len 0 cur_l, cur_r intervals[0] for l, r in intervals[1:]: if l cur_r: cur_r max(cur_r, r) else: count 1 max_len max(max_len, cur_r - cur_l) cur_l, cur_r l, r max_len max(max_len, cur_r - cur_l) return count, max_len排序O(n log n)扫描O(n)整体复杂度O(n log n)空间O(1)。在考场上这个复杂度足够通过。2.4 最容易丢分的细节第一处是区间包含。比如[1, 10]和[2, 3]合并后的右边界应该是10如果写成cur_r r就错了。处理方式很简单合并时右边界一律取max。第二处是端点相接。如果两节课的时间是[1, 3]和[3, 5]这算不算重叠需要根据题目描述判断。有的题说结束时间等于另一节课的开始时间也算冲突那条件就是l cur_r有的题认为不算那就得写成l cur_r。这个细节直接影响答案写代码前一定要先把题目的边界含义确认清楚。第三处是最后一段的收尾。循环结束后最后一个合并段还没被记进答案需要在循环外面再处理一次。很多人在现场会因为忘了这个导致答案差一段。这几处都属于想通了很简单没想通很头疼的点也是区间类题目最容易翻车的地方。3. 第二题课程依赖排课拓扑排序判环3.1 题面还原第二题的背景是课程依赖一共n门课编号0到n-1有m条依赖关系每条输入形如a b表示要学b之前必须先学a。要求判断能否安排一个学习顺序把所有课学完如果可以输出任意一个合法顺序如果不行输出impossible。本质上就是给一个有向图判断是否存在拓扑排序。相当于LeetCode 207课程表的加输出版本。这道题如果没见过拓扑排序可能会想着用DFS去全排列枚举n到10^5级别直接爆炸。所以考点很明确你是否熟悉拓扑排序以及能否在压力下写对邻接表和入度数组。3.2 Kahn算法的核心从入度为0的节点下手拓扑排序有两种常用实现DFS染色法和Kahn算法。我笔试时用的是Kahn因为它的判断环逻辑更直观。Kahn算法的出发点是一张有向无环图里一定存在至少一个入度为0的节点。这个节点没有任何前置依赖可以先学。把它放进结果序列然后删掉它以及它出发的边。删边会让一些后继节点的入度变成0这些节点又变成了可以学的节点。重复这个过程直到把所有节点都处理完。如果最后还有节点没处理说明剩下的节点互为前置依赖也就是存在环排课失败。这里的删边不需要真的从图里删用一个入度数组就能模拟每当一个节点被处理完遍历它的所有后继把后继的入度减1减到0就入队。3.3 代码实现from collections import deque def find_order(n, edges): g [[] for _ in range(n)] indeg [0] * n for a, b in edges: g[a].append(b) indeg[b] 1 q deque(i for i in range(n) if indeg[i] 0) res [] while q: u q.popleft() res.append(u) for v in g[u]: indeg[v] - 1 if indeg[v] 0: q.append(v) if len(res) ! n: return None return res邻接表建图O(nm)拓扑排序每个点和每条边访问一次也是O(nm)空间O(nm)。3.4 这题的坑和进阶问法方向是最容易错的。依赖关系学b之前必须先学a边应该是a到b入度加在b身上。如果把边建反了很多普通样例能过但一到环的场景就会判断错误。我自己当时第一版就把方向写反了靠样例输出不对才发现。另外是输出格式。题目要求输出任意一个合法顺序多个入度为0的节点时队列取出顺序不同会得到不同的答案这些都算对。但如果题目加一个要求字典序最小的顺序就需要把普通队列换成优先队列每次取编号最小的入度为0节点。这个进阶问法在面试里经常出现复杂度会变成O((nm) log n)。还有自环的情况某条依赖是a a那么a永远不可能入队最终结果一定少一个节点返回impossible。这是对的但很多人看到自环会愣一下需要心里有数。判环的逻辑其实是在最后统一判断的如果res的长度不等于n说明有环。这个判断放在while循环结束后做不要在里面提前返回。4. 第三题助教批改连续作业二分答案贪心验证4.1 题面还原第三题是压轴题背景是作业批改n份作业排成一行每份作业需要a[i]分钟的批改时间。现在有k个助教每个助教只能领走一段连续的作业不能跳着领所有助教同时开工。问全部批改完的最短时间是多少。说白了就是把一个数组切成若干连续段段数不超过k有助教可以不领任务希望所有段的和的最大值尽量小求这个最小值。这是分割数组的最大值经典题LeetCode 410、洛谷P1182都是这个模型。如果没接触过二分答案第一反应可能是DPdp[i][j]表示前i份作业分给j个助教的最短时间。但n到10^5级别DP的复杂度O(n^2k)直接超时。所以这道题的关键在于能不能想到二分。4.2 为什么能二分单调性是关键这道题能二分不是因为求最大值就二分而是因为答案具备单调性。设f(mid)表示是否存在一种划分使每段和都不超过mid且段数不超过k。当mid很大时所有作业放一段就行f(mid)为真当mid很小时每段只能装一点点段数会超过kf(mid)为假。随着mid从0增大到所有作业的总时间f(mid)一定是从假变成真中间只有一个拐点。这个拐点就是答案。单调性是二分的前提。想通这一步题目就变成已知单调函数f找真值的最小位置。很多人在考场上卡住是因为一直在想怎么直接算出最优解没有意识到给定一个上限判断可不可行其实更容易。二分答案就是把求最优转化成验证可行的经典手段。4.3 判断函数的贪心写法f(mid)的判断其实是一个贪心模拟从第一份作业开始往段里放只要当前段的总时间不超过mid就继续装一旦装不下就新开一段。这样每一段都尽量装得多段数会是最少的。如果最少的段数都不超过k说明用k个助教完全来得及。这里有个容易想不通的点题目要求段数不超过k那每段尽量装得多得到的段数确实是最少的这点贪心是正确的。可以用反证法理解如果存在一个比我贪心划分段数更少的方案那它在某个位置必然比我更早地截断了一段也就是在某一段里装得更少。但是贪心方案已经尽量装满了比我装得更少意味着它把更多东西留给了后面的段后面的段只会更早触顶不可能总段数更少。所以说贪心得到的段数一定是最少的。4.4 二分边界与复杂度def can_split(a, k, mid): cnt 1 cur 0 for x in a: if cur x mid: cur x else: cnt 1 cur x return cnt k def min_max_sum(a, k): lo max(a) hi sum(a) while lo hi: mid (lo hi) // 2 if can_split(a, k, mid): hi mid else: lo mid 1 return lo左边界为什么是max(a)而不是0因为每一段至少包含一份作业而一份作业的时间是a[i]所以任何一段的和不可能小于最大的a[i]。如果左边界设成0当mid小于某个a[i]时can_split里的curx会让这一段的和超过mid逻辑上已经不满足每段和不超过mid了判断结果虽然也能收敛但会让人心里不踏实。考场上直接把左边界设成max(a)逻辑就严密了。复杂度是O(n log(sum(a)))sum(a)最大到10^9级别log部分也就30次左右完全能过。4.5 如果题目要求输出具体划分有些版本会追加一问除了最短时间还要输出每个助教批改哪一段。做法是先在二分结束后拿到最优答案ans再跑一遍贪心按每段不超过ans的规则从左往右划分。这里需要小心的是切割点的边界每次装不下的位置就是下一段的起点但要注意最后如果段数不够k可以在任意一段的内部再拆开不影响总时间因为拆分只会让每段和变小。这个扩展问法我笔试时没遇到但准备面试的时候值得写一遍很容易在切割点的边界上出错。5. 考后复盘笔试现场最容易翻车的地方5.1 输入输出处理不当白白失分在线笔试最冤的失分不是不会做而是输入输出写错。这套题我记得用的是标准输入输出这意味着多组数据要用while循环读不能只处理一组就退出行尾可能有空格用split()切分时问题不大但用固定长度切片时要注意输出多个数用空格分隔时注意最后一个数后面不要多打一个空格数据量大的时候input()不如sys.stdin.readline()稳定。笔试平台的判题机对格式很严格多一个空行、少一个空格都可能被判wrong answer。我一般会先读完整行再用split切尽量不依赖行内格式。另外如果在本地IDE调试时用了断点或者print提交前一定要把print的调试信息全部注释掉别问我怎么知道的。5.2 边界用例应该在动笔前就想好我后来复盘发现很多问题其实在动笔前用一分钟想想边界就能避免。通用的边界用例包括空输入n0、只有一个元素、k1或者kn、所有a[i]相等、全递增或全递减的区间序列、依赖关系有环、有自环。把这些情况在脑子里过一遍等于提前给自己写了一批测试用例。提交前用这些用例自测能救回不少分。尤其第二题的依赖方向靠的就是试着画一个小环来验证比如有三条依赖0-1、1-2、2-0画完就能确认自己的建图方向是符合学b前先学a的语义的。5.3 时间分配先把能拿的分拿稳90分钟做三道题我的建议是前40分钟把前两道AC掉剩下50分钟给第三道。前两道属于想清楚就能写对的题不值得为了追求完美解法耗太多时间。第三道如果真的没接触过二分答案可以先写一个暴力剪枝或者带备忘的DP拿部分分再慢慢优化。这套题没有像很多笔试那样设置只有全过才算分的AC门槛通常是按测试组给分部分用例过了就有对应分数。所以宁可先交一个能过部分用例的版本也不要死磕最优解导致最后交白卷。实际做题时时间分配本身就是笔试能力的一部分平时刷题最好刻意练习一下限时完成。5.4 给准备校招笔试同学的具体建议考完这套题之后我总结了一个针对在线教育方向笔试的刷题清单区间类合并区间、