每年这个时间点都会有一批准备冲大厂算法岗的同学翻出往年的校招真题来练手。字节跳动2018校招算法方向第一批这套题在圈子里流传度相当高我到现在还时不时看到有人把它挂在博客里当作“入职必刷清单”。原因不难理解那一年是字节算法岗大规模扩招的年份笔试题目既保留了传统大厂对数据结构与算法基本功的考察又增加了不少贴近工程实际的业务场景题整体区分度做得很好。我帮好几个学弟学妹复盘过这套题自己也重新刷过两遍越刷越觉得它对“如何准备算法岗笔试”这件事有很强的指导意义。这篇文章不打算把每道题的标准答案抄一遍而是想从“这套题到底考什么、为什么要这样考、换了一道类似题该怎么下手”的角度做一次系统拆解。无论你是刚开始刷题的大三学生还是打算跳槽的社招选手这套题都值得当成一面镜子照一照自己的算法功底和临场解题能力。1. 2018这批试题的整体画像题量、难度与知识点分布先说一个很多人容易忽略的事实校招笔试的“题目难度”从来不是孤立的它和考试时长、题量、允许使用的编程语言、乃至你的面试轮次安排都是强相关的。2018年字节跳动算法方向第一批的笔试大概在两个小时左右题量控制在四到五道编程大题另外可能穿插少量客观题或简答题。这个结构放到今天看依然是大厂笔试的主流形态。从知识点覆盖来看这批题有几个非常明显的集中区。字符串处理是绝对的主场KMP算法、next数组这种经典考点几乎是必现的排序与贪心思想出现的频率也很高而且往往不是让你裸写一个快排而是把排序当作一个前置步骤后面再接二分查找、双指针或者区间合并之类的操作数据结构的考察偏向堆、并查集、哈希表这些在工程里真正高频使用的结构而不是红黑树手写、B树细节那种偏理论的内容动态规划和搜索DFS/BFS必然会有一道压轴题用来拉开区分度。为什么是这个分布我的判断是2018年字节的算法岗已经开始承担大量推荐、搜索、NLP相关的业务这批题目的出题人显然希望筛选出两类人一类是基本功扎实、能快速写出无bug代码的人另一类是看到新题能迅速抽象出数学模型、找到优化方向的人。所以你会发现这套题几乎没有那种“背了模板就会做”的套路题每道题都在逼迫你现场做问题转换。这点很重要后面每一章的拆解都会围绕“问题转换”这个核心能力展开。另外提一句有一个热词是“粒子群算法原理”可能有同学以为2018年校招会考群体智能或者元启发式算法。实际上从我了解的信息来看这批笔试题并没有涉及粒子群、模拟退火这类内容它们更多出现在研究生课程或者特定方向的面试深挖环节而不是校招笔试的通用考察范围。笔试阶段考察的还是计算机通用的算法功底这一点大家不要被网上零散的热搜词带偏。2. 字符串处理大题从KMP的next数组到业务场景的匹配需求2.1 KMP算法与next数组的推导逻辑既然热词里反复出现“在KMP算法中对于模式串pabacaba其next数组定义为什么”那咱们就从这个最经典的例子说起。KMP的核心思想是当主串与模式串在某一位失配时不要像暴力匹配那样只把模式串向后挪一位而是利用已经匹配成功的部分前缀信息直接把模式串跳到下一个可能匹配的位置。这里最关键的就是next数组。next[i]的定义是模式串前i个字符组成的子串中最长相等前缀和后缀的长度。注意这个长度不能等于i本身因为如果相等就表示整个子串是自己的前缀后缀没有意义。举个例子模式串abacaba当i1时子串是a最长相等前后缀长度为0。当i2时子串是ab前缀有a后缀有b不相等为0。当i3时子串是aba前缀a和后缀a相等长度为1。当i4时子串是abac前缀a与后缀c不相等前缀ab与后缀ac不相等为0。当i5时子串是abaca前缀a和后缀a相等长度为1。当i6时子串是abacab前缀ab和后缀ab相等长度为2。当i7时子串是abacaba前缀aba和后缀aba相等长度为3同时更短的前缀ab和后缀ba不相等a和后缀a相等但长度为1最长的是3。所以next数组是[0,0,1,0,1,2,3]这在网上有很多版本有的地方用next[0]-1有的用next[1]0作为边界实现上有差异但原理完全一致。我建议准备面试的同学不要只背这个数组要会现场推一遍。因为面试官很可能会追问“当模式串在第7位失配时模式串应该向右移动几位”答案是移动i-next[i]7-34位。这个计算过程本身就考察了你是否真正理解next数组的含义而不是只会抄模板。2.2 笔试里怎么考从匹配到“字符串转换的最小代价”2018年这批题里KMP并不会以裸题形式出现。更常见的是把字符串匹配的思想包装成一个业务场景比如“在长文本中找出所有出现某个敏感词的起始位置”或者“统计一个字符串在另一个字符串中出现了多少次”。这种题本质上就是KMP的变体但如果你看不穿这层包装就会以为是一道新题浪费大量时间思考。还有一种考法值得注意字符串转换类动态规划。比如两个字符串之间的编辑距离或者“将一个字符串变成另一个字符串的最小操作次数”。这类题需要你定义dp[i][j]表示字符串A的前i个字符转换为字符串B的前j个字符的最小代价然后按最后一步操作是插入、删除还是替换来写状态转移。这类题不仅考算法还考你对“编辑距离”这个经典模型的拓展能力——比如每次替换的代价可能不是1而是由字符对决定或者允许整个子串被一次性删除。我的建议是刷字符串题时不要止步于“AC了就可以”而是要把每道题归类到“这个题的底层模型是什么”。KMP是一个模型编辑距离是一个模型马拉车算法Manacher是一个模型后缀数组/后缀自动机是一个模型。笔试题目可能千变万化但底层模型逃不出这几个。你能把题目迅速映射到模型就已经赢了一半。3. 排序与贪心为什么说这是性价比最高的拿分区域3.1 排序题的进阶考法结构体排序与多关键字比较大部分同学对排序的理解停留在“会写快排、归并、堆排”的层面。但校招笔试里直接让你写排序算法的题目已经非常少了取而代之的是“你需要对一个结构体数组排序然后做后续处理”这类组合题型。比如有若干任务每个任务有开始时间、结束时间和收益你需要按某个规则排序之后再用贪心或DP去求解。这种题目里排序只是第一步但往往是最关键的一步——排序的关键字选错了后面的所有步骤全部白费。2018年这批题里有一道让我印象深刻的区间类问题大意是给定若干区间要求选出尽量多的互不重叠区间。这个问题的经典解法就是“按区间右端点排序然后从左到右贪心选择”。右端点越小的区间越应该优先选择因为它给后面的区间留下的空间更大。如果按左端点排序贪心就会出问题。这个反直觉的点恰恰是出题人想考察的。所以我在辅导学弟学妹时反复强调排序题不要只看“会不会写compare函数”要思考“为什么这个关键字的顺序是对的”。如果你能从“贪心选择后不会产生更优解”的角度解释清楚面试官对你的评价会明显上一个台阶。3.2 贪心的正确性证明不会证明的贪心就是赌博最常见的贪心错误是“凭感觉选择当前看起来最优的方案”没有验证局部最优是否真的能推出全局最优。笔试里贪心题翻车九成都是这个原因。正规的做法是两步。第一步设计一个候选贪心策略用中文描述清楚“每一步我选择的是哪个对象依据是什么”。第二步用反证法或者交换论证法证明这个策略的正确性。所谓交换论证就是假设存在一个最优解和我们贪心得到的解不同然后证明我们可以在不破坏最优性的前提下把最优解逐步“交换”成贪心解从而得出贪心解也是最优解。这个方法听起来抽象但练过五道以上经典贪心题之后就会形成肌肉记忆。从复习策略来说我强烈建议把“区间相关问题”当成贪心训练的主线。因为它的变体足够多选最多不重叠区间、用最少的箭引爆所有气球LeetCode 452、合并区间LeetCode 56、插入区间LeetCode 57、会议室IILeetCode 253。这几道题做完并弄清楚每条策略背后的交换论证笔试里的贪心题基本就稳了。4. 数据结构设计题手写优先队列、并查集与哈希表的边界4.1 优先队列Top-K问题的标准答案大数据场景下的Top-K问题是字节尤其喜欢考的方向因为推荐系统、搜索排序里到处都是海量数据取Top-K。最标准的解法是维护一个容量为K的小根堆堆顶是当前最小的元素。遍历所有数据当一个新元素比堆顶大时就把堆顶弹出把新元素压入遍历结束后堆里的K个元素就是全体数据中最大的K个。时间复杂度是O(N log K)空间复杂度O(K)。当K远小于N时这个方案是碾压全排序方案的。很多同学会问为什么不用大根堆因为大根堆的堆顶是最大的元素新元素比堆顶小时无法判断是否应该进入堆新元素比堆顶大时堆顶弹出了但新元素可能不是最大的后续还需要继续调整逻辑上很别扭。小根堆的设计根因就是“让堆顶成为进入堆的门槛”这是Top-K问题在工程上的最优解。2018年笔试里类似考察是少不了的尤其是和“数组第K大”“前K个高频元素”结合。如果你对堆不够熟一定要专门练一下priority_queueC或者heapqPython的用法并且要会手写堆的下沉和上浮操作因为有些面试官会让你现场实现二叉堆的插入和删除。4.2 并查集连通性问题与最小生成树的桥梁并查集在笔试中出现频率很高却经常被低估。它的核心操作就是两个find找根和union合并。带路径压缩的find可以在近乎O(1)的均摊复杂度内完成查询这个优化是必须写的不然在大数据量下很容易超时。笔试里并查集最经典的包装是“判断两个节点是否连通”“求连通分量数量”以及“在Kruskal最小生成树算法中维护连通性”。Kruskal算法本身就是“边按权值排序 并查集维护连通性”的组合这正好呼应了上一章说的“排序是前置步骤”。如果你只会写裸并查集不做路径压缩也不按秩合并遇到N10^5级别的数据就会超时挂掉非常可惜。我个人建议准备并查集时把三个版本的模板都写一遍递归find、迭代find、带按秩合并的union。这样才能在笔试的紧张状态下写出无bug的代码。4.3 哈希表的设计从“键值对”到“一致性哈希”大部分同学对哈希表的理解就是“python里的dict、C里的unordered_map”。笔试中直接考哈希表底层原理的题目不太多但有一个方向值得注意——一致性哈希。它在分布式缓存、负载均衡里应用很广如果笔试是算法方向且岗位偏后端基础架构出题人有可能把它包装成一个场景题有N台缓存服务器如何设计一个哈希方案使得增删服务器时受影响的缓存尽可能少。这种题不需要你完整实现一致性哈希的每个细节但你要理解“虚拟节点”和“哈希环”的基本思想把服务器和缓存key都映射到一个哈希环上每个key顺时针找到第一个服务器节点。当一台服务器宕机时只有它逆时针方向到上一台服务器之间的key会受影响而不是整个哈希表全部失效。这个思路本身就是“局部性替换全局性”的典型也是大厂考察候选人工程敏感度的一个切口。5. 动态规划与搜索压轴题背后的状态设计思维5.1 动态规划的四个步骤状态定义、转移方程、初始化、最终答案笔试里的动态规划题目一般不会直接告诉你“这是一道DP题”而是给你一个看起来很复杂的操作序列或资源分配场景。这时候最重要的不是急着写代码而是先把状态定义想清楚。我习惯按四个步骤来拆解状态定义dp[i][j]表示什么维度的选择一定要覆盖“决策所需的所有关键变量”但也不能冗余。转移方程最后一步操作是什么把这个操作枚举出来dp就被拆解成更小的子问题。边界初始化dp[0][0]等于什么什么地方需要设INF或-INF最终答案返回哪个状态是dp[n][m]还是max(dp[n][j])这三个步骤配套一个例子来理解0-1背包问题。dp[i][j]表示前i个物品放入容量为j的背包能获得的最大价值。转移时考虑第i个物品放还是不放不放就是dp[i-1][j]放就是dp[i-1][j-w[i]] v[i]。初始化dp[0][j]0。最终答案就是dp[n][capacity]。这个框架看起来很朴素但当你遇到“三维DP”“状态压缩DP”“区间DP”的时候框架依然适用变的只是维度设计更精巧。5.2 记忆化搜索DFS与DP的中间地带很多时候笔试现场想不清楚递推顺序用记忆化搜索反而更不容易出错。记忆化搜索的本质是用递归的方式写DP每次计算一个状态时先查表如果已经算过就直接返回否则递归计算后再存入表中。它写起来更符合直觉因为你是从“我站在某个状态下一步可以做什么”的角度思考而不是反过来从“我要从哪里来”的角度思考。以“矩阵中的最长递增路径”为例如果直接DP需要按数值排序后从小到大推进不太好想但如果你用记忆化搜索定义dfs(i,j)为从(i,j)出发能走出的最长递增路径长度每次尝试四个方向代码非常清晰时间复杂度同样是O(N*M)。2018年这批题的搜索题里记忆化搜索是很多高分选手的破题利器。5.3 状态压缩小数据量高性能的经典套路有另一类题目N的范围很小比如N≤16但每个元素都有“选或不选”的决策暴力枚举2^N种状态会超时。这时候就需要状态压缩DP用一个整数的二进制位表示一个集合的状态比如mask的第i位是1表示第i个物品已被选中。dp[mask]表示当前状态为mask时的最优值。转移时枚举mask中还没有被选的元素把它加入集合得到新的mask。经典的“旅行商问题TSP”“分配工作问题”“排列计数问题”都可以用状态压缩DP解决。笔试里这类题目的识别特征非常明显N小但状态空间巨大。如果你能在看到N≤16的瞬间想起状态压缩DP就相当于拿到了一道送分题。但前提是你对位运算足够熟——判断某一位是否是1用mask (1i)把某一位改成1用mask | (1i)把某一位改成0用mask ~(1i)。这些操作要练成条件反射。6. 编码细节与语言选择的实战策略如何在两个小时内不丢冤枉分6.1 用你最熟的语言不要为“炫技”临时切换笔试现场最忌讳的事情就是临时换语言。我见过C选手看到Python写起来快就改用Python结果对heapq、lambda排序这些细节不熟反而浪费了更长时间。反过来Python选手临时改用C也会被指针和内存管理拖累。2018年这批题的范围用C、Java、Python三种语言都能完成完全没有什么是“只会C才做得出来”的题。所以我的建议是挑一门你刷题时用得最多的语言笔试时坚决不换。如果你在LeetCode上一直用Python那就Python打到底如果你平时用C那就C打到底。“顺手”是考场上最大的优势。6.2 注意输入输出格式与大数陷阱老生常谈但每年都有人栽跟头readme里写了“多组测试数据”你只处理了一组题目说答案是10^9级别的整数你用int存结果溢出变成了负数输出要求“空格分隔末尾不能有多余空格”你多打了一个空格被判Presentation Error。这些都是零技术含量但致命的错误。我自己的习惯是笔试拿到题目先看输入输出描述的细节特别是数据范围那一栏。看到10^18直接上long long看到浮点数比较立一个EPS1e-9而不是用。时间不够时正确写出一个O(N^2)的边界情况代码远比“思路很高级但没写对输入输出”的代码拿分高。6.3 调试技巧小样例、大样例与assert代码写完不要急着交先做三件事。第一用题目给的样例跑一遍确认输出和样例一致第二构造一个极端的小输入比如N1、数组里全是相同元素、区间完全重叠看程序能不能处理边界第三如果时间充裕造一个大数据量的随机输入和自己写的暴力解法对拍输出不一致就说明某个细节错了。这三步说白了就是工程里的单元测试和回归测试思路。我用这个习惯在笔试里避免了至少两次“自以为AC但实际逻辑错误”的翻车。7. 时间分配与答题顺序复盘后的最优策略7.1 先扫一遍全部题目把题分成“秒杀题”“熟悉题”“陌生题”拿到试卷的10分钟什么代码都别写先把所有题目从头到尾读一遍。用一句话概括每道题的要求然后给它们打标签这道题我一眼就知道用什么算法这道题需要想一想这道题完全没有头绪。这个扫题动作的价值在于让你对整场考试的难度分布有全局判断从而决定策略秒杀题控制在每题20分钟以内熟悉题最多花30分钟陌生题放到最后如果剩下时间不足就直接放弃。很多同学失败不是因为难题做不出来而是把大量时间耗在一道中档题上导致后面的简单题没时间做。7.2 按分数密度排队不按题目顺序硬啃如果题目没有“必须按顺序作答”的限制我强烈推荐按“分数密度”排序作答。所谓分数密度就是每道题的预计得分除以预计耗时。先把密度高的题做了保证分数落袋为安。举个例子一道20分钟的简单题分值30分另一道60分钟的难题分值50分。如果你先做难题万一卡住了最后可能只拿50分但如果你先做简单题再花剩余时间做难题的部分case总分很可能是3020甚至更高。这就是考试策略上的“贪心”——是不是和我们前面讲过的贪心题完美呼应了。7.3 部分正确永远比空白好最后一个建议也是最重要的一个千万不要因为想不到最优解就整道题放弃。笔试的判分往往是按case给分的你写一个暴力解只要能通过小数据case也能拿到一部分分数。2018年这批题里不少难题都设计了小数据范围subtask暴力DFS就能拿30%到50%的分数。我的习惯是每道题即使没有AC思路也先写一个最朴素的暴力版本保证写出“确定能跑出正确答案的代码”。等剩余时间充足了再在这个暴力版本之上做优化。这样即使优化失败暴力版本也已经放进提交框里分数已经到手。这套策略听起来很功利但校招笔试本来就是一场以“最大化得分”为目标的限时竞赛。把考试策略当作贪心算法来设计把自己当作需要调度的资源本身就是对算法思想的最好实践。重新复盘2018年字节跳动校招算法方向第一批这套题我最想传递的一句话是算法功底扎实的人靠的从来不是题海战术而是把每一类题背后的模型吃透再在考场上快速匹配模型、果断取舍。你不需要成为算法天才只需要成为一个训练有素的工程师。把基本功练到条件反射把每一道错题彻底理解透你刷过的每一套真题都会在真正的考场上成为你的底气。