猿辅导2020校招笔试编程题全解析：字符串压缩、任务调度与二叉树路径

每年这个时间点都会有一批准备校招的同学被“猿辅导2020校招笔试一”这套题虐得死去活来。我当年也是其中之一笔试时候被最后一道二叉树题卡了半小时出考场后复盘了整整两天。今天把这场比赛的核心考点、三套编程题的完整思路与代码、以及我当时踩过的坑一次性整理出来给准备投教育科技公司算法岗/后端岗的同学做个参考。这套笔试整体分客观题和编程题两部分编程题是重头戏三道题分别考察字符串处理、贪心优先队列、二叉树递归。单看难度不算离谱但真正做起来很考验基本功尤其是边界条件的处理。无论你是第一次参加校招笔试还是已经刷了一两百道LeetCode这篇复盘应该都能帮你少走弯路。1. 猿辅导2020校招笔试一到底考了什么1.1 笔试整体安排与题型分布猿辅导的校招笔试通常通过牛客网在线完成总时长约120分钟。拿2020校招笔试一来说卷面结构是两个部分前面的客观题和后面的编程题。客观题覆盖计算机基础四件套——数据结构、操作系统、计算机网络、数据库偶尔还会穿插一两道C/Java语言特性题。客观题部分大概有15-20道左右单题分值不高但胜在覆盖面广。我当时印象比较深的是有几道题考了操作系统的进程调度算法、TCP三次握手过程中的状态变化、数据库索引失效的场景这些都是教科书里反复出现的内容平时背过就能答上来没背就只能靠直觉蒙。还有一道C的虚函数表选择题让我这种Java选手当场沉默。编程题是三道一般从简到难排列总分值能占到整张试卷的60%以上。前两道题大概率能在30分钟内搞定第三道决定你能不能进入下一轮。考试平台用的是牛客的在线OJ支持Java、C、Python等主流语言本地能跑通的代码一般直接能提交但有几个平台细节需要注意后面会专门讲。1.2 考点风格与备考判断从真题风格来看猿辅导的笔试和字节、腾讯这种大厂相比不算特别偏门但有两个很明显的倾向。第一非常看重基础数据结构的熟练度。哈希表、栈、队列、二叉树这些内容反复出现而且往往不是单独考察而是把多个结构组合在一起。比如任务调度那道题表面是数组排序实际要用到优先队列字符串题表面是模拟实际考察对下标边界的敏感程度。第二边界条件和异常输入的处理占很大比重。平时刷LeetCode习惯了一路“标准输入标准输出”但笔试题目会故意设置空字符串、单个字符、数据量很大的边缘场景。我第一次做字符串压缩题时只写了正常情况的逻辑结果空字符串输入直接返回了错误结果。这种失分是最亏的因为思路完全正确就是少判断了一行。我给的备考建议是不要盲目追求难题偏题把剑指Offer和LeetCode Hot 100刷扎实胜过于刷三百道乱题。尤其是递归、双指针、滑动窗口、贪心这几个高频模型必须做到不看题解能默写出来的程度。2. 编程题实战拆解三题思路到代码全还原2.1 真题一字符串连续字符压缩题目描述回忆版给定一个只包含小写字母的字符串将连续出现的相同字符压缩成“字符出现次数”的形式。例如输入aaabbc输出a3b2c。如果压缩后的字符串长度不小于原字符串长度则返回原字符串。这道题在LeetCode上有类似原型字符串压缩面试题 01.06属于“一看就会、一写就错”的类型。核心思路很简单一趟遍历用计数器统计当前字符连续出现的次数遇到不同字符时结算一次。但有几个关键点必须注意单个字符不需要拼接数字比如c保持c而不是c1。遍历结束后最后一组字符需要额外结算一次。题目要求“压缩后长度不小于原长度则返回原串”这个判断要在所有循环结束后做。def compress_string(s: str) - str: if not s: return res [] cnt 1 for i in range(1, len(s) 1): if i len(s) and s[i] s[i - 1]: cnt 1 else: res.append(s[i - 1]) if cnt 1: res.append(str(cnt)) cnt 1 compressed .join(res) return compressed if len(compressed) len(s) else s时间复杂度O(n)空间复杂度O(n)。这里用列表而不是字符串直接拼接是为了避免频繁创建新字符串对象。笔试时如果对Python字符串拼接的底层机制不熟悉直接用res s[i-1]也能过但数据量一大性能差距就出来了。我当初在循环里写的是for i in range(1, len(s))最后忘了补最后一组的结算导致aaabbb输出成了a3b。这种错误在笔试环境下很常见因为样例通常不会覆盖到“字符串以连续相同字符结尾”的情况自己一定要主动构造用例来验证。2.2 真题二任务调度器题目描述回忆版给定一个用字符数组表示的任务列表每个任务需要1个单位时间执行相同任务之间必须有n个冷却单位时间。求完成所有任务所需的最短时间。例如tasks [A,A,A,B,B,B]n 2最短时间是8。这题是LeetCode 621的原题变体也是笔试中区分度比较高的一道题。核心思路有两种一种是用优先队列模拟执行过程另一种是直接用公式计算。我先说公式法因为它更快也更不容易写错。统计每个任务的出现频率freq设maxFreq是最大频率maxCount是达到最大频率的任务个数。最终时间 max((maxFreq - 1) * (n 1) maxCount, len(tasks))。这个公式的含义是把频率最高的任务作为“骨架”每个任务之间插入n个冷却单位时间最后挂上同样达到最高频率的任务。如果加入其他任务后总长度超过了这个骨架长度说明冷却时间被填满甚至不够用那么答案就是原任务总数。from collections import Counter def least_interval(tasks, n: int) - int: freq Counter(tasks) max_freq max(freq.values()) max_count sum(1 for v in freq.values() if v max_freq) return max((max_freq - 1) * (n 1) max_count, len(tasks))很多同学疑惑为什么len(tasks)也可能是答案。举个例子如果任务类型很多n 0那么不断执行不同任务就能把冷却时间填满总时间就是任务总数。这时候公式算出来的骨架反而更小取最大值就可以了。模拟法也能做而且更好理解。用一个大根堆保存剩余任务数量每一轮从堆里取n1个任务执行执行完剩余次数大于0的放回去如果堆提前空了说明这一轮没填满需要补上冷却时间。这个解法的代码量稍大但容错率高尤其适合那种“公式背不住”的同学。笔试时我用的是模拟法大概十五分钟写完重点是把“空转时间”也算进答案里。2.3 真题三二叉树最大路径和题目描述回忆版给定一棵二叉树每个节点有一个整数值求从任意节点出发到任意节点结束的路径使得路径上节点的值之和最大。路径不要求经过根节点也不要求一定走叶子节点但路径中每个节点只能出现一次。这题是LeetCode 124的原题也是整张卷子难度最高的一题。核心用后序遍历对于每个节点分别计算左子树和右子树能给当前节点带来多少“增益”如果增益为负数就舍弃取0。class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right class Solution: def maxPathSum(self, root: TreeNode) - int: self.ans float(-inf) def dfs(node): if not node: return 0 left max(dfs(node.left), 0) right max(dfs(node.right), 0) self.ans max(self.ans, node.val left right) return node.val max(left, right) dfs(root) return self.ans关键点在于理解return node.val max(left, right)和更新self.ans的node.val left right的区别。前者是“穿过当前节点的路径只能继续向父节点延伸因此只能选择左右子树中较大的一支”后者是“以当前节点为拐点的完整路径左右两边的增益都能算进来用来更新全局最大值”。如果画一棵简单的树比如根节点是-10左右子节点分别是9和20右子节点再挂15和7手推一遍就能发现最大路径是15 - 20 - 7 42而不是经过根节点的路径。这个例子我每次讲都会让读者手推一遍推完就理解了为什么负数增益要砍掉。这题我笔试时写了个前序遍历版本直接算出了错误答案。后来复盘才明白二叉树路径问题绝大多数都需要后序遍历因为父节点的路径依赖子节点的计算结果只有后序能让子节点先返回信息给父节点。3. 笔试答题策略时间分配与边界处理3.1 客观题与编程题的时间分配120分钟看似充裕实际上很多人会在客观题上抠太久导致后面编程题写不完。我建议把时间切成三段客观题最多45分钟编程题每题分配20-25分钟留出10分钟检查输入输出格式和边界样例。客观题遇到不会的先标记出来不要恋战。我当时在两道网络题上各耗了五分钟结果编程题的前两题写得就很赶。后来学聪明了客观题控制在“会做的全做对不会的快速猜”的节奏把时间留给分值更大的编程题。一个更细的时间策略是把所有题目先通读一遍。编程题的第三题如果读完1分钟还没有任何思路先跳过去做第二题的代码调优最后再回头啃第三题。不要因为一道题卡住就心态崩掉笔试拼的是总分不是单题满分。3.2 边界条件和隐藏陷阱怎么躲边界条件是笔试最常见的失分点。我把编程题常见的边界场景总结成一份自查清单空输入字符串为空、链表为空、根节点为None代码第一行就要处理。单元素输入比如字符串只有一个字符、数组只有一个数。数值边界整数溢出Java选手尤其注意、Python的负数除法行为。全相同元素比如压缩字符串输入全是aaaaa任务调度全是同一个任务。结果等于输入原始值比如字符串压缩后长度不变或变长的场景。树退化二叉树退化成链表递归深度可能栈溢出要评估是否改成迭代。每写完一道题照着这份清单逐个构造测试用例能减少80%的冤枉分。我见过的同学里有人思路完全正确但对“单个字符的字符串”没有单独处理直接丢了一半测试用例的分。另外注意题目里给的“如果压缩后的字符串长度不小于原字符串长度则返回原字符串”这类条件它不是在跟你商量而是硬性输出规则。很多人看到这种句子就划过去了结果输出的压缩串明明比原串长还在纠结为什么样例过不了。3.3 编码细节与调试习惯在线笔试的编码体验通常不如本地IDE说几个细节读输入时用sys.stdin.readline()而不是input()多组大数据输入时性能差距明显。Python把递归深度限制从默认1000调大sys.setrecursionlimit(10000)防止二叉树题爆栈。提交前把代码里的调试输出全部删掉print语句会影响判题结果。如果题目要求类名是Solution就老老实实用这个类名定义方法签名也要完全一致牛客和LeetCode的题格式可能不同审题要仔细。还有一个小技巧在本地写完代码后手动跑一遍题目给的样例再跑一遍自己构造的边界样例如果都能过再提交。宁愿多花两分钟验证也不要赌一次提交就能AC。4. 常见问题与实战避坑记录4.1 机考平台和本地环境的差异很多人在笔试时遇到的最诡异问题不是题目不会做而是“本地能跑提交零分”。我整理了几个常见的平台差异牛客的Python环境版本可能和本地不同比如不支持某些高版本语法写完代码先确认平台支持的语言版本。Java的类名和主方法签名在牛客和LeetCode上不同牛客要求public class Main类里要有main方法LeetCode则是提交Solution类。输出结果不要带多余的空格和换行尤其注意最后一个字符后面不要多输出一个空格。在线平台一般不支持相对路径读文件所有数据都从标准输入读。如果代码用了math、collections等第三方标准库必须显式import别依赖本地环境自动加载。我刚参加笔试时有一次Java题把类名写成了Main2平台直接编译报错白白丢了一道题的分。经验是拿到题先看顶部给好的框架代码填进去就好千万别自己重新起炉灶。4.2 笔试中踩过的典型坑复盘2020校招笔试一我发现自己栽了两个大坑写出来给大家引以为戒。第一个坑是没有通读全部题目就开写。我拿到题第一反应是马上做第一题结果第三题其实可以复用第一题的某些数据结构设计但等做到第三题时已经没时间回去重构了。正确的做法是先花3分钟把所有题目浏览一遍心里有个优先级。第二个坑是误判第三题的难度。我一开始以为二叉树最大路径和要用复杂的状态DP还想了半天怎么设计状态转移结果实际只需要后序遍历加一个全局变量。这提醒我一件事笔试中的难题往往只是“看起来难”真正解题用的还是基础算法不要自己吓自己。还有一个小坑是关于max函数的使用。我在任务调度公式里把max((maxFreq - 1) * (n 1) maxCount, len(tasks))写成了min样例和自作聪明构造的用例都过了但是提交后发现大量测试用例失败。因为当冷却时间很小时公式结果会比任务总数小而实际执行时间不可能少于任务总数。这个教训是不能只看自己构造的用例要反过来问问“答案不可能小于什么”。4.3 复盘与后续准备建议笔试结束后我建议当天就复盘趁记忆还热乎。把每道题的思路写成题解标注错误原因比过几天再做一遍有效得多。我每次笔试后都会把“失误类型”分类统计比如少考虑空输入、数组越界、long溢出、题看错下次笔试前先看一遍这个清单基本能避开70%以上的坑。复盘时还要注意不要只盯着自己没做出来的题。就算AC了的题也要看看官方题解尤其是同一题的最优解。比如任务调度那道题我用的模拟法能通过但官方公式法的时间复杂度是O(n)空间复杂度O(1)在大数据量下明显更优。笔试虽然不要求极致性能但面试官问起“有没有更优解法”时能答出两种方案是完全不同的印象。针对教育科技公司的后续准备建议再刷一下“字符串编辑距离”“反转链表变体”“接雨水”这几个高频题以及稍微看下海量数据处理相关的场景题毕竟线上教育产品会有大量并发和数据处理场景面试阶段很容易追问。最后分享一个我个人的体会校招笔试考的不只是刷题量更是在有限时间内稳定输出正确代码的能力。练题的时候给自己定闹钟模拟考试节奏比漫无目的地一天刷十道题更有效。这套“猿辅导2020校招笔试一”是个很好的练手素材建议你按两个小时完整做一遍做完再看这篇文章的代码和思路找找自己会卡在哪个环节。多复盘几套笔试的感觉就上来了。