字节跳动2018校招算法笔试复盘：KMP变种、状态压缩DP与推箱子BFS全解析

字节跳动2018校招算法方向第四批的笔试复盘我压箱底拿出来了。说实话这批题放到现在来看依然很有嚼头里面涉及的KMP变种、状态压缩DP、推箱子BFS几乎年年都有同学在牛客上哀嚎。我当年也是踩着截止时间交的卷后来工作里做推荐系统排序模型回头看这些题才真正理解字节这批笔试为什么这么设计——它根本不是在考你会不会背模板而是在筛你有没有建模的脑子。这篇我不光把题目解法掰开揉碎还会把当时大家最容易踩的坑、以及现在准备算法岗笔试还能怎么用这批题一并讲清楚。1. 2018年这批算法笔试的整体气质不玩偏题怪题专考基本功的极限先给没经历过那个年代校招的同学一个背景。2018年是字节跳动扩张最凶的一年算法岗投递量巨大笔试题目是线上统一笔试牛客网平台编程题为主时间紧张。第四批这批题整体难度在中等偏上但不过分变态但有个很突出的特点几乎每一题都是经典问题的变体而且刻意提高了编码实现的复杂度。1.1 从热搜词反推当年的考察重心你看现在搜索字节跳动2018校招算法关联出来的热词排在前面的几乎都是KMP算法、数据结构排序算法、贪心算法、Dijkstra算法、深度/机器学习算法。这个关联不是没道理的。2018年第四批笔试里虽然没有直接让你默写KMP但有一道字符串相关的题目你要是不知道next数组的含义现场推导绝对会卡壳。同样排序算法、贪心、BFS这些不是作为独立题目出现而是作为解题的基础工具被反复使用。所以我的结论是字节这批笔试表面上考的是会不会做题实际上考的是常用算法武器库是否够用、够熟、能组合使用。你要是只会背快排代码不知道快排的分治思想怎么迁移到找第K大的数那在第四批里会很吃亏。1.2 第四批题目的整体难度分布根据当时牛客上评论区和我自己所在求职群的反馈第四批编程题大致可以分为三个梯度梯度题型特点代表题目方向预估AC率第一梯度签到题但隐藏边界条件模拟、简单数学、找规律30%-50%第二梯度中等题经典问题变体BFS/DFS、双指针、区间问题、字符串处理10%-20%第三梯度压轴题需要建模和优化状态压缩DP、复杂搜索、数学推导3%-8%AC率是我根据当时的讨论粗略估计的不一定精确但能说明一个现象第一梯度题很多人能AC但第二第三梯度会刷掉大部分人。字节的笔试不是让你拿满分的是一个相对排位赛你需要在有限时间内多拿分所以做题顺序策略很重要。这一点我在后面专门讲。2. 第四批编程题逐题拆解从读题到AC的完整思路下面我回忆一下第四批里比较有代表性的几道题。时间过去几年题目细节不可能一字不差但题型和核心考点是准确的。我会用回忆版题目描述 解题思路 代码实现 注意事项的结构来写尽量还原当时的思考和实战过程。2.1 机器人跳跃问题二分答案还是逆推两种解法的取舍题目回忆版机器人初始有能量E需要依次通过N个高度为H_i的建筑。如果H_i E则能量减少H_i - E如果H_i E则能量增加E - H_i。要求全程能量不为负求初始能量的最小值。这道题当时有两种主流做法二分答案和逆推。我两个都实现过简单对比一下。二分答案思路初始能量范围是[0, max(H)]因为能量超过最高建筑高度后只会增加不会减少所以上界设max(H)就够。然后对每个候选能量模拟一遍是否全程非负。复杂度O(N log maxH)N大概是10^5完全能过。关键点是模拟过程中能量可能溢出理论上能量可以一直增加如果不用long longC里int会爆。逆推思路从最后一栋建筑往前推。设到达第i栋建筑后能量为E_i那么有递推关系E_{i-1} ceil((E_i H_i) / 2)。为什么是这个式子因为从E_{i-1}到E_i的变换是E_i 2 * E_{i-1} - H_i两种情况统一写就是E_i 2E_{i-1} - H_i不信你分情况展开。反解就是E_{i-1} (E_i H_i) / 2向上取整保证整数。初始令E_N 0往前推到E_0就是答案。提示面试时如果被追问推荐优先讲逆推思路因为O(N)且不用二分更能体现对变换公式的理解。二分答案作为保底方案用于交叉验证。我当时实际写的是逆推因为早就知道这个结论。但如果你第一次见这题二分答案反而更容易想出来而且不容易错。建议先写二分AC之后再思考逆推的数学原理一举两得。2.2 字符串变换问题最小区间覆盖的贪心证明题目回忆版给定两个长度相同的字符串A和B你可以在A上进行操作每次选择A的一个子串将所有字符变成任意一个相同字符。问最少操作次数使得A变成B。这道题是典型的区间覆盖贪心。核心观察是如果A[i] B[i]那这一位根本不用管可以直接跳过。如果A[i] ! B[i]从i往后扫描连续一段都可以通过一次操作覆盖条件是它们变换后的目标字符必须相同——因为一次操作只能把区间内所有字符统一变成同一个字符所以只要B[j] ! B[i]且A[j] ! B[j]的那一位就必须另起一次操作。你可能会问如果A[j] B[j]但B[j]和B[i]相同能不能把j也划进这次操作不能。因为一次操作会把A[j]也变成B[i]但A[j]已经等于B[j]了如果强制覆盖反而会破坏已匹配的字符。所以贪心策略是从左到右扫描遇到第一个A[i] ! B[i]的位置就记一次操作然后一直往后跳直到遇到一个位置j满足A[j] B[j]或者B[j] ! B[i]才停下来。这个贪心的证明思路是每一次操作都不会让情况变差属于排序不等式直觉的变体面试时能口头解释清楚就行。我当时没有卡在这题上因为代码很短十分钟内搞定。2.3 推箱子问题BFS状态爆炸的经典应对题目回忆版一个N x M的地图上有墙、空地、箱子和目标点人每次可以上下左右移动箱子可以被推一格问最少推动次数把箱子推到目标点。推箱子是搜索题里的经典了。难点在于状态定义人的位置和箱子的位置共同构成一个状态。朴素BFS的状态量是(N*M)^2地图一大就炸。所以必须用状态压缩 预处理可达性来优化。我当时用的方法是以箱子位置为BFS主状态对每个箱子位置把人可能站的位置箱子四邻的非墙格作为附属状态。每次尝试把箱子从当前格推向相邻格时需要判断人能否从当前附属位置走到推箱子的人应处位置。这个能否走到可以用一次BFS预处理从附属位置出发避开箱子和墙看能否到达目标位置。复杂度上状态数变成O(NM4)远小于平方级。实现的时候要特别注意方向映射和坐标变换我当时用dx[4] {-1, 1, 0, 0}dy[4] {0, 0, -1, 1}然后循环4个方向分别判断箱子推到哪人应该站在哪。注意推箱子题里有个经典bug——人在绕路去推箱子的过程中不能穿过箱子。所以每次判断可达性时BFS的起点和终点都必须避开箱子当前所在格。我当时就在这个细节上debug了半小时。2.4 毕业旅行问题状态压缩DP的入门必练题目回忆版给定N个城市之间的路费矩阵从城市0出发每个城市恰好访问一次最后回到城市0求最小花费。N 20。这题就是旅行商问题TSP的裸题但N 20意味着暴力全排列是20!绝对超时必须用状态压缩DP。状态定义是dp[mask][i]已经访问过的城市集合是mask二进制表示当前所在城市是i的最小花费。转移就是枚举下一个未访问的城市j更新dp[mask | (1 j)][j] min(自身, dp[mask][i] cost[i][j])。初始化dp[1][0] 0答案是dp[(1 N) - 1][0]。这道题的坑在于矩阵不对称即cost[i][j] ! cost[j][i]最初我写的时候下意识用了对称矩阵的模板结果WA了三发。另外N20时mask最大是2^20 1048576dp数组开 int dp[1 20][20]大约80MB在C内存限制256MB下没问题但如果用Python就会MLE。所以建议对这道题用C写或者用一维滚动数组优化求值顺序。2.5 找出最接近的x个数字排序双指针的经典组合题目回忆版给定一个有序数组可能含重复元素以及一个目标值t和一个整数x找到数组中与t最接近的x个数字返回时需要保持原数组中的相对顺序若有多个答案返回下标较小的那组。这题在LeetCode上是找到 K 个最接近的元素但字节把返回原数组顺序和多个答案取下标小作为额外条件加上去。我当时直接用归并排序的思路写错了后来改成双指针先二分找到第一个大于等于t的位置然后左右指针分别向左向右扩展每次比较左指针指向元素与t的差和右指针指向元素与t的差哪边小就选哪边直到选满x个。注意这里有个陷阱比较差的时候要用绝对值且如果两边差值相等要优先取左边的也就是下标小的。我当时没认真审题把相等情况按右指针优先处理了结果只过了部分测试用例。复盘时发现这题可以说是送分题里最容易丢分的点——不是算法难而是边界条件多。3. 藏在第四批背后的高频算法考点从真题延伸到系统掌握如果你只刷了上面几道题就去笔试大概率还是不够。字节的笔试特点在于一道题里可能同时考察多个基础算法点比如KMP的next数组、排序的稳定性、贪心的反例识别等。这一节我把第四批背后牵出的高频考点系统梳理一遍这些也是当年搜索热词里反复出现的核心。3.1 KMP的next数组到底在算什么东西热搜词里KMP算法和模式串pabacaba的next数组被反复提到说明这是高频考点。很多人考试时能默写KMP代码但你要是问一句next[i]到底代表什么他可能会卡壳。next[i]的定义是模式串P[0..i]这个前缀子串中最长的相等真前缀和真后缀的长度。换句话说next[i] max{k | k i 且 P[0..k-1] P[i-k1..i]}。这个值的意义在于当主串匹配到第i位失败时模式串可以右移多少位而不用重新从0开始匹配。举热搜里的例子P abacaba手工求next数组。i0时next[0] -1或0视实现而定我用-1代表不存在。i1时前缀ab真前缀有a真后缀有b不相等next[1] 0。i2时前缀aba真前缀有a,ab真后缀有a,ba最长相等的是a长度为1next[2] 1。i3时前缀abac真前缀a,ab,aba真后缀c,ac,bac没有相等next[3] 0。i4时前缀abaca真前缀里a,ab,aba,abac真后缀里a,ca,aca,baca相等的是anext[4] 1。i5时前缀abacab真前缀a,ab,aba,abac,abaca真后缀b,ab,cab,acab,bacab最长相等abnext[5] 2。i6时前缀abacaba真前缀里最长相等是aba长度3next[6] 3。所以next数组是[-1, 0, 1, 0, 1, 2, 3]。提示KMP笔试里更常见的是让你求nextval数组优化版它对next数组做了修正避免P[next[i]] P[i]时的无效跳转。建议两个版本都手写一遍理解差异。3.2 排序算法不只是快排稳定性与场景匹配排序几乎是每场算法笔试的常客但字节的考察方式很刁钻。它不是问你快排的平均复杂度是多少而是给你一个场景问哪种排序最合适。比如数据基本有序时插入排序效率最高需要稳定排序且数据量较小用归并排序需要原地排序且不在乎稳定性用堆排序。2018年第四批有一道题具体我记不太清了属于排序的变体需要你在极大数组中找第K大的数。最优解不是排序而是基于快排分区的快速选择算法平均O(N)。我当时用的方法是随机选一个pivot把数组分成小于pivot和大于pivot两部分根据K落在哪一侧递归处理。注意如果要求不能改变原数组顺序可以用nth_elementC STL直接搞定但面试时最好把它和手写快排分区的思路讲清楚。3.3 贪心算法的反例识别为什么有时候贪心会错贪心是笔试里最容易掉坑的考点。因为贪心听起来简单每次取最优嘛但你得证明局部最优能推出全局最优。第四批里有一道区间调度类的问题具体题目我记不清了类似最少会议室安排很多人第一反应就是按结束时间排序然后贪心选择不冲突的区间——这在求最多可选区间数时是对的但如果题目问的是最少会议室数量贪心策略就不一样了得用扫描线算法把所有区间的开始和结束事件排序扫一遍维护当前活跃区间数取最大值。为什么按结束时间排序的贪心在这里错因为最少会议室问题是求重叠的最大深度不是选最多不重叠区间前者要全局统计重叠峰值的时刻后者才适合贪心。这个反例说明贪心之前必须把题目目标抽象清楚不能看到区间就往经典贪心上靠。3.4 动态规划的状态定义是灵魂第四批里DP题不少TSP、跳跃问题等DP的核心难点永远是怎么定义状态。很多同学DP学了很久做题还是蒙就是因为没有形成一套状态定义方法论。我的经验是先看数据范围N 20几乎就是状态压缩DP的信号N 10^5且要求最值大概率是线性DP或贪心如果状态有多个维度把维度列出来逐个看是否可压缩。比如TSP的状态dp[mask][i]为什么要加i因为已经访问了哪些城市这个信息不足以推出下一步的最小花费你还得知道当前人在哪才能计算从当前城市出发到下一个城市的代价。所以状态里的每个维度都不是随便加的都是为了满足无后效性和能转移。4. 扩展延伸粒子群、重采样、PID这些热词和算法笔试的关系热搜词里除了经典算法还有一些看起来和笔试无关的词比如粒子群算法原理、音频重采样算法、PID算法在CRPS PSU Power的作用、卡尔曼滤波算法。我猜这是系统根据算法这个关键词自动关联的不一定直接对应第四批题目。但作为博主我想借这个机会说清楚这些算法在算法岗笔试中到底会不会考以及备考时值不值得花时间。4.1 元启发式算法笔试很少直接考但面试可能聊粒子群算法PSO、模拟退火、遗传算法这类元启发式算法在2018年的校招笔试里几乎不会出编程题因为它们的核心是迭代寻优很难在线上笔试里设置确定性的测试用例。但它们可能会出现在面试的开放性题目里比如如果让你优化一个推荐系统的超参数你会用什么方法——这时候提到粒子群或贝叶斯优化会加分。我当时在准备面试时把粒子群算法的核心公式背了下来每个粒子有位置x和速度v迭代更新v wv c1r1*(pbest - x) c2r2(gbest - x)x x v。不需要会写完整代码但至少能解释清楚惯性权重w、个体认知c1、社会认知c2各自的含义和作用。4.2 重采样算法信号处理方向同学的建议音频重采样、图像锐化的拉普拉斯算法、sobel边缘检测这些属于信号处理和计算机视觉方向的内容。如果你投的是推荐/搜索/广告这类通用算法岗这些考的概率很低但如果你投的是音视频算法岗或CV算法岗重采样和图像算子就是核心考点。说白了笔试题目会根据你投递的部门有所调整第四批是算法方向通用卷不代表所有算法岗都考同一套题。4.3 PID算法和卡尔曼滤波自动化/机器人方向的大山PID和卡尔曼滤波在控制领域是核心但它们在通用算法笔试里出现的频率很低。不过如果你面的是字节的机器人、自动驾驶或硬件相关团队这些就是必考。我看到热搜词里PID算法在CRPS PSU Power的作用这个应该是特定硬件场景下的应用问题涉及电源管理芯片的闭环控制那就更偏嵌入式/硬件算法工程师了。这里想提醒跨方向投递的同学不要只看算法岗三个字就统一准备。先搞清楚你投的团队是做什么的再针对性地看笔试题目或者面试题。第四批这批题是通用算法能力测试但它不能覆盖所有方向。5. 考前最后的冲刺策略从真题到实战的时间分配与踩坑总结最后这部分我给正在准备算法岗笔试的同学讲讲更实际的东西怎么利用好字节跳动2018校招算法方向第四批这类的真题资源以及笔试现场的时间分配和常见坑。5.1 真题不是用来背的是用来建解题模型的很多人刷题的方式是把每道题的题号、题解、代码背下来刷了几百道遇到新题还是不会。我见过太多这样的简历了——项目写得花团锦簇笔试一上来自动机题都不会。你要做的是从第四批每道题里提炼出一个可迁移的模型跳跃问题 - 逆推/二分答案模型字符串变换 - 贪心区间覆盖模型推箱子 - BFS 状态压缩优化模型毕业旅行 - TSP状态压缩DP模型最接近的x个数字 - 双指针夹逼模型每个模型都要能回答三个问题用于什么场景状态/指针怎么定义时间复杂度多少这样遇到新题时你就能快速识别它属于哪个模型或者几个模型的组合。5.2 笔试现场的时间分配先保一题AC再谈满分线上笔试通常2小时4-5道编程题。我的策略是前30分钟快速把每道题都读一遍标注每道题的预估难度和思路。然后按易到难的顺序做题但优先级不只是难度还有AC的确定性——有的题你觉得简单但实现细节多容易踩坑就先跳过先做那种思路清晰、代码量少的题。举个例子2018第四批里字符串变换题代码量很小思路也直接属于优先做的推箱子题逻辑复杂、易错适合放在后面。当时很多同学在推箱子上耗了1小时结果其他题都没做这就是时间分配的大忌。5.3 我踩过的几个典型坑你们别再踩了第一不审清输入范围和输出格式。第四批有些题是多组输入有些是单组输出大小写、换行格式都有要求。我在最接近x个数字的那道题因为输出顺序没按原数组相对顺序WA了好几次。第二C基本类型溢出不查。跳跃问题的能量值如果上界设成int最大值模拟过程中翻倍容易溢出。第三忽略多解时的输出规则。很多题会说若有多个答案输出任意一个或输出下标最小的这个别看漏。第四轻视编译器和内存限制。状态压缩DP在Java里用int二维数组没问题但在Python里用list of list很容易MLE所以考前一定要看你常用语言的MLE/TLE限制必要时手写快读或改用C。5.4 笔试之后复盘比继续刷题更重要每次笔试完不管考得好不好我都会把每道题重新写一遍然后对照网上的题解或讨论找出自己想不到的优化思路。2018年第四批这套题我后来复盘时发现推箱子那题有一个反向BFS的写法可以预处理所有可能状态的最近距离但因为地图大小有限实际收益不大反而增加了实现复杂度。这种复盘时发现更好的解法的过程才是刷真题真正涨功力的时刻。字节2018年的题现在看确实有些年头了但字节笔试的风格一直有延续性——重基础、重建模、重代码细节。把这套题吃透再去做近几年其他大厂的算法真题你会发现很多套路是共通的。最后再给大家一个实用建议找一套近年的大厂笔试真题按真实考试时间去模拟一次中间不要查资料也不要用IDE的自动补全考场很多没有适应那种屏幕变灰、时间流逝、心跳加速的感觉。这东西练多了上考场和平时刷题完全是两种状态提前适应能帮你少丢不少冤枉分。