猿辅导2020校招后端笔试解析：合并区间、拓扑排序与二分答案实战

2020年秋招季，我投了猿辅导的后端研发岗。笔试通知来得比较突然，当天下午还在实验室调模型，看到邮件后草草翻了翻题就上了考场。这套笔试（二）做完之后我印象很深，不是因为难，而是因为它的出题风格和很多大厂一上来就三道hard压垮你的方式完全不同。它把算法题套在在线教育的业务场景里，整体有梯度，第一题热身，第二题核心，第三题稍微烧脑。当时没有写题解的习惯，好些细节考完就忘了，最近翻做题记录又重新过了一遍，把题目还原、解题思路、完整代码和考场上踩过的坑都整理出来了。对准备投在线教育方向、或者想了解2020年校招笔试风格的同学，这篇应该能给你一些参考。

1. 笔试总体印象：三道编程题，业务外壳下的经典内核

1.1 考试环境与时间安排

猿辅导2020校招笔试（二）是在在线笔试平台上完成的，我记得限时90分钟，题型以编程题为主。语言可以从C++、Java、Python里选，这点对平时用Python刷题的人很友好。整套题共三道，难度是明显的阶梯状：第一道偏基础，15分钟左右能拿下；第二道是图论里的经典模型，需要注意细节；第三道压轴，需要想到二分答案，否则容易卡在O(n^2)的暴力里。

笔试开始前有几分钟试机器、调整摄像头的时间，建议把这段时间用来确认代码编译环境。这套题没有选择题，全部是编程题，题目描述里给了样例输入输出，但数据范围提示得比较模糊，需要自己根据题意估算复杂度。这也算在线笔试的老传统了——范围写得含糊，逼着你往更优解想。

1.2 出题风格：把经典题套上业务壳

这是我想重点说的一点。猿辅导的笔试题目不是纯粹的LeetCode硬核题，它更喜欢把经典算法放到自己的业务场景里：直播课时间段合并、课程依赖关系排课、作业批改分配，这些背景一眼就能看出是在线教育公司的日常工作。好处是你不会觉得题目莫名其妙，坏处是容易被业务描述带偏，忽略底层的经典模型。

三道题的核心考点分别是排序贪心、拓扑排序、二分答案。这三个点放在2020年的校招笔试里不算冷门，但组合在一起就很有代表性。我把整体印象整理成了一张表：

这张表也说明了一个备考思路：与其漫无目的地刷题，不如按"区间处理、拓扑排序、二分答案"这类高频考点去专项突破，在线教育公司的笔试题基本都能落回这几个经典模型。

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(key=lambda 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(n+m)，拓扑排序每个点和每条边访问一次，也是O(n+m)，空间O(n+m)。

3.4 这题的坑和进阶问法

方向是最容易错的。依赖关系"学b之前必须先学a"，边应该是a到b，入度加在b身上。如果把边建反了，很多普通样例能过，但一到环的场景就会判断错误。我自己当时第一版就把方向写反了，靠样例输出不对才发现。

另外是输出格式。题目要求输出"任意一个合法顺序"，多个入度为0的节点时，队列取出顺序不同会得到不同的答案，这些都算对。但如果题目加一个"要求字典序最小的顺序"，就需要把普通队列换成优先队列，每次取编号最小的入度为0节点。这个进阶问法在面试里经常出现，复杂度会变成O((n+m) log n)。

还有自环的情况：某条依赖是a a，那么a永远不可能入队，最终结果一定少一个节点，返回impossible。这是对的，但很多人看到"自环"会愣一下，需要心里有数。判环的逻辑其实是在最后统一判断的：如果res的长度不等于n，说明有环。这个判断放在while循环结束后做，不要在里面提前返回。

4. 第三题：助教批改连续作业，二分答案+贪心验证

4.1 题面还原

第三题是压轴题，背景是作业批改：n份作业排成一行，每份作业需要a[i]分钟的批改时间。现在有k个助教，每个助教只能领走一段连续的作业，不能跳着领，所有助教同时开工。问全部批改完的最短时间是多少。

说白了就是：把一个数组切成若干连续段，段数不超过k，有助教可以不领任务，希望所有段的和的最大值尽量小，求这个最小值。这是"分割数组的最大值"经典题，LeetCode 410、洛谷P1182都是这个模型。

如果没接触过二分答案，第一反应可能是DP：dp[i][j]表示前i份作业分给j个助教的最短时间。但n到10^5级别，DP的复杂度O(n^2k)直接超时。所以这道题的关键在于能不能想到二分。

4.2 为什么能二分：单调性是关键

这道题能二分不是因为"求最大值"就二分，而是因为答案具备单调性。

设f(mid)表示"是否存在一种划分，使每段和都不超过mid且段数不超过k"。当mid很大时，所有作业放一段就行，f(mid)为真；当mid很小时，每段只能装一点点，段数会超过k，f(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里的cur=x会让这一段的和超过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 边界用例应该在动笔前就想好

我后来复盘发现，很多问题其实在动笔前用一分钟想想边界就能避免。通用的边界用例包括：空输入n=0、只有一个元素、k=1或者k=n、所有a[i]相等、全递增或全递减的区间序列、依赖关系有环、有自环。

把这些情况在脑子里过一遍，等于提前给自己写了一批测试用例。提交前用这些用例自测，能救回不少分。尤其第二题的依赖方向，靠的就是"试着画一个小环"来验证：比如有三条依赖0->1、1->2、2->0，画完就能确认自己的建图方向是符合"学b前先学a"的语义的。

5.3 时间分配：先把能拿的分拿稳

90分钟做三道题，我的建议是前40分钟把前两道AC掉，剩下50分钟给第三道。前两道属于"想清楚就能写对"的题，不值得为了追求完美解法耗太多时间。第三道如果真的没接触过二分答案，可以先写一个暴力剪枝或者带备忘的DP拿部分分，再慢慢优化。

这套题没有像很多笔试那样设置"只有全过才算分"的AC门槛，通常是按测试组给分，部分用例过了就有对应分数。所以宁可先交一个能过部分用例的版本，也不要死磕最优解导致最后交白卷。实际做题时，时间分配本身就是笔试能力的一部分，平时刷题最好刻意练习一下限时完成。

5.4 给准备校招笔试同学的具体建议

考完这套题之后，我总结了一个针对在线教育方向笔试的刷题清单：

• 区间类：合并区间、