猿辅导2020校招笔试一这次题目整体给人的感觉是基础、扎实、不偏门。如果你平时刷题量不算特别大但把剑指Offer和LeetCode Hot 100认真过了一遍这套卷子做起来会比较顺手。如果你指望靠背题应付过去那可能会在几个细节题上翻车。我尽量把这次笔试涉及的核心题型、解题思路和容易踩的坑都捋一遍给后面准备在线教育公司技术岗笔试的同学做个参考。需要先说明一点校招笔试题目属于回忆整理具体细节可能与原卷有出入但考察方向和题型分布具备代表性。这篇文章不是单纯报答案而是把每类题背后的原理和刷题策略讲清楚。1. 笔试整体结构与考察方向拆解1.1 题型分布与时间分配猿辅导的校招笔试一整体分为两部分选择题 编程题。从岗位方向看算法岗和研发岗用的是同一套基础卷只是在编程题的难度和题量上略有区分。选择题大概在20道上下覆盖数据结构、操作系统、计算机网络、数据库和C/Java基础编程题一般是2到3道难度梯度明显第一道偏简单第二道中等第三道如果有的话基本是压轴题。时间上通常是90分钟到120分钟。这个时间规划非常关键。选择题不能纠结单题超过两分钟就必须先标记跳过编程题才是拉开差距的地方。我实际测试下来比较合理的时间分配是选择题控制在35分钟以内编程题留足50分钟以上最后10分钟检查边界和输入输出格式。1.2 考察重点与解题优先级这套卷子的核心考察点集中在四个方向数据结构基础链表操作、二叉树遍历、栈和队列的应用经典算法思想动态规划、贪心、排序与查找的变体计算机基础进程线程、内存管理、TCP/IP、数据库索引代码实现能力从题意到代码的落地速度、边界情况的处理如果按性价比排序编程题第一题和选择题中数据结构部分是最容易拿分的。动态规划题虽然出现频率高但往往是中等难度的那道套路比较固定。计算机网络和操作系统选择题属于记忆性内容考前突击完全来得及。这里有个实际经验值得说一下猿辅导这类在线教育公司的笔试算法题往往和业务场景有隐含联系。比如排课、调度、资源分配这类题目本质上对应公司的业务逻辑。做题时如果遇到类似描述不要慌剥掉业务外壳后内核还是经典算法。2. 核心算法题的思路拆解与避坑指南2.1 数组与字符串处理别小看基础操作第一道编程题通常是数组或字符串处理。我记得这轮笔试的编程第一题考的是字符串分割与统计要求按某种规则拆分字符串然后统计满足条件的子串数量。这类题目的难点不在算法本身而在边界条件的完整性。很多同学在本地IDE跑测试用例没问题一提交就报错多半是没考虑空字符串、单字符字符串、分隔符连续出现这些情况。写代码时的几个关键点处理前先判断输入是否为空避免空指针异常连续分隔符要明确处理策略是跳过还是产生空串统计条件用状态变量记录而不是每次都重新遍历以字符串分割为例一个比较稳妥的实现思路是遍历字符串用标志位记录当前是否处于一个有效段中遇到分隔符时判断标志位决定是否递增计数器。这样一次遍历就能完成时间复杂度O(n)空间复杂度O(1)。int countValidSegments(const string s, char delimiter) { int count 0; bool inSegment false; for (char c : s) { if (c delimiter) { inSegment false; } else { if (!inSegment) { count; inSegment true; } } } return count; }这类题目现场写的时候容易犯一个错误用split函数处理后习惯性忽略空串结果统计结果和预期不符。处理这类问题时建议不要依赖语言内置的split而是自己写扫描逻辑这样边界行为完全可控。2.2 链表类题目指针操作的细节决定成败链表题在笔试中出现频率很高这轮笔试的选择题里就有一道关于链表反转的变体。链表题考察的核心是指针操作的准确性和对引用传递的理解。链表反转最经典的实现是迭代法三指针prev、curr、next交替移动。这里有一个常见的坑如果直接修改指针方向后没有先保存下一个节点的指针链表就会断掉。我见过不少同学在写反转链表时漏掉保存next这一步导致死循环或者空指针。除了反转链表的快慢指针找中点、判断是否有环、合并两个有序链表也是高频考点。这些题型的套路比较固定建议考前集中刷一遍把模板代码背熟。关于链表题我的经验是先在纸上画出每一步指针的指向变化再写代码。链表题画图和不画图的正确率差距非常大尤其是指针操作超过两步的题目。笔试环境没有草稿纸的话多用注释模拟过程。2.3 动态规划识别状态定义是关键编程第二题通常是动态规划这套卷子考的是最长递增子序列的变体。不是标准的LIS而是带条件的递增子序列要求相邻元素之间的差值满足某个约束。动态规划题最核心的不是递推公式本身而是状态定义。状态定义对了递推公式自然就出来了状态定义错了后面全错。以最长递增子序列为例标准的状态定义是dp[i]表示以第i个元素结尾的最长递增子序列长度。转移方程是dp[i] max(dp[j] 1)其中j i且nums[j] nums[i]。如果加上相邻元素差值至少为k的约束转移条件变成nums[j] k nums[i]。这个变化很细微但如果在笔试时没有注意到这个约束条件直接套标准LIS模板测试用例大概率通不过。这里有一个实用技巧初始化dp数组时全部置为1因为单个元素本身就是一个长度为1的子序列。很多同学在初始化时只把dp[0]设为1导致后续比较出错。再看一个这轮笔试中类似“爬楼梯”的变体题。题目描述是有n级台阶每次可以跨1级或2级但连续跨2级的次数有限制。这种加了限制条件的题目简单的 dp[n] dp[n-1] dp[n-2] 就不够用了需要增加一维状态来记录限制条件的使用次数。def climbStairsWithLimit(n: int, max_double: int) - int: # dp[i][j][k] 表示到第i级台阶上一跨是单步还是双步已用双步次数j # 简化dp[i][j] 表示到第i级台阶最后一步用了j次双步 # 状态转移需要记录上一步类型这里省略简化为二维DP dp [[0] * (max_double 1) for _ in range(n 1)] dp[0][0] 1 for i in range(1, n 1): for j in range(max_double 1): # 跨1级 dp[i][j] dp[i-1][j] # 跨2级 if i 2 and j 0: dp[i][j] dp[i-2][j-1] return sum(dp[n])这类题在状态转移时要格外注意跨两级会消耗一次限制次数跨一级不消耗需要在循环中分别处理。2.4 二叉树层次遍历与递归的平衡二叉树题目中层次遍历BFS和递归遍历DFS是两大核心。猿辅导的笔试里经常考到二叉树的层次遍历变体比如之字形打印、每层最大值、每层平均值等。层次遍历的基础是队列。很多同学写BFS时习惯用两层循环外层处理层数内层处理当前层的节点。这里有个细节内层循环的次数要在处理前先记录为size而不是动态读取队列大小。因为处理过程中会不断往队列添加新节点动态读取会导致多处理下层的节点。vectorvectorint levelOrder(TreeNode* root) { vectorvectorint result; if (!root) return result; queueTreeNode* q; q.push(root); while (!q.empty()) { int size q.size(); vectorint level; for (int i 0; i size; i) { TreeNode* node q.front(); q.pop(); level.push_back(node-val); if (node-left) q.push(node-left); if (node-right) q.push(node-right); } result.push_back(level); } return result; }这个细节在笔试中特别容易踩坑因为本地测试的树规模小看不出问题一旦遇到大树节点就会被打乱到错误的层。判断二叉树是否平衡、求二叉树的直径这类递归题核心是后序遍历先处理左右子树再处理当前节点把子树的高度返回给上层。对于二叉树的递归问题我习惯先写出递归函数的语义它返回什么、做什么事情、终止条件是什么。三层语义清楚了代码基本不会出大错。3. 编程题的环境准备与代码实现细节3.1 ACM模式与核心代码模式的区别这里要特别强调一个很多人吃亏的点笔试环境用的是ACM模式还是核心代码模式。猿辅导的笔试系统用的是牛客网或赛码网部分岗位是ACM模式部分岗位是核心代码模式。ACM模式要求自己处理输入输出包括读取多行数据、按空格或换行分割、处理多组测试用例。核心代码模式则只需要写出函数实现。这两种模式考查的能力侧重点不同ACM模式更贴近工程实践中的IO处理核心代码模式更聚焦算法本身。如果笔试前没有搞清楚模式很容易出现题目看懂了解法也写出来了但卡在输入输出上导致0分。我建议在笔试前先做几道对应平台的模拟题熟悉输入输出模板。一个典型的ACM模式输入模板C#include iostream #include vector #include string #include sstream using namespace std; int main() { int n; cin n; // 先读入元素个数 vectorint nums(n); for (int i 0; i n; i) { cin nums[i]; } // 处理逻辑 cout result endl; return 0; }这里有一个细节如果第一行是测试用例组数T那要在循环中处理T组数据每组数据都独立读取和输出结果。很多同学忘记处理多组用例只写了单组逻辑提交后只能通过部分用例。3.2 常用数据结构的时间复杂度对照选择题里考时间复杂度的概率很高尤其是对比不同数据结构的操作效率。我把笔试中常用的数据结构操作复杂度整理成一个表格方便查阅数据结构查找插入删除适用场景数组O(n)O(n)O(n)随机访问频繁有序数组二分查找O(log n)O(n)O(n)查找多、增删少链表O(n)O(1)已知位置O(1)已知位置增删频繁、无随机访问栈O(n)遍历O(1)栈顶O(1)栈顶括号匹配、单调栈队列O(n)遍历O(1)队尾O(1)队头BFS、滑动窗口哈希表O(1)平均O(1)平均O(1)平均快速查找、去重二叉搜索树O(log n)平均O(log n)平均O(log n)平均有序数据维护堆O(1)最大/最小O(log n)O(log n)优先队列、TopK笔试中常考的一个点是哈希表在极端情况下的退化问题。理论上哈希表查找是O(1)但如果哈希函数设计不好冲突过多会退化为O(n)。这也是为什么C的unordered_map在极端情况下效率远低于预期。3.3 递归转迭代的常见套路笔试中有些题递归写法很简单但会要求用迭代实现。典型的例子就是二叉树的前序、中序、后序遍历。递归版本十行内搞定迭代版本需要显式维护栈。以前序遍历为例迭代实现的思路是用栈保存待访问的节点先访问根节点然后把右孩子压栈、左孩子压栈因为栈是后进先出左孩子后进栈会先被处理。vectorint preorderTraversal(TreeNode* root) { vectorint result; if (!root) return result; stackTreeNode* st; st.push(root); while (!st.empty()) { TreeNode* node st.top(); st.pop(); result.push_back(node-val); if (node-right) st.push(node-right); if (node-left) st.push(node-left); } return result; }递归转迭代的关键是把递归调用栈中的状态显式地维护在一个数据结构里。递归函数中每次递归调用对应一次压栈操作每次返回对应一次弹栈操作。理解了这一点任何递归都能转成迭代。我在笔试中遇到这类题的习惯做法是先用递归写一遍确认逻辑正确再改写成迭代。如果时间紧张递归写对了也能得分不需要勉强自己必须在第一时间写出迭代版本。4. 选择题中的计算机基础高频考点4.1 进程与线程区别与联系猿辅导笔试的选择题里操作系统相关题目基本绕不开进程和线程。高频考点包括进程是资源分配的最小单位线程是CPU调度的最小单位同一进程内的线程共享地址空间、文件描述符、信号处理器每个线程拥有独立的栈、寄存器上下文、程序计数器进程之间通信需要借助内核提供的IPC机制一个经典的判断题是“进程间通信比线程间通信更高效。”这个说法是错误的。线程间通信通过共享内存即可完成效率远高于进程间通信代价是同步控制更复杂需要锁、条件变量等。另一个常考的细节是协程与线程的区别。协程是用户态的轻量级线程切换不需要陷入内核因此更轻量。但协程是协作式调度需要主动让出执行权线程是抢占式调度由操作系统决定何时切换。4.2 网络协议TCP三次握手与拥塞控制网络方向的选择题TCP相关知识点几乎是必考的。三次握手、四次挥手、TIME_WAIT状态、拥塞控制算法这些是高频中的高频。关于TCP三次握手的常见选择第一次握手客户端发送SYN报文进入SYN_SENT状态第二次握手服务器收到SYN回复SYNACK进入SYN_RCVD状态第三次握手客户端收到SYNACK发送ACK双方进入ESTABLISHED状态这里容易混淆的是ACK和SYN标志位的组合。第二次握手的报文同时包含SYN和ACK标志很多同学误以为第二次握手只有ACK标志导致选项判断错误。拥塞控制部分常考拥塞窗口的变化规则阶段触发条件窗口变化慢启动连接建立初期每收到一个ACK窗口1指数增长拥塞避免窗口达到慢启动阈值ssthresh每经过一个RTT窗口1线性增长快速重传连续收到3个重复ACK立即重传缺失报文不等待超时快速恢复快速重传后将ssthresh减半窗口减半后执行拥塞避免有一种较常见的考察角度是区分“超时重传”和“快速重传”。超时重传意味着网络拥塞严重TCP会直接将ssthresh设为当前窗口的一半并将窗口降为1个MSS重新进入慢启动。而快速重传假设网络还不算太糟只做窗口减半处理。4.3 数据库索引失效与SQL优化数据库方向的选择题主要集中在索引和SQL优化。一个高频考点是索引失效的场景。常见导致索引失效的操作包括对索引列使用函数如 WHERE YEAR(create_time) 2020隐式类型转换如字符串列与数字比较时没有加引号使用LIKE通配符开头的模糊查询如 WHERE name LIKE %abc%OR条件中有一个非索引列复合索引未遵循最左前缀原则举个例子复合索引(a, b, c)如果查询条件是WHERE b 1 AND c 2由于没有用到最左列a这个索引不会生效。如果查询条件是WHERE a 1 AND c 2那么只有a会走索引c这列用不上。这里有一个容易被忽视的点数据库优化器不一定会用索引。如果优化器估算全表扫描比走索引更快比如表中大部分行都满足条件它会放弃索引。这就是为什么有时候明明建了索引EXPLAIN结果却显示typeALL。4.4 编程语言基础常见陷阱C和Java基础题也是选择题的重要组成部分。C常考的点包括虚函数表的机制虚函数调用是运行时多态非虚函数是编译期绑定构造函数和析构函数的调用顺序构造从基类到派生类析构从派生类到基类引用和指针的区别引用必须初始化、不能改变指向对象const的修饰位置const int* p 是指向常量的指针int* const p 是常量指针Java常考的点主要是equals和的区别比较引用地址equals默认也调用了但String类重写了equals比较内容HashMap的底层实现数组链表Java 8后链表长度超过阈值8会转为红黑树静态变量和实例变量的生命周期差异垃圾回收的可达性分析以Java的Integer缓存为例一个常见的坑Integer a 100; Integer b 100; 判断a b的结果是true因为Integer内部缓存了-128到127的值两个引用指向同一个缓存对象。但改成200后a b的结果是false因为超出缓存范围会各自new一个对象。这类题目考查的是对语言机制的理解深度不是背语法能解决的。5. 备赛路径总结与避坑经验5.1 如何规划校招笔试的刷题顺序很多同学准备校招时刷题没有规划从LeetCode第1题开始按顺序刷。这是一个效率很低的做法。合理的刷题顺序应该是按数据结构组织的第一阶段模拟题和字符串处理。这类题型简单用来热身和建立信心。常见题目包括字符串反转、回文判断、括号匹配、进制转换。第二阶段链表和二叉树。这两类是笔试中出现频率最高的数据结构题型。链表主要练反转、合并、找环二叉树主要练遍历、深度、路径和。第三阶段动态规划和贪心算法。这是拉分题需要刷一定量的题目才能形成条件反射。建议把LeetCode上的常见DP题型都过一遍背包问题、最长递增子序列、最长公共子序列、编辑距离、打家劫舍系列、股票买卖系列。第四阶段高频面试题总复习。把剑指Offer的题目按章节复习一遍同时整理自己的错题本。每个阶段刷题的过程中都要注意总结模板。动态规划题可以总结状态转移的常见模式链表题可以总结指针操作的固定写法。有了模板笔试时只要识别出题型就能快速套用。5.2 关于模拟笔试训练的三个关键建议我强烈建议在正式笔试前至少做三次完整的模拟笔试。模拟的目的不是做对题而是适应考试节奏和查漏补缺。第一条模拟时要严格限时。超过两道编程题的时间点就不能再继续直接看下一题。很多同学平时刷题没有时间压力一到笔试就手忙脚乱。第二条模拟后要认真复盘。复盘的重点不是看自己哪些题做错了而是分析为什么做错是思路不清晰、是代码写错了、还是题目理解偏差。错误类型不同改进策略完全不同。第三条模拟时尽量用笔试系统做别只用本地IDE。输入输出的处理模式差异比较大的时候直接用正式笔试环境跑一遍能避免考试当天踩输入输出格式的坑。5.3 常见失误速查表我把过往笔试中同学们最容易犯的错误整理成一张速查表笔试前看一遍能少踩很多坑错误类型典型场景避免方式边界条件遗漏字符串为空、数组长度为1写代码前先列出边界用例输入输出格式错误多组用例只处理了一组、输出多空格考前熟悉笔试平台模板动态规划状态定义错误状态维度不够漏掉限制条件先写清楚dp[i]表示什么链表指针丢失反转链表前没保存next节点画图模拟指针变化后再写代码二叉树层次遍历错误队列大小动态读取导致层间数据混叠遍历前先记录当前层节点数类型溢出int做加法乘法溢出大数场景直接用long long递归爆栈链表、二叉树深层递归考虑递归深度必要时改迭代我印象最深的是类型溢出这个坑。笔试环境一般不会提示溢出错误的结果看起来又特别合理很容易忽略。涉及累加、累乘的题目开始就定义为long long会比事后排查省很多时间。5.4 在线教育类公司笔试的差异化特点如果准备投猿辅导这类在线教育公司的技术岗可以额外了解一下它们的业务特点对笔试的影响。在线教育业务有两个核心场景大规模并发访问和个性化推荐。大促期间的直播课抢课场景、题库系统的海量检索场景都与后端性能优化直接相关。因此笔试中操作系统和网络部分的题目往往偏重高并发下的性能问题比如线程池设计、缓存策略、CDN原理。推荐系统和用户行为分析则与算法题有一定关联。像协同过滤、内容推荐的基础算法不一定在笔试中出现但了解这些业务背景有助于快速理解题目描述中的业务包装。还有一点教育类公司的产品往往有题库系统涉及大量数据的增删改查。因此数据库索引和慢查询优化的考题频率也不低。准备时可以把MySQL的索引原理、B树结构、执行计划分析这块多花些时间。我个人在实际操作中的体会是校招笔试拼的不是天赋而是准备的系统性。把基础数据结构刷穿、把高频考点背扎实、把容易踩的坑提前标记好通过率会大幅提升。猿辅导2020校招这套题给我的整体感受是没有偏题怪题每个考点都能在常规刷题范围内找到对应练习。如果你正在准备校招笔试按上面的策略走方向不会错。
猿辅导2020校招笔试真题解析：算法与计算机基础考点全梳理
猿辅导2020校招笔试一这次题目整体给人的感觉是基础、扎实、不偏门。如果你平时刷题量不算特别大但把剑指Offer和LeetCode Hot 100认真过了一遍这套卷子做起来会比较顺手。如果你指望靠背题应付过去那可能会在几个细节题上翻车。我尽量把这次笔试涉及的核心题型、解题思路和容易踩的坑都捋一遍给后面准备在线教育公司技术岗笔试的同学做个参考。需要先说明一点校招笔试题目属于回忆整理具体细节可能与原卷有出入但考察方向和题型分布具备代表性。这篇文章不是单纯报答案而是把每类题背后的原理和刷题策略讲清楚。1. 笔试整体结构与考察方向拆解1.1 题型分布与时间分配猿辅导的校招笔试一整体分为两部分选择题 编程题。从岗位方向看算法岗和研发岗用的是同一套基础卷只是在编程题的难度和题量上略有区分。选择题大概在20道上下覆盖数据结构、操作系统、计算机网络、数据库和C/Java基础编程题一般是2到3道难度梯度明显第一道偏简单第二道中等第三道如果有的话基本是压轴题。时间上通常是90分钟到120分钟。这个时间规划非常关键。选择题不能纠结单题超过两分钟就必须先标记跳过编程题才是拉开差距的地方。我实际测试下来比较合理的时间分配是选择题控制在35分钟以内编程题留足50分钟以上最后10分钟检查边界和输入输出格式。1.2 考察重点与解题优先级这套卷子的核心考察点集中在四个方向数据结构基础链表操作、二叉树遍历、栈和队列的应用经典算法思想动态规划、贪心、排序与查找的变体计算机基础进程线程、内存管理、TCP/IP、数据库索引代码实现能力从题意到代码的落地速度、边界情况的处理如果按性价比排序编程题第一题和选择题中数据结构部分是最容易拿分的。动态规划题虽然出现频率高但往往是中等难度的那道套路比较固定。计算机网络和操作系统选择题属于记忆性内容考前突击完全来得及。这里有个实际经验值得说一下猿辅导这类在线教育公司的笔试算法题往往和业务场景有隐含联系。比如排课、调度、资源分配这类题目本质上对应公司的业务逻辑。做题时如果遇到类似描述不要慌剥掉业务外壳后内核还是经典算法。2. 核心算法题的思路拆解与避坑指南2.1 数组与字符串处理别小看基础操作第一道编程题通常是数组或字符串处理。我记得这轮笔试的编程第一题考的是字符串分割与统计要求按某种规则拆分字符串然后统计满足条件的子串数量。这类题目的难点不在算法本身而在边界条件的完整性。很多同学在本地IDE跑测试用例没问题一提交就报错多半是没考虑空字符串、单字符字符串、分隔符连续出现这些情况。写代码时的几个关键点处理前先判断输入是否为空避免空指针异常连续分隔符要明确处理策略是跳过还是产生空串统计条件用状态变量记录而不是每次都重新遍历以字符串分割为例一个比较稳妥的实现思路是遍历字符串用标志位记录当前是否处于一个有效段中遇到分隔符时判断标志位决定是否递增计数器。这样一次遍历就能完成时间复杂度O(n)空间复杂度O(1)。int countValidSegments(const string s, char delimiter) { int count 0; bool inSegment false; for (char c : s) { if (c delimiter) { inSegment false; } else { if (!inSegment) { count; inSegment true; } } } return count; }这类题目现场写的时候容易犯一个错误用split函数处理后习惯性忽略空串结果统计结果和预期不符。处理这类问题时建议不要依赖语言内置的split而是自己写扫描逻辑这样边界行为完全可控。2.2 链表类题目指针操作的细节决定成败链表题在笔试中出现频率很高这轮笔试的选择题里就有一道关于链表反转的变体。链表题考察的核心是指针操作的准确性和对引用传递的理解。链表反转最经典的实现是迭代法三指针prev、curr、next交替移动。这里有一个常见的坑如果直接修改指针方向后没有先保存下一个节点的指针链表就会断掉。我见过不少同学在写反转链表时漏掉保存next这一步导致死循环或者空指针。除了反转链表的快慢指针找中点、判断是否有环、合并两个有序链表也是高频考点。这些题型的套路比较固定建议考前集中刷一遍把模板代码背熟。关于链表题我的经验是先在纸上画出每一步指针的指向变化再写代码。链表题画图和不画图的正确率差距非常大尤其是指针操作超过两步的题目。笔试环境没有草稿纸的话多用注释模拟过程。2.3 动态规划识别状态定义是关键编程第二题通常是动态规划这套卷子考的是最长递增子序列的变体。不是标准的LIS而是带条件的递增子序列要求相邻元素之间的差值满足某个约束。动态规划题最核心的不是递推公式本身而是状态定义。状态定义对了递推公式自然就出来了状态定义错了后面全错。以最长递增子序列为例标准的状态定义是dp[i]表示以第i个元素结尾的最长递增子序列长度。转移方程是dp[i] max(dp[j] 1)其中j i且nums[j] nums[i]。如果加上相邻元素差值至少为k的约束转移条件变成nums[j] k nums[i]。这个变化很细微但如果在笔试时没有注意到这个约束条件直接套标准LIS模板测试用例大概率通不过。这里有一个实用技巧初始化dp数组时全部置为1因为单个元素本身就是一个长度为1的子序列。很多同学在初始化时只把dp[0]设为1导致后续比较出错。再看一个这轮笔试中类似“爬楼梯”的变体题。题目描述是有n级台阶每次可以跨1级或2级但连续跨2级的次数有限制。这种加了限制条件的题目简单的 dp[n] dp[n-1] dp[n-2] 就不够用了需要增加一维状态来记录限制条件的使用次数。def climbStairsWithLimit(n: int, max_double: int) - int: # dp[i][j][k] 表示到第i级台阶上一跨是单步还是双步已用双步次数j # 简化dp[i][j] 表示到第i级台阶最后一步用了j次双步 # 状态转移需要记录上一步类型这里省略简化为二维DP dp [[0] * (max_double 1) for _ in range(n 1)] dp[0][0] 1 for i in range(1, n 1): for j in range(max_double 1): # 跨1级 dp[i][j] dp[i-1][j] # 跨2级 if i 2 and j 0: dp[i][j] dp[i-2][j-1] return sum(dp[n])这类题在状态转移时要格外注意跨两级会消耗一次限制次数跨一级不消耗需要在循环中分别处理。2.4 二叉树层次遍历与递归的平衡二叉树题目中层次遍历BFS和递归遍历DFS是两大核心。猿辅导的笔试里经常考到二叉树的层次遍历变体比如之字形打印、每层最大值、每层平均值等。层次遍历的基础是队列。很多同学写BFS时习惯用两层循环外层处理层数内层处理当前层的节点。这里有个细节内层循环的次数要在处理前先记录为size而不是动态读取队列大小。因为处理过程中会不断往队列添加新节点动态读取会导致多处理下层的节点。vectorvectorint levelOrder(TreeNode* root) { vectorvectorint result; if (!root) return result; queueTreeNode* q; q.push(root); while (!q.empty()) { int size q.size(); vectorint level; for (int i 0; i size; i) { TreeNode* node q.front(); q.pop(); level.push_back(node-val); if (node-left) q.push(node-left); if (node-right) q.push(node-right); } result.push_back(level); } return result; }这个细节在笔试中特别容易踩坑因为本地测试的树规模小看不出问题一旦遇到大树节点就会被打乱到错误的层。判断二叉树是否平衡、求二叉树的直径这类递归题核心是后序遍历先处理左右子树再处理当前节点把子树的高度返回给上层。对于二叉树的递归问题我习惯先写出递归函数的语义它返回什么、做什么事情、终止条件是什么。三层语义清楚了代码基本不会出大错。3. 编程题的环境准备与代码实现细节3.1 ACM模式与核心代码模式的区别这里要特别强调一个很多人吃亏的点笔试环境用的是ACM模式还是核心代码模式。猿辅导的笔试系统用的是牛客网或赛码网部分岗位是ACM模式部分岗位是核心代码模式。ACM模式要求自己处理输入输出包括读取多行数据、按空格或换行分割、处理多组测试用例。核心代码模式则只需要写出函数实现。这两种模式考查的能力侧重点不同ACM模式更贴近工程实践中的IO处理核心代码模式更聚焦算法本身。如果笔试前没有搞清楚模式很容易出现题目看懂了解法也写出来了但卡在输入输出上导致0分。我建议在笔试前先做几道对应平台的模拟题熟悉输入输出模板。一个典型的ACM模式输入模板C#include iostream #include vector #include string #include sstream using namespace std; int main() { int n; cin n; // 先读入元素个数 vectorint nums(n); for (int i 0; i n; i) { cin nums[i]; } // 处理逻辑 cout result endl; return 0; }这里有一个细节如果第一行是测试用例组数T那要在循环中处理T组数据每组数据都独立读取和输出结果。很多同学忘记处理多组用例只写了单组逻辑提交后只能通过部分用例。3.2 常用数据结构的时间复杂度对照选择题里考时间复杂度的概率很高尤其是对比不同数据结构的操作效率。我把笔试中常用的数据结构操作复杂度整理成一个表格方便查阅数据结构查找插入删除适用场景数组O(n)O(n)O(n)随机访问频繁有序数组二分查找O(log n)O(n)O(n)查找多、增删少链表O(n)O(1)已知位置O(1)已知位置增删频繁、无随机访问栈O(n)遍历O(1)栈顶O(1)栈顶括号匹配、单调栈队列O(n)遍历O(1)队尾O(1)队头BFS、滑动窗口哈希表O(1)平均O(1)平均O(1)平均快速查找、去重二叉搜索树O(log n)平均O(log n)平均O(log n)平均有序数据维护堆O(1)最大/最小O(log n)O(log n)优先队列、TopK笔试中常考的一个点是哈希表在极端情况下的退化问题。理论上哈希表查找是O(1)但如果哈希函数设计不好冲突过多会退化为O(n)。这也是为什么C的unordered_map在极端情况下效率远低于预期。3.3 递归转迭代的常见套路笔试中有些题递归写法很简单但会要求用迭代实现。典型的例子就是二叉树的前序、中序、后序遍历。递归版本十行内搞定迭代版本需要显式维护栈。以前序遍历为例迭代实现的思路是用栈保存待访问的节点先访问根节点然后把右孩子压栈、左孩子压栈因为栈是后进先出左孩子后进栈会先被处理。vectorint preorderTraversal(TreeNode* root) { vectorint result; if (!root) return result; stackTreeNode* st; st.push(root); while (!st.empty()) { TreeNode* node st.top(); st.pop(); result.push_back(node-val); if (node-right) st.push(node-right); if (node-left) st.push(node-left); } return result; }递归转迭代的关键是把递归调用栈中的状态显式地维护在一个数据结构里。递归函数中每次递归调用对应一次压栈操作每次返回对应一次弹栈操作。理解了这一点任何递归都能转成迭代。我在笔试中遇到这类题的习惯做法是先用递归写一遍确认逻辑正确再改写成迭代。如果时间紧张递归写对了也能得分不需要勉强自己必须在第一时间写出迭代版本。4. 选择题中的计算机基础高频考点4.1 进程与线程区别与联系猿辅导笔试的选择题里操作系统相关题目基本绕不开进程和线程。高频考点包括进程是资源分配的最小单位线程是CPU调度的最小单位同一进程内的线程共享地址空间、文件描述符、信号处理器每个线程拥有独立的栈、寄存器上下文、程序计数器进程之间通信需要借助内核提供的IPC机制一个经典的判断题是“进程间通信比线程间通信更高效。”这个说法是错误的。线程间通信通过共享内存即可完成效率远高于进程间通信代价是同步控制更复杂需要锁、条件变量等。另一个常考的细节是协程与线程的区别。协程是用户态的轻量级线程切换不需要陷入内核因此更轻量。但协程是协作式调度需要主动让出执行权线程是抢占式调度由操作系统决定何时切换。4.2 网络协议TCP三次握手与拥塞控制网络方向的选择题TCP相关知识点几乎是必考的。三次握手、四次挥手、TIME_WAIT状态、拥塞控制算法这些是高频中的高频。关于TCP三次握手的常见选择第一次握手客户端发送SYN报文进入SYN_SENT状态第二次握手服务器收到SYN回复SYNACK进入SYN_RCVD状态第三次握手客户端收到SYNACK发送ACK双方进入ESTABLISHED状态这里容易混淆的是ACK和SYN标志位的组合。第二次握手的报文同时包含SYN和ACK标志很多同学误以为第二次握手只有ACK标志导致选项判断错误。拥塞控制部分常考拥塞窗口的变化规则阶段触发条件窗口变化慢启动连接建立初期每收到一个ACK窗口1指数增长拥塞避免窗口达到慢启动阈值ssthresh每经过一个RTT窗口1线性增长快速重传连续收到3个重复ACK立即重传缺失报文不等待超时快速恢复快速重传后将ssthresh减半窗口减半后执行拥塞避免有一种较常见的考察角度是区分“超时重传”和“快速重传”。超时重传意味着网络拥塞严重TCP会直接将ssthresh设为当前窗口的一半并将窗口降为1个MSS重新进入慢启动。而快速重传假设网络还不算太糟只做窗口减半处理。4.3 数据库索引失效与SQL优化数据库方向的选择题主要集中在索引和SQL优化。一个高频考点是索引失效的场景。常见导致索引失效的操作包括对索引列使用函数如 WHERE YEAR(create_time) 2020隐式类型转换如字符串列与数字比较时没有加引号使用LIKE通配符开头的模糊查询如 WHERE name LIKE %abc%OR条件中有一个非索引列复合索引未遵循最左前缀原则举个例子复合索引(a, b, c)如果查询条件是WHERE b 1 AND c 2由于没有用到最左列a这个索引不会生效。如果查询条件是WHERE a 1 AND c 2那么只有a会走索引c这列用不上。这里有一个容易被忽视的点数据库优化器不一定会用索引。如果优化器估算全表扫描比走索引更快比如表中大部分行都满足条件它会放弃索引。这就是为什么有时候明明建了索引EXPLAIN结果却显示typeALL。4.4 编程语言基础常见陷阱C和Java基础题也是选择题的重要组成部分。C常考的点包括虚函数表的机制虚函数调用是运行时多态非虚函数是编译期绑定构造函数和析构函数的调用顺序构造从基类到派生类析构从派生类到基类引用和指针的区别引用必须初始化、不能改变指向对象const的修饰位置const int* p 是指向常量的指针int* const p 是常量指针Java常考的点主要是equals和的区别比较引用地址equals默认也调用了但String类重写了equals比较内容HashMap的底层实现数组链表Java 8后链表长度超过阈值8会转为红黑树静态变量和实例变量的生命周期差异垃圾回收的可达性分析以Java的Integer缓存为例一个常见的坑Integer a 100; Integer b 100; 判断a b的结果是true因为Integer内部缓存了-128到127的值两个引用指向同一个缓存对象。但改成200后a b的结果是false因为超出缓存范围会各自new一个对象。这类题目考查的是对语言机制的理解深度不是背语法能解决的。5. 备赛路径总结与避坑经验5.1 如何规划校招笔试的刷题顺序很多同学准备校招时刷题没有规划从LeetCode第1题开始按顺序刷。这是一个效率很低的做法。合理的刷题顺序应该是按数据结构组织的第一阶段模拟题和字符串处理。这类题型简单用来热身和建立信心。常见题目包括字符串反转、回文判断、括号匹配、进制转换。第二阶段链表和二叉树。这两类是笔试中出现频率最高的数据结构题型。链表主要练反转、合并、找环二叉树主要练遍历、深度、路径和。第三阶段动态规划和贪心算法。这是拉分题需要刷一定量的题目才能形成条件反射。建议把LeetCode上的常见DP题型都过一遍背包问题、最长递增子序列、最长公共子序列、编辑距离、打家劫舍系列、股票买卖系列。第四阶段高频面试题总复习。把剑指Offer的题目按章节复习一遍同时整理自己的错题本。每个阶段刷题的过程中都要注意总结模板。动态规划题可以总结状态转移的常见模式链表题可以总结指针操作的固定写法。有了模板笔试时只要识别出题型就能快速套用。5.2 关于模拟笔试训练的三个关键建议我强烈建议在正式笔试前至少做三次完整的模拟笔试。模拟的目的不是做对题而是适应考试节奏和查漏补缺。第一条模拟时要严格限时。超过两道编程题的时间点就不能再继续直接看下一题。很多同学平时刷题没有时间压力一到笔试就手忙脚乱。第二条模拟后要认真复盘。复盘的重点不是看自己哪些题做错了而是分析为什么做错是思路不清晰、是代码写错了、还是题目理解偏差。错误类型不同改进策略完全不同。第三条模拟时尽量用笔试系统做别只用本地IDE。输入输出的处理模式差异比较大的时候直接用正式笔试环境跑一遍能避免考试当天踩输入输出格式的坑。5.3 常见失误速查表我把过往笔试中同学们最容易犯的错误整理成一张速查表笔试前看一遍能少踩很多坑错误类型典型场景避免方式边界条件遗漏字符串为空、数组长度为1写代码前先列出边界用例输入输出格式错误多组用例只处理了一组、输出多空格考前熟悉笔试平台模板动态规划状态定义错误状态维度不够漏掉限制条件先写清楚dp[i]表示什么链表指针丢失反转链表前没保存next节点画图模拟指针变化后再写代码二叉树层次遍历错误队列大小动态读取导致层间数据混叠遍历前先记录当前层节点数类型溢出int做加法乘法溢出大数场景直接用long long递归爆栈链表、二叉树深层递归考虑递归深度必要时改迭代我印象最深的是类型溢出这个坑。笔试环境一般不会提示溢出错误的结果看起来又特别合理很容易忽略。涉及累加、累乘的题目开始就定义为long long会比事后排查省很多时间。5.4 在线教育类公司笔试的差异化特点如果准备投猿辅导这类在线教育公司的技术岗可以额外了解一下它们的业务特点对笔试的影响。在线教育业务有两个核心场景大规模并发访问和个性化推荐。大促期间的直播课抢课场景、题库系统的海量检索场景都与后端性能优化直接相关。因此笔试中操作系统和网络部分的题目往往偏重高并发下的性能问题比如线程池设计、缓存策略、CDN原理。推荐系统和用户行为分析则与算法题有一定关联。像协同过滤、内容推荐的基础算法不一定在笔试中出现但了解这些业务背景有助于快速理解题目描述中的业务包装。还有一点教育类公司的产品往往有题库系统涉及大量数据的增删改查。因此数据库索引和慢查询优化的考题频率也不低。准备时可以把MySQL的索引原理、B树结构、执行计划分析这块多花些时间。我个人在实际操作中的体会是校招笔试拼的不是天赋而是准备的系统性。把基础数据结构刷穿、把高频考点背扎实、把容易踩的坑提前标记好通过率会大幅提升。猿辅导2020校招这套题给我的整体感受是没有偏题怪题每个考点都能在常规刷题范围内找到对应练习。如果你正在准备校招笔试按上面的策略走方向不会错。
)
