去年秋招那会儿我帮实验室好几个师弟改简历、模拟面试发现一个特别普遍的现象很多人刷题刷了几百道LeetCode周赛也能稳住三道题但一到“猿辅导2023校园招聘技术类笔试一”这种带公司特色的综合笔试就直接懵圈。倒不是题目难到天上去而是这套笔试卷子的风格跟纯刷题平台完全不一样——它考的是你在有限时间内能不能把数据结构、算法、系统设计、甚至业务场景串起来思考。这篇文章我就拿这套笔试的典型题目做个深度拆解不讲虚的直接上硬货每道题怎么审、怎么破、代码怎么写、有哪些坑是笔试时最容易踩的。不管你是正在准备秋招的应届生还是想跳槽的社招选手只要目标是国内一二线互联网公司的技术岗这套题背后的出题逻辑都值得你花半小时认真过一遍。1. 为什么猿辅导的笔试跟LeetCode风格差异这么大先聊点题外话。很多人拿到猿辅导的笔试卷子第一反应是“怎么还有这种题”这恰恰说明你还没摸透这家公司的出题套路。跟纯互联网大厂的海量题库不同猿辅导作为教育科技公司它的技术笔试有一个很明显的倾向既考基本功也考业务理解。我翻了近三年的真题总结下来有三个核心特点。第一题目量不大但单题分值高。一套卷子通常四到六道大题每道题都可能是一个完整的场景描述而不是孤立的算法题。这意味着你如果某道题卡住了整块分值直接丢掉容错率很低。第二算法题偏爱“变形题”。比如你刷过“最长递增子序列”它可能会给你一个“按学科成绩排名”的场景你刷过“二叉树层序遍历”它可能会结合“课程表依赖关系”来考。知识点还是那个知识点但包装换了很多人就认不出来了。第三会有一道“压轴题”专门考工程思维。这道题不一定多难但一定涉及多线程、内存管理、分布式、或者大数据量处理目的是筛掉那些只会背题、不会解决实际问题的人。我印象最深的是去年一道压轴题题目是“设计一个支持百万并发排课的调度系统”要求写出核心数据结构并说明线程安全策略。这题放在LeetCode上根本不算算法题但在笔试里它就是用来区分“刷题机器”和“真正理解工程”的。所以准备这套笔试的思路必须调整刷题是基础但不是全部。你需要把每个知识点都往“如果做成一个真实功能会怎样”的方向想一遍。2. 字符串与哈希的经典组合拳第一道送分题的多种解法笔试第一题通常不会太难目的是让你热身但越是这样越容易翻车。猿辅导2023这套卷子的第一题大致是这样的题目给定一个字符串s和一个整数k请找出字符串中恰好出现k次的最长子串的长度。如果不存在则返回-1。很多人的第一反应是“滑动窗口”这确实是常见解法但这里有个坑题目要求“恰好出现k次”它没有说明子串是否必须连续。我当年帮一个学弟复盘时发现他直接用滑动窗口做了结果只过了30%的测试用例就是因为没审清楚“子串”在题目里的定义。2.1 审题比写代码更重要我通常拿到这种题先做三件事确认子串是否连续——这在中文语境里经常有歧义确认“恰好k次”是指在整个原字符串中出现的次数还是字面意义上的字符频率确认字符串长度范围这决定了能不能用O(n^2)暴力假设题目中的子串是“连续子串”并且“恰好出现k次”是指这个子串作为整体在原串中出现的次数那解法就清晰了。核心思路是这样的如果一个子串出现了恰好k次那它的长度一定不会超过某个阈值。更关键的是我们可以枚举所有可能的子串起点用哈希表记录每个子串出现的次数。但直接枚举所有子串是O(n^2)的如果字符串长度到10^5就会超时。这里有一个优化技巧用“后缀数组高度数组”或者“后缀自动机”来解决但笔试现场写后缀自动机不太现实。更实用的做法是二分答案。二分答案的check函数怎么写对于长度为len的所有子串用滚动哈希也叫Rabin-Karp哈希计算每个子串的哈希值存到哈希表里统计每个哈希值出现的次数。如果某个哈希值出现的次数等于k就说明存在长度为len的子串恰好出现k次。这里要注意哈希碰撞的问题笔试中一般用双哈希或者直接用一个128位的pair来降低碰撞概率。2.2 代码实现与边界条件我给出一个比较稳的Python实现这个风格在笔试里既好写又好调试def solve(s: str, k: int) - int: n len(s) if k 0 or k n: return -1 base 131 mod 10**9 7 # 预处理前缀哈希和幂 prefix [0] * (n 1) power [1] * (n 1) for i in range(n): prefix[i1] (prefix[i] * base ord(s[i])) % mod power[i1] power[i] * base % mod def get_hash(l, r): # 左闭右开区间 [l, r) return (prefix[r] - prefix[l] * power[r-l]) % mod # 二分答案 left, right 1, n ans -1 while left right: mid (left right) // 2 freq {} found False for i in range(n - mid 1): h get_hash(i, i mid) freq[h] freq.get(h, 0) 1 if freq[h] k: found True break if found: ans mid left mid 1 else: right mid - 1 return ans这段代码有几个细节值得注意power数组预处理了base的幂这样get_hash就是O(1)操作二分答案从1到n每次check是O(n)整体O(n log n)一旦发现某个哈希值出现次数达到k就提前返回这是个小优化边界条件kn直接返回-1因为任何子串不可能出现超过n次笔试中容易踩的坑还有子串长度mid不能为0如果k0按题意应该返回-1还是0这个必须看题目说明。我一般会写一个注释说明按题意处理。2.3 为什么不用Python自带的字符串切片这个问题我在模拟面试时被问过很多次。用s[i:ilen]做切片然后放入字典代码确实更短但笔试环境里字符串切片是O(len)的整体复杂度会变成O(n^2 log n)数据量一大直接超时。滚动哈希稍微多写几行但换来的是O(n log n)的稳定表现这笔账值得算。3. 树形DP与依赖关系的套路压轴前的那道“送命题”猿辅导笔试的第二道算法题通常有点分量2023这套卷子里考了一道跟“课程依赖”有关的树形动态规划。题目大致是题目现在有n门课程编号1到n课程之间存在先修关系形成一个森林。每门课有一个学习收益w[i]。如果直接学习某门课需要先完成它的所有先修课程。你可以从任意课程开始学习但必须满足依赖关系。请问在最多选择m门课程的情况下能获得的最大收益是多少这题其实是经典的“树形背包”问题洛谷上有一道叫“选课”的题跟它几乎一模一样。难点在于如果只是一条线性的先修链那很简单但它是森林而且每门课只能选一次依赖关系构成了一棵树多叉树。3.1 把森林转成树的第一板斧遇到森林最常用的处理方式就是虚拟一个“超级根节点”编号0收益为0作为所有根节点的父亲。这样森林就变成了一棵以0为根的树。然后定义dp[u][j]表示在以u为根的子树中最多选择j门课程能获得的最大收益。这里要注意如果选择了u这个节点那么它的子节点才能被选择如果不选u子节点一个都不能选因为依赖关系决定了必须先修u才能修子节点。所以状态转移方程就出来了dp[u][j] max(dp[u][j], dp[u][j-t] dp[v][t])其中v是u的一个子节点t是在v的子树中选择的课程数量。这个过程本质上是把子节点的dp结果做一次“分组背包”——每个子节点看作一组从每组中最多选一个t出来。3.2 子树大小的剪枝优化直接O(n*m^2)的复杂度在n1000、m100时是能过的但n到10^5就危险了。这里有个经典优化背包容量上限每次只用到当前子树大小不需要每次都跑到m。代码实现如下def solve(n, m, w, pre): # 建树虚拟根节点0 children [[] for _ in range(n1)] for i in range(1, n1): p pre[i] children[p].append(i) dp [[0] * (m1) for _ in range(n1)] size [1] * (n1) # 记录子树大小 def dfs(u): dp[u][1] w[u] # 如果只选一个就是选自己 size[u] 1 for v in children[u]: dfs(v) # 分组背包 new_dp dp[u][:] for j in range(min(size[u], m), 0, -1): for t in range(1, min(size[v], m - j 1) 1): if dp[u][j] ! -1 and dp[v][t] ! -1: new_dp[j t] max(new_dp[j t], dp[u][j] dp[v][t]) dp[u] new_dp size[u] size[v] dfs(0) # 因为虚拟根节点收益为0选它相当于少选一门 # 题目要求最多选m门可以直接取 max(dp[0][:m1]) return max(dp[0][:m1])这个写法有几个细节dp[u][1] w[u]意味着选了u这里是把u本身算作一门课子节点背包循环时new_dp dp[u][:]是很关键的——不能直接在dp[u]上改否则同一层会重复计算虚拟根节点0的dp里dp[0][1] 0它占了一个选择名额但收益为0所以最后取max的时候要包含它但实际选课数可能少一门3.3 为什么不能用贪心很多人在这种“选课获得最大收益”的题目上第一反应是贪心——按收益从大到小排序然后依次选不就行了如果你也这么想我劝你谨慎。树形依赖关系决定了收益高的课可能被收益低的先修课卡住你选了它就必须选那门低收益的课这时候单纯按收益排序是得不到最优解的。树形背包的本质是穷举所有“在满足约束条件下的组合”只有这样才保证正确性。笔试里遇到这类题宁可用O(n^2)的DP也别用可能拿零分的贪心。4. 多线程与并发那道让算法高手翻车的工程压轴题2023年笔试卷子最后一题是个“计算题设计题”的混合体题目本身不长但信息密度很大。大意是题目实现一个线程安全的线程池用于异步处理一批任务。要求支持提交任务、关闭线程池、等待所有任务完成。请写出核心代码并说明你的设计如何处理任务队列的并发竞争。看到这题算法好的同学可能有点懵因为这考察的完全是工程能力跟算法题是两套体系。但这类题目在猿辅导的笔试里出现频率不低因为在线教育系统有大量异步任务——比如作业批改、课程视频转码、消息推送——全都要靠线程池来承载。4.1 线程池的核心组件拆解一个从零实现的线程池核心组件无非四个工作线程集合任务队列线程池状态运行中/关闭拒绝策略任务队列用queue.Queue还是自定义链表queue.Queue内部已经用threading.Condition实现了线程安全直接用就行。关键是“关闭”和“等待全部完成”这两个语义要处理好。我的思路是用一个标志位_shutdown表示线程池是否关闭用一个计数器_pending_tasks表示还没有完成的任务数配合Condition来实现关闭时的等待。下面是一份可以直接跑的最小实现代码不长但覆盖了所有核心点import threading import queue import time class ThreadPool: def __init__(self, num_threads): self._num_threads num_threads self._work_queue queue.Queue() self._shutdown False self._pending_tasks 0 self._cond threading.Condition() self._threads [] self._start_threads() def _start_threads(self): for _ in range(self._num_threads): t threading.Thread(targetself._worker) t.daemon True t.start() self._threads.append(t) def _worker(self): while True: with self._cond: while not self._shutdown and self._work_queue.empty(): self._cond.wait() if self._shutdown and self._work_queue.empty(): break task self._work_queue.get() try: task() except Exception as e: print(fTask error: {e}) finally: with self._cond: self._pending_tasks - 1 self._cond.notify_all() def submit(self, task): with self._cond: if self._shutdown: raise RuntimeError(ThreadPool is shutdown) self._pending_tasks 1 self._work_queue.put(task) self._cond.notify() def shutdown(self, waitTrue): with self._cond: self._shutdown True self._cond.notify_all() if wait: self.wait_all() def wait_all(self): with self._cond: while self._pending_tasks 0: self._cond.wait() # 使用示例 if __name__ __main__: pool ThreadPool(4) for i in range(10): pool.submit(lambda ii: time.sleep(0.1) or print(fTask {i} done)) pool.shutdown(waitTrue) print(All tasks completed)4.2 为什么用Condition而不是Event很多人的第一直觉是用threading.Event做线程间的同步但这里有个问题Event是广播式的它不能精确控制“某个任务完成”这个条件。我们真正需要的是“任务队列空且没有执行中的任务”这种复合条件Condition最合适因为它支持多条件等待和通知。self._pending_tasks这个计数器是关键中的关键。如果不加它shutdown(waitTrue)时只判断队列是否为空是不够的因为可能有任务正在被某个worker执行队列已经空了但你直接退出就会丢失正在执行的任务。有了这个计数器主线程可以精确地等待所有任务真正结束。4.3 笔试中怎么写出让面试官眼前一亮的答案光写出一个能跑的线程池可能只拿60%的分。想拿高分你得在代码里体现几个“亮点”这些也是面试官期待看到的亮点一任务异常隔离。worker执行task时用try-except包住而不是让异常杀掉线程。这个细节看似很小但能体现你对线程池稳定性的理解。亮点二关闭时的双条件判断。while not self._shutdown and self._work_queue.empty()这个条件很讲究它保证线程在shutdown之后还能把队列里剩余的任务消费完而不是直接退出。亮点三避免死锁的思考。如果任务A内部又去submit任务B而线程池只有1个线程那A在等B完成但这个线程还在执行A就死锁了。笔试时如果能主动提到这种现象并说明自己在实际设计时会加“任务不能提交到同一个线程池”的限制或使用非阻塞提交那这题的印象分会很高。亮点四说明替代方案比码代码更重要。比如可以提一句“在生产环境中我一般直接用ThreadPoolExecutor它的内部实现比这个复杂得多包括工作线程的回收、线程数动态调整等。笔试手写是为了展示核心逻辑真实项目里要优先复用标准库。”5. 数据库与索引优化一道容易被忽略的SQL场景题猿辅导这套笔试还有一道数据库题隐藏在一段业务描述里。大意是题目你的系统中有一个课程表course(id, name, teacher_id, create_time)一个选课表student_course(id, student_id, course_id, score)。现在需要查询“选了课程数量最多的前10名学生的学号和选课数量”请写出SQL并创建合适的索引。这种题看起来简单但想答得特别完整并不容易。多数人能写出SQL但问到底层索引时就开始含糊了。5.1 SQL与索引设计最简单的写法是SELECT student_id, COUNT(*) AS cnt FROM student_course GROUP BY student_id ORDER BY cnt DESC LIMIT 10;索引怎么建这里的关键是查询中只有一个等值条件student_id且需要做GROUP BY。对于这种“按某列分组并统计数量”的查询直接在student_course表上建(student_id, course_id)的联合索引是合适的——因为count(*)只需要扫描索引不需要回表速度会快很多。要注意一个细节不能只建student_id的单列索引虽然GROUP BY能用上它但count(*)要回表去拿course_id在数据量大的时候回表开销很大。联合索引(student_id, course_id)可以做成覆盖索引整个查询在索引层面就完成了速度是数量级的差别。5.2 为什么GROUP BY需要排序或哈希这题另一个容易被追问的点是GROUP BY是怎么执行的MySQL里GROUP BY有两种实现方式——使用临时表配合文件排序或者利用索引的有序性直接从索引扫描时完成分组。建立(student_id, course_id)联合索引后因为student_id是有序的MySQL可以在扫描索引时顺带完成分组避免了临时表和文件排序效率高得多。笔试答案里如果有这句话基本就能拉开跟普通考生的差距。6. 计算机网络与系统设计你认为在线教育的“高并发”卡在哪最后再说一道不太像笔试的题。猿辅导2023这套卷子最后面藏了一道开放题请简要说明在线直播课的互动系统在高峰期会出现哪些性能瓶颈你会如何设计或优化这种题没有标准答案但判卷是有得分点的。你不需要写出完整的架构但得展现出你有“系统性思考”的能力。我的答题框架一般是第一拆解请求链路。从学生端到直播间会经过网关、业务服务、消息推送、实时信令服务、存储等多个环节。你要逐一分析每个环节在高并发下的瓶颈是什么。第二针对瓶颈给出具体方案。比如业务服务层可以水平扩展但数据库是单点的话就白搭所以要加缓存或分库分表再比如实时互动消息的推送如果用轮询几百个学生同时轮询会把服务器打崩应该改成长连接或者WebSocket方案。第三用数据说话。比如一个2万人同时在线的直播课假设每10秒产生一条互动消息那消息推送服务的QPS就是2000存储层每秒要写入2000条记录——如果按这个量级设计系统你自然知道哪些组件才是真正的瓶颈。我当时给学弟的建议是写这类题不要追求面面俱到而是选两个关键链路讲透让面试官看到你是真的思考过而不是在背八股文。7. 备考策略如何用最后两周高效准备这类笔试说完了具体题目最后聊聊备考策略。我知道很多同学是临时抱佛脚型的如果是这种情况我给你一套“两周冲刺激活方案”亲测有效。第一周查漏补缺重点抓高频考点。根据猿辅导的历年真题笔试高频考点就那几类字符串/哈希、树形DP、二分搜索、并查集、多线程、SQL聚合查询。你把每个考点各找三道代表性题目练手不求多但求把“套路”吃透。尤其是树形DP和并查集这两个概念很多人觉得难但其实代码模板很短背下来就能用。第二周整套模拟 时间控制。按笔试的时长通常90分钟完整做模拟卷严格计时。我发现很多人不是不会做而是时间分配不合理——前面小题写太久了压轴题没时间动。我的建议是先用15分钟把全部题目扫一遍分辨出哪些是送分题、哪些是攻坚题然后优先保送分题再做攻坚题。算法题如果20分钟没思路果断跳到下一题不要恋战。另外练题的时候一定要动手写完整代码尤其注意边界条件。很多人看题解觉得自己懂了一到笔试现场怎么写怎么错就是因为平时练得太少。我帮学弟复盘时发现70%的提交不过是因为边界条件没处理而不是核心逻辑不对。多线程和SQL题也要动手写Python的threading库不跑一遍你根本不会意识到Condition和Event的区别SQL不实际执行你也很难理解GROUP BY在底层做了多少事。最后说一句掏心窝的话笔试没过不代表你技术不行很多时候是准备方向歪了。把每一道笔试题当成一个真实业务场景去分析而不是当成一道纯算法题去套模板你会发现这套卷子的难度其实没那么高拿到offer只是时间问题。
去年秋招那会儿我帮实验室好几个师弟改简历、模拟面试发现一个特别普遍的现象很多人刷题刷了几百道LeetCode周赛也能稳住三道题但一到“猿辅导2023校园招聘技术类笔试一”这种带公司特色的综合笔试就直接懵圈。倒不是题目难到天上去而是这套笔试卷子的风格跟纯刷题平台完全不一样——它考的是你在有限时间内能不能把数据结构、算法、系统设计、甚至业务场景串起来思考。这篇文章我就拿这套笔试的典型题目做个深度拆解不讲虚的直接上硬货每道题怎么审、怎么破、代码怎么写、有哪些坑是笔试时最容易踩的。不管你是正在准备秋招的应届生还是想跳槽的社招选手只要目标是国内一二线互联网公司的技术岗这套题背后的出题逻辑都值得你花半小时认真过一遍。1. 为什么猿辅导的笔试跟LeetCode风格差异这么大先聊点题外话。很多人拿到猿辅导的笔试卷子第一反应是“怎么还有这种题”这恰恰说明你还没摸透这家公司的出题套路。跟纯互联网大厂的海量题库不同猿辅导作为教育科技公司它的技术笔试有一个很明显的倾向既考基本功也考业务理解。我翻了近三年的真题总结下来有三个核心特点。第一题目量不大但单题分值高。一套卷子通常四到六道大题每道题都可能是一个完整的场景描述而不是孤立的算法题。这意味着你如果某道题卡住了整块分值直接丢掉容错率很低。第二算法题偏爱“变形题”。比如你刷过“最长递增子序列”它可能会给你一个“按学科成绩排名”的场景你刷过“二叉树层序遍历”它可能会结合“课程表依赖关系”来考。知识点还是那个知识点但包装换了很多人就认不出来了。第三会有一道“压轴题”专门考工程思维。这道题不一定多难但一定涉及多线程、内存管理、分布式、或者大数据量处理目的是筛掉那些只会背题、不会解决实际问题的人。我印象最深的是去年一道压轴题题目是“设计一个支持百万并发排课的调度系统”要求写出核心数据结构并说明线程安全策略。这题放在LeetCode上根本不算算法题但在笔试里它就是用来区分“刷题机器”和“真正理解工程”的。所以准备这套笔试的思路必须调整刷题是基础但不是全部。你需要把每个知识点都往“如果做成一个真实功能会怎样”的方向想一遍。2. 字符串与哈希的经典组合拳第一道送分题的多种解法笔试第一题通常不会太难目的是让你热身但越是这样越容易翻车。猿辅导2023这套卷子的第一题大致是这样的题目给定一个字符串s和一个整数k请找出字符串中恰好出现k次的最长子串的长度。如果不存在则返回-1。很多人的第一反应是“滑动窗口”这确实是常见解法但这里有个坑题目要求“恰好出现k次”它没有说明子串是否必须连续。我当年帮一个学弟复盘时发现他直接用滑动窗口做了结果只过了30%的测试用例就是因为没审清楚“子串”在题目里的定义。2.1 审题比写代码更重要我通常拿到这种题先做三件事确认子串是否连续——这在中文语境里经常有歧义确认“恰好k次”是指在整个原字符串中出现的次数还是字面意义上的字符频率确认字符串长度范围这决定了能不能用O(n^2)暴力假设题目中的子串是“连续子串”并且“恰好出现k次”是指这个子串作为整体在原串中出现的次数那解法就清晰了。核心思路是这样的如果一个子串出现了恰好k次那它的长度一定不会超过某个阈值。更关键的是我们可以枚举所有可能的子串起点用哈希表记录每个子串出现的次数。但直接枚举所有子串是O(n^2)的如果字符串长度到10^5就会超时。这里有一个优化技巧用“后缀数组高度数组”或者“后缀自动机”来解决但笔试现场写后缀自动机不太现实。更实用的做法是二分答案。二分答案的check函数怎么写对于长度为len的所有子串用滚动哈希也叫Rabin-Karp哈希计算每个子串的哈希值存到哈希表里统计每个哈希值出现的次数。如果某个哈希值出现的次数等于k就说明存在长度为len的子串恰好出现k次。这里要注意哈希碰撞的问题笔试中一般用双哈希或者直接用一个128位的pair来降低碰撞概率。2.2 代码实现与边界条件我给出一个比较稳的Python实现这个风格在笔试里既好写又好调试def solve(s: str, k: int) - int: n len(s) if k 0 or k n: return -1 base 131 mod 10**9 7 # 预处理前缀哈希和幂 prefix [0] * (n 1) power [1] * (n 1) for i in range(n): prefix[i1] (prefix[i] * base ord(s[i])) % mod power[i1] power[i] * base % mod def get_hash(l, r): # 左闭右开区间 [l, r) return (prefix[r] - prefix[l] * power[r-l]) % mod # 二分答案 left, right 1, n ans -1 while left right: mid (left right) // 2 freq {} found False for i in range(n - mid 1): h get_hash(i, i mid) freq[h] freq.get(h, 0) 1 if freq[h] k: found True break if found: ans mid left mid 1 else: right mid - 1 return ans这段代码有几个细节值得注意power数组预处理了base的幂这样get_hash就是O(1)操作二分答案从1到n每次check是O(n)整体O(n log n)一旦发现某个哈希值出现次数达到k就提前返回这是个小优化边界条件kn直接返回-1因为任何子串不可能出现超过n次笔试中容易踩的坑还有子串长度mid不能为0如果k0按题意应该返回-1还是0这个必须看题目说明。我一般会写一个注释说明按题意处理。2.3 为什么不用Python自带的字符串切片这个问题我在模拟面试时被问过很多次。用s[i:ilen]做切片然后放入字典代码确实更短但笔试环境里字符串切片是O(len)的整体复杂度会变成O(n^2 log n)数据量一大直接超时。滚动哈希稍微多写几行但换来的是O(n log n)的稳定表现这笔账值得算。3. 树形DP与依赖关系的套路压轴前的那道“送命题”猿辅导笔试的第二道算法题通常有点分量2023这套卷子里考了一道跟“课程依赖”有关的树形动态规划。题目大致是题目现在有n门课程编号1到n课程之间存在先修关系形成一个森林。每门课有一个学习收益w[i]。如果直接学习某门课需要先完成它的所有先修课程。你可以从任意课程开始学习但必须满足依赖关系。请问在最多选择m门课程的情况下能获得的最大收益是多少这题其实是经典的“树形背包”问题洛谷上有一道叫“选课”的题跟它几乎一模一样。难点在于如果只是一条线性的先修链那很简单但它是森林而且每门课只能选一次依赖关系构成了一棵树多叉树。3.1 把森林转成树的第一板斧遇到森林最常用的处理方式就是虚拟一个“超级根节点”编号0收益为0作为所有根节点的父亲。这样森林就变成了一棵以0为根的树。然后定义dp[u][j]表示在以u为根的子树中最多选择j门课程能获得的最大收益。这里要注意如果选择了u这个节点那么它的子节点才能被选择如果不选u子节点一个都不能选因为依赖关系决定了必须先修u才能修子节点。所以状态转移方程就出来了dp[u][j] max(dp[u][j], dp[u][j-t] dp[v][t])其中v是u的一个子节点t是在v的子树中选择的课程数量。这个过程本质上是把子节点的dp结果做一次“分组背包”——每个子节点看作一组从每组中最多选一个t出来。3.2 子树大小的剪枝优化直接O(n*m^2)的复杂度在n1000、m100时是能过的但n到10^5就危险了。这里有个经典优化背包容量上限每次只用到当前子树大小不需要每次都跑到m。代码实现如下def solve(n, m, w, pre): # 建树虚拟根节点0 children [[] for _ in range(n1)] for i in range(1, n1): p pre[i] children[p].append(i) dp [[0] * (m1) for _ in range(n1)] size [1] * (n1) # 记录子树大小 def dfs(u): dp[u][1] w[u] # 如果只选一个就是选自己 size[u] 1 for v in children[u]: dfs(v) # 分组背包 new_dp dp[u][:] for j in range(min(size[u], m), 0, -1): for t in range(1, min(size[v], m - j 1) 1): if dp[u][j] ! -1 and dp[v][t] ! -1: new_dp[j t] max(new_dp[j t], dp[u][j] dp[v][t]) dp[u] new_dp size[u] size[v] dfs(0) # 因为虚拟根节点收益为0选它相当于少选一门 # 题目要求最多选m门可以直接取 max(dp[0][:m1]) return max(dp[0][:m1])这个写法有几个细节dp[u][1] w[u]意味着选了u这里是把u本身算作一门课子节点背包循环时new_dp dp[u][:]是很关键的——不能直接在dp[u]上改否则同一层会重复计算虚拟根节点0的dp里dp[0][1] 0它占了一个选择名额但收益为0所以最后取max的时候要包含它但实际选课数可能少一门3.3 为什么不能用贪心很多人在这种“选课获得最大收益”的题目上第一反应是贪心——按收益从大到小排序然后依次选不就行了如果你也这么想我劝你谨慎。树形依赖关系决定了收益高的课可能被收益低的先修课卡住你选了它就必须选那门低收益的课这时候单纯按收益排序是得不到最优解的。树形背包的本质是穷举所有“在满足约束条件下的组合”只有这样才保证正确性。笔试里遇到这类题宁可用O(n^2)的DP也别用可能拿零分的贪心。4. 多线程与并发那道让算法高手翻车的工程压轴题2023年笔试卷子最后一题是个“计算题设计题”的混合体题目本身不长但信息密度很大。大意是题目实现一个线程安全的线程池用于异步处理一批任务。要求支持提交任务、关闭线程池、等待所有任务完成。请写出核心代码并说明你的设计如何处理任务队列的并发竞争。看到这题算法好的同学可能有点懵因为这考察的完全是工程能力跟算法题是两套体系。但这类题目在猿辅导的笔试里出现频率不低因为在线教育系统有大量异步任务——比如作业批改、课程视频转码、消息推送——全都要靠线程池来承载。4.1 线程池的核心组件拆解一个从零实现的线程池核心组件无非四个工作线程集合任务队列线程池状态运行中/关闭拒绝策略任务队列用queue.Queue还是自定义链表queue.Queue内部已经用threading.Condition实现了线程安全直接用就行。关键是“关闭”和“等待全部完成”这两个语义要处理好。我的思路是用一个标志位_shutdown表示线程池是否关闭用一个计数器_pending_tasks表示还没有完成的任务数配合Condition来实现关闭时的等待。下面是一份可以直接跑的最小实现代码不长但覆盖了所有核心点import threading import queue import time class ThreadPool: def __init__(self, num_threads): self._num_threads num_threads self._work_queue queue.Queue() self._shutdown False self._pending_tasks 0 self._cond threading.Condition() self._threads [] self._start_threads() def _start_threads(self): for _ in range(self._num_threads): t threading.Thread(targetself._worker) t.daemon True t.start() self._threads.append(t) def _worker(self): while True: with self._cond: while not self._shutdown and self._work_queue.empty(): self._cond.wait() if self._shutdown and self._work_queue.empty(): break task self._work_queue.get() try: task() except Exception as e: print(fTask error: {e}) finally: with self._cond: self._pending_tasks - 1 self._cond.notify_all() def submit(self, task): with self._cond: if self._shutdown: raise RuntimeError(ThreadPool is shutdown) self._pending_tasks 1 self._work_queue.put(task) self._cond.notify() def shutdown(self, waitTrue): with self._cond: self._shutdown True self._cond.notify_all() if wait: self.wait_all() def wait_all(self): with self._cond: while self._pending_tasks 0: self._cond.wait() # 使用示例 if __name__ __main__: pool ThreadPool(4) for i in range(10): pool.submit(lambda ii: time.sleep(0.1) or print(fTask {i} done)) pool.shutdown(waitTrue) print(All tasks completed)4.2 为什么用Condition而不是Event很多人的第一直觉是用threading.Event做线程间的同步但这里有个问题Event是广播式的它不能精确控制“某个任务完成”这个条件。我们真正需要的是“任务队列空且没有执行中的任务”这种复合条件Condition最合适因为它支持多条件等待和通知。self._pending_tasks这个计数器是关键中的关键。如果不加它shutdown(waitTrue)时只判断队列是否为空是不够的因为可能有任务正在被某个worker执行队列已经空了但你直接退出就会丢失正在执行的任务。有了这个计数器主线程可以精确地等待所有任务真正结束。4.3 笔试中怎么写出让面试官眼前一亮的答案光写出一个能跑的线程池可能只拿60%的分。想拿高分你得在代码里体现几个“亮点”这些也是面试官期待看到的亮点一任务异常隔离。worker执行task时用try-except包住而不是让异常杀掉线程。这个细节看似很小但能体现你对线程池稳定性的理解。亮点二关闭时的双条件判断。while not self._shutdown and self._work_queue.empty()这个条件很讲究它保证线程在shutdown之后还能把队列里剩余的任务消费完而不是直接退出。亮点三避免死锁的思考。如果任务A内部又去submit任务B而线程池只有1个线程那A在等B完成但这个线程还在执行A就死锁了。笔试时如果能主动提到这种现象并说明自己在实际设计时会加“任务不能提交到同一个线程池”的限制或使用非阻塞提交那这题的印象分会很高。亮点四说明替代方案比码代码更重要。比如可以提一句“在生产环境中我一般直接用ThreadPoolExecutor它的内部实现比这个复杂得多包括工作线程的回收、线程数动态调整等。笔试手写是为了展示核心逻辑真实项目里要优先复用标准库。”5. 数据库与索引优化一道容易被忽略的SQL场景题猿辅导这套笔试还有一道数据库题隐藏在一段业务描述里。大意是题目你的系统中有一个课程表course(id, name, teacher_id, create_time)一个选课表student_course(id, student_id, course_id, score)。现在需要查询“选了课程数量最多的前10名学生的学号和选课数量”请写出SQL并创建合适的索引。这种题看起来简单但想答得特别完整并不容易。多数人能写出SQL但问到底层索引时就开始含糊了。5.1 SQL与索引设计最简单的写法是SELECT student_id, COUNT(*) AS cnt FROM student_course GROUP BY student_id ORDER BY cnt DESC LIMIT 10;索引怎么建这里的关键是查询中只有一个等值条件student_id且需要做GROUP BY。对于这种“按某列分组并统计数量”的查询直接在student_course表上建(student_id, course_id)的联合索引是合适的——因为count(*)只需要扫描索引不需要回表速度会快很多。要注意一个细节不能只建student_id的单列索引虽然GROUP BY能用上它但count(*)要回表去拿course_id在数据量大的时候回表开销很大。联合索引(student_id, course_id)可以做成覆盖索引整个查询在索引层面就完成了速度是数量级的差别。5.2 为什么GROUP BY需要排序或哈希这题另一个容易被追问的点是GROUP BY是怎么执行的MySQL里GROUP BY有两种实现方式——使用临时表配合文件排序或者利用索引的有序性直接从索引扫描时完成分组。建立(student_id, course_id)联合索引后因为student_id是有序的MySQL可以在扫描索引时顺带完成分组避免了临时表和文件排序效率高得多。笔试答案里如果有这句话基本就能拉开跟普通考生的差距。6. 计算机网络与系统设计你认为在线教育的“高并发”卡在哪最后再说一道不太像笔试的题。猿辅导2023这套卷子最后面藏了一道开放题请简要说明在线直播课的互动系统在高峰期会出现哪些性能瓶颈你会如何设计或优化这种题没有标准答案但判卷是有得分点的。你不需要写出完整的架构但得展现出你有“系统性思考”的能力。我的答题框架一般是第一拆解请求链路。从学生端到直播间会经过网关、业务服务、消息推送、实时信令服务、存储等多个环节。你要逐一分析每个环节在高并发下的瓶颈是什么。第二针对瓶颈给出具体方案。比如业务服务层可以水平扩展但数据库是单点的话就白搭所以要加缓存或分库分表再比如实时互动消息的推送如果用轮询几百个学生同时轮询会把服务器打崩应该改成长连接或者WebSocket方案。第三用数据说话。比如一个2万人同时在线的直播课假设每10秒产生一条互动消息那消息推送服务的QPS就是2000存储层每秒要写入2000条记录——如果按这个量级设计系统你自然知道哪些组件才是真正的瓶颈。我当时给学弟的建议是写这类题不要追求面面俱到而是选两个关键链路讲透让面试官看到你是真的思考过而不是在背八股文。7. 备考策略如何用最后两周高效准备这类笔试说完了具体题目最后聊聊备考策略。我知道很多同学是临时抱佛脚型的如果是这种情况我给你一套“两周冲刺激活方案”亲测有效。第一周查漏补缺重点抓高频考点。根据猿辅导的历年真题笔试高频考点就那几类字符串/哈希、树形DP、二分搜索、并查集、多线程、SQL聚合查询。你把每个考点各找三道代表性题目练手不求多但求把“套路”吃透。尤其是树形DP和并查集这两个概念很多人觉得难但其实代码模板很短背下来就能用。第二周整套模拟 时间控制。按笔试的时长通常90分钟完整做模拟卷严格计时。我发现很多人不是不会做而是时间分配不合理——前面小题写太久了压轴题没时间动。我的建议是先用15分钟把全部题目扫一遍分辨出哪些是送分题、哪些是攻坚题然后优先保送分题再做攻坚题。算法题如果20分钟没思路果断跳到下一题不要恋战。另外练题的时候一定要动手写完整代码尤其注意边界条件。很多人看题解觉得自己懂了一到笔试现场怎么写怎么错就是因为平时练得太少。我帮学弟复盘时发现70%的提交不过是因为边界条件没处理而不是核心逻辑不对。多线程和SQL题也要动手写Python的threading库不跑一遍你根本不会意识到Condition和Event的区别SQL不实际执行你也很难理解GROUP BY在底层做了多少事。最后说一句掏心窝的话笔试没过不代表你技术不行很多时候是准备方向歪了。把每一道笔试题当成一个真实业务场景去分析而不是当成一道纯算法题去套模板你会发现这套卷子的难度其实没那么高拿到offer只是时间问题。
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
