猿辅导2020校招算法岗笔试复盘：核心考点与解题套路详解

2020年秋招的时候我投了猿辅导的算法岗笔试是在牛客网上完成的全程摄像头监控两个小时的题量包含选择题和编程题。那场笔试给我的印象很深选择题考得很杂从机器学习基础到C内存布局都有涉及编程题倒是不偏不怪全是基本功但基本功不扎实的话一道题就能卡死你。今天把这套猿辅导2020校招笔试算法岗一拆开聊聊给准备投算法岗、尤其是在线教育大厂的同学一个参考。文章不会贴完整原题但我会把考点、题型分布、解题思路和实战技巧讲透保证你看完对这类笔试的套路心里有底。1. 猿辅导算法岗笔试到底考什么1.1 题型分布与整体感受先说结论猿辅导这套笔试卷子分为两个部分——基础选择题和编程题。选择题大概有20道左右覆盖范围很广包括数据结构、操作系统、计算机网络、机器学习基础、深度学习常识偶尔还会有一两道数学题。编程题一般是2到3道难度梯度拉得很明显第一题通常是签到题最后一题就是真正拉开差距的压轴题。整体感受用一个字形容就是杂。我当时复习的时候把大量精力放在机器学习算法和深度学习模型上结果选择题里确实考了一些比如过拟合的解决方法、交叉熵和KL散度的关系但更多题是数据结构与算法的基础题。反而是最后几道编程题让我意识到自己刷题量虽然不少但对某些经典算法的理解还是停留在背模板的层面换个包装就不会了。如果你准备投猿辅导或者其他在线教育公司的算法岗我的建议是不要只盯着机器学习、深度学习数据结构和算法的基础一定要扎实前面的选择题和后面的编程题才是决定你能否进面试的关键。1.2 考察范围与难度定位从难度上看猿辅导算法岗笔试的编程题整体处于LeetCode Medium偏上的水平偶尔会有Hard级别的题目但不会特别偏门。考察的知识点主要集中在数据结构数组、链表、栈、队列、堆、二叉树、并查集基础算法排序、二分、贪心、动态规划、深度优先搜索、广度优先搜索字符串KMP、Trie树、字符串哈希进阶状态压缩DP、树状数组、线段树这些知识点看起来都是常规操作但关键在于题目包装。猿辅导的编程题特别喜欢结合实际业务场景比如课程安排、学生选课、题目推荐这类场景本质考的是区间调度、拓扑排序、贪心策略但你如果看不穿这层包装就会觉得题目很绕。另外要注意的是选择题占的分值并不低。有些同学觉得选择题嘛随便选选就行重点搞编程题这是个误区。选择题错个五六道编程题就算全对总分也可能被拉下来。我当时认识的一个朋友就是编程题全AC了但选择题正确率不高最后没进面试。所以一定要两条腿走路选择题和编程题都不能放弃。2. 核心考点拆解哪些算法必须吃透2.1 数据结构类题目永远是重头戏不管什么公司什么岗位数据结构都是笔试的重头戏猿辅导也不例外。从历年题目来看链表、二叉树、堆、并查集是高频考点而且经常不是单独考一个结构而是两个结构结合着考。先说链表。链表的题说难不难说简单也不简单核心考察的是指针操作和边界处理。比如常见的链表反转、合并两个有序链表、找链表中间节点这些必须写得又快又准。我建议你把这些基础链表操作练到肌肉记忆的程度因为笔试如果考链表往往不会只考一道单纯的反转而是会跟其他知识点结合比如判断链表是否有环并找到环的入口两个链表找第一个公共节点这类经典题。二叉树更是绕不开的重点。层序遍历、前中后序遍历包括递归和非递归写法、二叉搜索树的相关操作、最近公共祖先这些都是高频中的高频。尤其是非递归遍历很多同学递归写得溜一到非递归就卡壳建议多练几遍。再强调一下并查集。很多同学平时刷题不太关注并查集但它出现的频率其实很高尤其是在处理连通性分组朋友圈这类问题的时候。2020年这套笔试的选择题里甚至直接考了并查集的路径压缩和按秩合并的复杂度分析编程题里也出现过需要用到并查集的题。所以并查集一定要掌握包括路径压缩的递归写法和非递归写法都要会。堆也是个常考点。优先队列的实现原理、堆排序、TopK问题这些不仅要会用还要理解底层是怎么实现的。比如选择题问你堆的插入和删除操作的时间复杂度如果你只背了答案没理解原理换个问法可能就懵了。2.2 动态规划与贪心从套路到变种动态规划几乎是所有算法岗笔试的必考内容猿辅导也不例外。我的感受是DP题在笔试中的占比非常高而且往往是区分度最大的题目。DP的核心就三步定义状态、写转移方程、确定初始化。听起来简单但实际操作中大部分人的问题出在前两步。定义状态这一步要搞清楚题目问什么、有哪些维度是必须纳入状态的。比如前i个物品中选若干个总重量不超过W的最大价值那状态就得包含i和W两个维度。转移方程这一步要想清楚当前状态跟哪些前置状态有关是取max还是取min是累加还是求概率。常见的基础DP类型你得烂熟于心背包问题0-1背包、完全背包、多重背包、最长递增子序列、最长公共子序列、编辑距离、区间DP、数位DP、状态压缩DP。我当时在猿辅导这套卷子里就碰到了一道状态压缩DP的题本质是旅行商问题的变种但包装成了安排老师上课路线之类的情景如果你没见过状态压缩的套路光读题就会花掉好几分钟。贪心算法也是必考但贪心有个特点——不考则已一考就容易卡住。因为贪心策略的证明往往比写代码难。做贪心题的时候我有个习惯先用直觉想出一个贪心策略然后立刻在脑子里找反例如果找不出反例再尝试用手工模拟的小样例验证。如果验证通过多半这个贪心是对的。写代码的时候再注意排序规则和比较函数的写法C的sort比较器如果写反了整个算法直接废掉贪心题一般就稳了。个人感受是贪心题最常考的套路是区间问题比如区间调度最多能安排多少个不重叠的区间、区间合并、区间选点。以课程安排为背景考的可能就是一天最多能上几节课这类问题。排序规则要么按右端点升序要么按左端点升序关键是看题目约束条件。2.3 字符串与搜索容易被忽略的送分题字符串这块必须掌握KMP算法。我记得热搜词里就有在KMP算法中对于模式串pabacaba其next数组这种题目在笔试选择题里出现过太多次了。KMP的next数组求法一定要做到能手动模拟求出来而且能快速写出来。你说笔试的时候现场推next数组的求法可以但会很浪费时间而且容易出错。建议在笔试前把next数组的两种求法前缀函数和失配指针都手写一遍做到肌眼心三者合一。除了KMPTrie树也是常客尤其是处理前缀匹配、单词查找这类问题。Trie树的实现比KMP简单就是一个个节点往下走但要注意节点的子节点用数组还是哈希表存的区别。笔试如果考Trie树一般不会让你从零开始实现一整棵而是考某个核心操作比如插入和查询的复杂度、如何判断一个单词是否完整存在等。搜索算法这块深度优先搜索和广度优先搜索就不必多说了必须掌握。关键是搞清楚什么时候用DFS、什么时候用BFS求最短路径、最少步数这类问题用BFS求连通分量、排列组合、棋盘问题、回溯枚举这类用DFS。尤其注意DFS中的剪枝很多看上去数据规模不大的题不剪枝就会超时。剪枝的技巧包括最优性剪枝、可行性剪枝、记忆化搜索这些针对性地练一练笔试的时候非常实用。3. 真题实战复盘三道有代表性的笔试题3.1 第一题排序与双指针的经典组合编程题第一题一般是签到题但这道签到题也不是单纯给个数组让你排个序。我碰到的那道题大概是这样的给一个数组求出所有满足两数之和等于目标值的数对个数要求不重复计数。乍看之下很简单但数据规模很大不能用两层循环暴力解决。这题的标准解法是先排序再用双指针从两端向中间移动。排序之后左指针指向最小元素右指针指向最大元素如果两数之和等于目标值则找到一个数对然后移动指针如果小于目标值说明需要更大的数左指针右移如果大于目标值说明需要更小的数右指针左移。时间复杂度是排序的O(n log n)加上双指针扫描的O(n)。这道题的关键在于你会不会想到用双指针如果你平时刷题只刷题解、不总结套路看到两数之和可能第一反应就是哈希表。哈希表解法在这道题也能过但要注意去重逻辑容易写错。双指针解法因为先排序了去重就特别简单。所以笔试的时候遇到数组类问题可以多想一想如果先排序会不会变简单很多时候排序就是解题的钥匙。3.2 第二题二分答案处理最小化最大值问题第二题就有点意思了考的是二分答案。题目背景大概是要把一个长数组分成连续的若干段希望这么多段的和的最大值尽量小求这个最小值。这个表述一看就是经典的最小化最大值问题标准解法是二分答案。为什么想到二分答案因为最大值尽量小这种表述是二分答案的典型信号。我们把最大值当成一个变量x如果x太小分成的段数就会超过限制如果x足够大段数就够用。于是问题转化为给定一个上界x判断能否用不超过k段的分割方式使得每段和都不超过x这个判定问题用一次线性扫描贪心就行。写二分答案的时候最容易出错的地方是边界条件。初始的二分范围怎么定下界可以是数组最大值因为任何一段的sum都不小于单个元素上界可以是数组总和。然后while循环里left和right的更新是left mid 1还是left mid这个一定要根据具体代码风格统一好否则很容易死循环或者漏解。我记得当时很多人卡在判定函数上。有些人觉得能否分成不超过k段只要贪心去切就行这个思路没错但实现的时候要注意如果某个元素本身就大于x那直接返回false因为单独一段也放不下它。这个边界如果不处理样例都过不了。二分答案这题算是我吃过的教训里比较有代表性的一道后面我专门写了一篇文章讲二分答案的套路核心就是看到最大值最小最小值最大最多/最少能...使得...优先考虑二分。3.3 第三题状态压缩DP与图论背景最后一题是压轴题难度明显上一个台阶。题目背景是老师上课路线优化本质是给定一个有向图要求从起点出发经过所有指定节点再回到起点求最短总路程。这就是经典的旅行商问题TSP变种数据规模是n大约在15到20之间不能用全排列暴力需要用状态压缩DP。状态压缩DP的核心思路是用一个整数bitmask表示已经访问过的节点集合比如二进制第i位为1表示第i个节点已经去过。定义dp[mask][i]表示当前访问过的节点集合是mask最后停在节点i的最短路径长度。转移时枚举下一个要去的节点j如果j还没去过就用dp[mask][i] dist[i][j]去更新dp[mask | (1 j)][j]。最终答案是dp[(1 n) - 1][0]加上从最后一个节点回到起点的距离。这题难在两点一是要一眼看穿这是个状态压缩DP题而且能识别出n不超过20的约束条件就是状态压缩的信号。二是状态转移怎么写才不会漏解。我当时的做法是先不管题目背景直接抽象出图论模型然后回忆TSP问题的标准写法再把模板套进去。状态压缩DP如果你之前没写过现场是想不出来的所以这种题就是要靠平时的积累。这里要特别提醒一下状态压缩DP的数组通常是dp[1 n][n]n20时大小就是一百多万内存不是问题。但如果题目数据规模到了25以上状态数就是三千多万时间和内存都会出问题这时候就要考虑更高级的优化了。笔试中遇到n15到20的图论题通常就是想让你用状态压缩DP别犹豫。4. 笔试现场的应试技巧与时间分配4.1 先拿稳分再攻坚难题笔试时间两个小时选择题加编程题时间其实并不宽裕。我的策略是拿到试卷先花3分钟扫一遍所有题目大致判断难度分布。然后先做选择题因为选择题每题都有固定答案做一道得一道的分稳。遇到拿不准的选择题不要卡太久先标记一下最后有时间再回头想。编程题我建议按照从易到难的顺序来做。第一题通常比较简单尽量一遍写对不要返工。第二题如果5分钟内没思路先跳过看第三题。第三题作为压轴题往往最难但也不排除第一眼看上去很难、仔细想想其实是套路题的情况。总之就是先拿稳分再攻坚难题。不要跟一道题死磕死磕的代价往往是你后面的题没时间做心态还会崩。实际做题的时候我习惯先写一个能跑的暴力版本即使复杂度很高也先保证有分。然后用这个暴力版本作为对拍程序去验证后面想出来的高效算法是否正确。对拍是一个特别有用的技巧笔试环境虽然不能像本地那样方便地对拍但你可以先用小样例人工验证再把测试样例手动推演一遍。4.2 暴力解法与数据规模判断很多同学有个误区一上来就想最优解如果一时没想到就不敢下笔。其实笔试的判分规则一般是只要通过部分测试用例就有部分分数。所以即使你想不出最优解也可以先写一个暴力解法把能过的测试用例都过了拿到部分分。暴力解法的关键是要准确判断数据规模。比如n在10以内全排列或DFS都能过n在1000以内O(n^2)可以接受n在10^5级别就一定要O(n log n)或O(n)了。你需要在心里快速估算一下可能的解法能跑多少数据量然后决定是写暴力还是想优化。我当时的经验是拿到一道编程题先看数据范围。如果n在20以下秒想状态压缩或全排列n在100左右O(n^3)的DP可能可行n在1000左右O(n^2)可以接受n在10^5以上不好意思必须O(n log n)。这套判断标准可以帮你快速排除一些不靠谱的解法节约大量时间。4.3 调试与边界条件处理笔试现场最怕的就是本地能跑提交就WA。这种情况九成是边界条件出了问题。常见的边界条件有空数组、只有一个元素、元素重复、最大最小值、数组长度正好等于分割段数、目标值正好等于数组中某个元素等。我在做猿辅导这套卷子的时候就吃过元素重复的亏。当时第一题要求找两数之和等于目标值的数对个数数组里有重复元素我没有考虑去重结果样例过了但提交只有部分分数。后来我养成了一个习惯每道题写完代码后先自己想几个极端小样例测一下比如空数组、单元素数组、所有元素都相同的情况。这些极端样例往往能暴露问题而且想极端样例的时间成本很低收益却很高。另外要注意数据类型的坑。有些题目的中间结果会超过int范围必须用long long。尤其是涉及累加、求和的题目即使最终结果在int范围内中间过程也可能溢出。写代码的时候直接无脑用long long可以省掉很多麻烦。当然如果题目要求int输出最后cast回来就行。5. 复盘与避坑那些笔试后才明白的事5.1 常见失误汇总笔试结束后我复盘了一下发现自己的失误主要集中在几个方面也跟周围同学聊过发现大家踩的坑都差不多。第一个坑是读题不仔细。有些题目看起来是算法题实际上考的是某个特定的数据结构和技巧比如求所有区间的最大值之和这种题其实是单调栈的经典应用如果你只看题目表面以为可以用暴力或线段树就会方向性错误。建议拿到题先反复读两遍搞清题目的本质再动手。第二个坑是复杂度估算错误。有些同学写完代码不去算复杂度直接提交碰到大数据的测试用例就超时。建议在动手写之前快速想一下你的算法复杂度再对照数据规模判断能不能过如果能过就写不能过就想优化方案。不要写完了才后悔。第三个坑是掌握算法但不熟练。比如你知道KMP算法是干什么的但让你快速写出next数组却写不出来。笔试没有那么多时间让你慢慢回忆。所以平时刷题的时候重要的算法不要只看思路要动手写代码而且要多次重复写形成肌肉记忆。第四个坑是编程语言的细节问题。用C的同学特别要注意指针和STL的使用很多时候报错是因为越界访问或迭代器失效。用Python的同学要注意递归深度的问题DFS如果递归深度很深Python默认的递归限制会报错得手动调sys.setrecursionlimit。这些细节平时不注意笔试现场遇到了就很崩溃。5.2 从笔试到面试后续准备建议如果你笔试过了进了面试那恭喜你但也不要掉以轻心。猿辅导的面试一般也有算法题环节而且面试时的算法题往往比笔试的更注重思路交流和复杂度分析。面试官会让你先讲思路再写代码写完了还会问能不能优化如果数据量更大怎么办这些都是考察点。我的建议是笔试结束后趁热打铁把笔试中暴露出来的薄弱知识点补上。比如你发现自己在状态压缩DP上卡壳了那就把这一个专题刷透找出十道以上的同类题训练。不要一个知识点学一半就换下一个那样效果很差。另外算法岗位的面试除了手撕代码还会问机器学习相关的基础知识。比如决策树、随机森林、GBDT、XGBoost的原理和区别这些在笔试选择题里也会出现但面试时会问得更深。比如XGBoost和GBDT有什么核心区别如何防止过拟合特征工程有哪些常用方法。所以准备算法岗的面试算法和机器学习两条线都要抓。最后提一句猿辅导作为在线教育大厂业务场景跟教育数据、推荐系统、自然语言处理都有关系。如果你有相关项目经验写在简历上并提前准备好细节面试的时候会很有优势。5.3 个人心得刷题方法论才是核心竞争力吐槽完具体题目我还是想聊聊更深一点的东西。很多人觉得笔试就是刷题刷得越多越好这话对了一半。刷题数量确实重要但比数量更重要的是刷题的方法论。我见过一些同学刷了五六百道LeetCode但遇到新题还是不会做原因就是他只刷题不复盘没有从题目中抽象出共通的解题套路。我自己的刷题方法是这样每做完一道题不管做没做出来都会在笔记里记下这道题的关键词和核心思路。比如做了一道求最多可以安排多少场会议的题我就记下贪心区间调度按结束时间排序。下次遇到类似的题翻开笔记一看马上有思路。这样坚持三个月你会发现自己看到新题的第一反应不再是慌而是这道题跟某某题的思路有点像。从这个角度看猿辅导2020校招笔试算法岗一这张卷子其实就是一套不错的自我检测题。如果你能独立做完这套题并且总结出每道题背后的算法思想那你对算法和数据结构的理解就上了一个台阶。就算你最后没有投猿辅导这套题也值得拿来练手。