企业官网建设流程全解析

一份迟到的贝壳找房校招算法卷复盘：考的其实不只是算法

去年秋招季帮实验室几个师弟师妹做模拟面试辅导，前后整理了不少大厂的校招算法真题。贝壳找房2023届校招算法卷1是其中比较有代表性的一套，它的题目难度不算顶尖，但考察面很杂——从经典字符串匹配到动态规划、从图论到贪心策略，基本上把计算机科班的核心算法考点扫了一遍。当时有个师妹考完跟我说：“题目看着都眼熟，但做起来就是差点意思。”这句话其实点出了这类校招算法卷的本质：它考的不是你会不会背某个算法，而是你在有限时间内能不能快速识别题目类型、选对解题思路、写出能跑的代码。

这篇文章把这份算法卷的题目结构、核心考点和解题思路完整复盘一下，包括KMP算法的next数组到底怎么推、动态规划的边界条件怎么定、Dijkstra在什么场景下会失效这类细节。适合正在准备秋招春招的应届生、想转算法岗的非科班同学，以及单纯想检验自己算法功底的从业者。看完之后你会发现，校招算法题的通关密码其实就六个字：识别、拆解、套模板。

1. 试卷整体风格与考点分布

贝壳这套算法卷的题型结构比较典型：选择题+编程题，编程题占大头。从题目风格来看，出题人明显在意基础算法的扎实程度，而不是偏题怪题。整套卷子做完的感受是：每个题都认识，但每个题都有坑。

1.1 考点覆盖范围

根据做完的回忆和复盘，这套卷子的考点大致分布如下：

• 字符串类：KMP算法的next数组计算，这是热搜词里出现最多的考点之一。给一个模式串让你手推next数组，属于送分题但也是失分重灾区。
• 数据结构：排序算法的稳定性比较、堆排序的手写实现、二分图匹配的HK算法选型。
• 图论：Dijkstra最短路径、拓扑排序相关的变体题。
• 动态规划：一道编辑距离的变体题，以及一道区间DP的题目。
• 贪心：区间调度类问题，但有两个看似正确的贪心策略会翻车。
• 数值计算：快速幂算法，考察二进制思维。

1.2 题目难度阶梯

这套卷子的难度设计是层层递进的。前三道题属于热身级别，基本是数据结构的基础操作，比如手写一个稳定的归并排序、给定一个二叉树求层序遍历。中间几道题开始上强度，比如KMP的next数组推导和Dijkstra的应用变体。最后两道题才是真正的分水岭，一道综合性的动态规划加一道需要优化到O(n log n)的贪心题。

用我当时带师弟模拟时说的原话：“贝壳这套卷子，前60%的分数是给认真刷过题的人送的，后40%的分数是给真正理解算法本质的人留的。”这也符合贝壳找房作为居住服务领域头部公司的技术定位——他们需要的不只是会调包的人，而是能理解算法原理、能针对业务场景做优化的工程师。

2. 字符串算法：KMP的next数组是基本功分水岭

热搜词里关于KMP的讨论特别多，比如“在KMP算法中，对于模式串p=‘abacaba’，其next数组”。这几乎是每次校招必考的题型。KMP的价值不仅仅在于字符串匹配本身，它背后的“前缀函数”思想在很多场景都能复用，比如字符串压缩、重复子串检测、文本比对。

2.1 next数组的定义与手推方法

KMP算法中的next数组，严格来说有几种不同的定义版本。贝壳这套卷子采用的是最常见的定义：next[i]表示模式串p的前i个字符组成的子串中，最长相等前后缀的长度。注意，这里的“前缀”不包括整个子串本身，“后缀”也不包括整个子串本身。

以模式串p=“abacaba”为例，手推next数组的过程应该是这样的：

• i=1，子串为“a”，没有真前后缀，next[1]=0（部分教材从0开始计数，下标处理有差异，但原理一致）
• i=2，子串为“ab”，前缀“a”，后缀“b”，不相等，next[2]=0
• i=3，子串为“aba”，前缀“a”、“ab”，后缀“a”、“ba”，最长相等前后缀是“a”，长度为1，next[3]=1
• i=4，子串为“abac”，前缀“a”、“ab”、“aba”，后缀“c”、“ac”、“bac”，没有相等项，next[4]=0
• i=5，子串为“abaca”，前缀“a”、“ab”、“aba”、“abac”，后缀“a”、“ca”、“aca”、“baca”，最长相等前后缀是“a”，长度为1，next[5]=1
• i=6，子串为“abacab”，前缀“a”、“ab”、“aba”、“abaca”，后缀“b”、“ab”、“cab”、“acab”，最长相等前后缀是“ab”，长度为2，next[6]=2
• i=7，子串为“abacaba”，前缀“a”、“ab”、“aba”、“abac”、“abaca”、“abacab”，后缀“a”、“ba”、“aba”、“caba”、“acaba”、“bacaba”，最长相等前后缀是“aba”，长度为3，next[7]=3

所以p=“abacaba”的next数组为[0, 0, 1, 0, 1, 2, 3]（从下标1开始的话，前面补一个-1或0，取决于具体实现）。

2.2 手推next数组的实用技巧

考场上手推next数组，最容易出错的地方是把“最长相等前后缀”和“回文”搞混。前后缀相等强调的是顺序一致，比如“aba”的前缀“ab”和后缀“ba”就不相等，因为顺序不同。

我总结了一个快速推next数组的办法：每增加一个字符，就看新增字符能否和已有的最长前缀的下一个字符对上。能对上就在前一个next值基础上加1，对不上就回退到更短的前缀再比较。这个思路其实就是KMP算法中求next数组的递推过程，理解了它在推导时就不用一个个枚举所有前后缀了。

另外要注意考场常见的坑：题目中next数组的定义可能不同。有的教材next[0]=-1，有的从0开始。做选择题时先看选项的取值区间，再反推题目用的是哪种定义，这个技巧能帮你规避至少一道送命题。

3. 动态规划与贪心策略：区分套路与真功夫

动态规划和贪心是校招算法卷的常客，贝壳这套卷子也不例外。但它的出题角度比较讲究，不是直接扔一道“最长上升子序列”让你背模板，而是给一个贴近业务场景的包装，考察你能不能把包装剥掉看到底层的模型。

3.1 编辑距离变体题的状态定义

卷子里有一道编辑距离的变体题：给定两个字符串，允许的操作从“插入、删除、替换”变成了“插入、删除、替换、交换相邻两个字符”，求最小编辑距离。这题如果没见过，很容易在状态转移上卡住。

传统的编辑距离问题，状态定义是dp[i][j]表示字符串A的前i个字符转换为字符串B的前j个字符所需的最少操作次数。多了“交换相邻字符”这个操作后，状态转移方程需要增加一条：如果A的第i-1个字符等于B的第j个字符，且A的第i个字符等于B的第j-1个字符，那么dp[i][j]可以由dp[i-2][j-2]加1转移而来。

这里的关键点是：交换操作影响的不只是当前位，还有前一位。所以状态转移时要考虑两层的对齐关系。当时有个师弟在这个题上卡了很久，他的问题是只关注了当前字符的匹配，忽略了交换操作对前一位的联动影响。用一句话总结就是：当操作类型发生变化时，先重新定义状态的含义，再推导转移方程，不要试图在旧的状态定义上打补丁。

3.2 区间调度贪心：看起来对的不一定对

区间调度问题是贪心算法的经典入门题。贝壳这套卷子里的变体是：给定若干区间，要求选出尽量多的区间使得它们互不重叠。常见的贪心策略是按区间结束时间排序，然后依次选择。这个策略是正确的，因为选择结束时间早的区间能为后续留出更多空间。

但卷子里增加了一个条件：区间有权重，要求选择互不重叠的区间使得权重之和最大。这时候“按结束时间贪心”就不再成立了，因为一个结束时间晚但权重大的区间可能比两个结束时间早但权重小的区间更优。正确解法是动态规划：先按结束时间排序，dp[i]表示前i个区间能获得的最大权重和，然后二分查找与第i个区间不冲突的最后一个区间。

这个题的教训很深刻：贪心算法成立的先决条件是局部最优能推出全局最优。当你给问题增加一个维度（比如权重）时，这个前提可能就被破坏了。考场上遇到贪心题，先花30秒验证一下贪心策略能否被反例推翻，再决定是直接贪心还是转动态规划。

4. 图论算法与数值计算：高频考点的工程化思考

图论和数值计算在校招中的出镜率一直很高。贝壳这套卷子里面的Dijkstra和快速幂都不是直接裸考，而是加了实际场景的包装。这正是现在校招算法题的普遍趋势：把算法放到具体业务场景里考。

4.1 Dijkstra在业务场景中的应用变形

卷子里Dijkstra的题目包装成了一道与“通勤时间计算”相关的题：一个城市有若干地铁站和公交站，换乘需要额外的时间成本，求从起点到终点的最短时间。这题乍一看是图论题，但难的点在于“换乘代价”怎么建图。

如果直接套Dijkstra模板，把每个站点当节点，换乘时间加到边上，会出现一个问题：换乘时间只发生在路径切换时，不能被简单地累加。比如你从地铁A线换到地铁B线，需要额外5分钟，这个5分钟不应该算在任意一条边上，而是应该算在“换乘”这个动作上。

解法一：把每个站点按线路拆成多个节点，同一条线路内的节点边权为站间运行时间，同一个站点的不同线路节点之间连一条边权为换乘时间的边。解法二：在Dijkstra的状态里增加一个维度，记录当前所在线路，在转移时判断是否需要额外计算换乘时间。

这道题给我的感触是：校招的图论题，真正的难点往往不在Dijkstra本身，而在如何把业务约束转化成图的边和节点。这也是为什么有些刷题很多的人在校招笔试中翻车——他们太熟悉模板，却不擅长建模。

4.2 快速幂算法的二进制本质

快速幂属于那种“会者不难，难者不会”的题目。贝壳这套卷子直接要求写一个计算a的b次方模c的代码。

快速幂的核心思想是把指数b写成二进制形式，比如b=13，二进制是1101，那么a^13 = a^8 * a^4 * a。通过不断对底数平方来得到a的各二进制位对应的幂次，时间复杂度从O(b)降到了O(log b)。

def fast_pow(a, b, c): result = 1 a = a % c while b > 0: if b & 1: # 当前二进制位为1 result = (result * a) % c a = (a * a) % c # 底数平方 b >>= 1 # 右移，处理下一位 return result

这段代码有三个容易出错的细节：一是a要先对c取模，因为(a * b) % c = ((a % c) * (b % c)) % c；二是b为0时要返回1，因为任何数的0次方都是1；三是注意取模的时机，防止中间结果溢出。考场上时间紧，很多人会在取模的细节上犯低级错误。

我遇到过不止一个候选人能把快速幂的思路讲清楚，但代码写出来边界条件不完整。所以在带新人时我总会强调：算法题的代码实现，边界条件的处理比思路本身更体现基本功。

5. 笔试时间分配与答题策略

整场笔试的时间一般是90到120分钟，题量在5到8道之间。贝壳这套卷子属于题量中等偏多的类型，如果按部就班地做，很容易出现时间不够用的情况。

5.1 拿到卷子后的前5分钟

不要急着做题。先把所有题目扫一遍，按难度和熟悉度打标签。我问过不少参加校招的同学，他们普遍的做法是顺着题号一题一题做，遇到难题卡住了也不舍得跳过，结果前面的分数没拿全，后面的简单题也没时间做。

我的建议是：先做自己最有把握的题，把确定性分数拿到手；再做看起来眼熟但需要思考的题；最后攻坚完全没有思路的题。以贝壳这套卷子为例，KMP的手推next数组、快速幂这类题属于送分题，应该放在最前面做；编辑距离变体和带权重的区间调度属于拉分题，放在中间；如果时间不够，难度最大的题目可以先用暴力解拿部分分数。

5.2 编程题的“部分分”策略

校招笔试的判题系统通常有部分分机制，不是只对全对或全错。即使想不出最优解，暴力解法也能拿到一定比例的分数。所以在考场上，遇到不会的编程题，先用最简单的暴力算法写一版，保证能过部分测试用例，再想着优化。

举个例子，区间调度的变体题如果想不到动态规划加二分的解法，可以直接按权重大小排序然后暴力枚举所有组合，n比较小的时候也能过一部分用例。我当时带师弟训练时总跟他们说：笔试的目标是拿分，不是炫技。能AC的题不丢分，不能AC的题尽量拿部分分，这才是校招笔试的正确姿势。

5.3 代码书写的工程化习惯

还有一点值得提醒：在线笔试系统的代码编辑环境通常没有IDE那么智能，没有自动补全、没有语法检查，写代码时要格外注意语法错误。我见过很多人在笔试中因为一个小括号没闭合导致编译失败，白白丢了一道题的分数。

建议平时练习时就用在线编辑器写代码，不要依赖IDE的自动补全功能。另外，写代码前先在草稿纸上理清思路，把关键变量和状态转移写清楚再敲代码，能显著提高一次通过率。

6. 常见问题与避坑技巧总结

复盘这套卷子的过程中，我整理了考生最容易栽的几个坑，主要集中在KMP和动态规划这两块。这里综合多个人的错题经验做一个汇总。

6.1 KMP相关的常见踩坑点

• next数组定义搞混：不同教材对next数组的定义不同，有的以-1开头，有的以0开头。遇到选择题先看选项的取值范围，反推题目使用的定义。
• 前缀和后缀的边界处理：最长相等前后缀不能包含整个字符串，容易出错的是当整个字符串就是重复串时，有人会把整个串的长度算进去。
• 手推时枚举遗漏：建议采用“新增字符与前缀匹配”的递推思路，不要暴力枚举所有前后缀，容易遗漏短的前后缀匹配情况。

6.2 动态规划的常见踩坑点

• 状态定义不清晰导致转移方程错误：特别是在增加操作类型或约束条件后，要重新审视状态定义是否需要调整。
• 边界条件处理错误：比如dp[0][j]、dp[i][0]的初始化值搞错，或者dp数组的长度定义不准确。
• 空间优化时逻辑混乱：用滚动数组优化空间时，要确保每个状态在转移前读到的是上一轮的值，不是被覆盖后的新值。

6.3 其他高频踩坑点

• 排序算法的稳定性判断：快排不稳定、归并稳定、堆排序不稳定、基数排序稳定，这些结论要背熟，选择题经常考。
• 快速幂输入数据范围：a、b、c都是大整数时，中间过程的取模要及时，否则Python虽然不会溢出但会拖慢速度，C++和Java则可能直接溢出。
• 全局变量和局部变量的作用域：在线笔试系统里，多道题共用一套代码框架时，全局变量可能会串味。每道题最好封装成独立的函数，避免变量污染。

7. 这套卷子的出题规律与备考建议

复盘完整套卷子，不难发现贝壳这套算法卷的出题规律，本质上反映的是整个校招算法考察的大趋势。理解这个规律，比单纯刷题更有价值。

7.1 出题规律：从“考知识”到“考能力”

传统的算法题考察的是“你知不知道这个算法”，比如让你手写一个快排，只要背过模板就能做出来。但现在校招算法卷的命题趋势是“给你一个业务场景，看你能不能识别出该用什么算法”，比如把区间调度包装成值班排表问题，把Dijkstra包装成通勤路径规划问题。

这个变化对应的是实际工作中算法工程师的真实工作状态：日常业务给出的问题很少是“请用KMP做字符串匹配”这种直白描述，更多是“用户搜索关键词后返回匹配的房源列表，但长尾关键词召回效果不理想”，需要你自己先抽象建模，再选择合适的算法解决。所以备考时不能只刷模板题，要练习“读题识别算法模型”的能力。

7.2 高效备考的三个阶段

第一阶段的重点是重建知识体系。把基础数据结构和常用算法过一遍，确保每种数据结构的特性和复杂度了然于胸。这个阶段不需要刷太多题，而是要吃透原理。

第二阶段的重点是分类刷题。按算法类型去刷，比如这周只刷动态规划，下周只刷图论。刷题时每道题都要思考三个问题：这道题考的是哪个算法模型，为什么用这个算法，有没有其他可行方案。

第三阶段的重点是模拟实战。找几套目标公司往年的真题，开计时器模拟笔试环境，提前适应做题节奏和时间分配。这个阶段更重要的是复盘：每套题做完后，整理错题和耗时过长的题，分析卡顿的原因。

7.3 结合业务的算法训练

这套卷子还有一个值得注意的细节：部分题目的背景与贝壳的居住服务业务有关，比如房源匹配、通勤路径规划。这说明有些公司在校招时会偏好结合自身业务出题，考察候选人将算法应用于业务场景的能力。

备考时可以多做一步：思考一下目标公司的核心业务中，哪些环节会用到算法。以贝壳找房为例，房源推荐会用到推荐算法和协同过滤，附近房源搜索会用到空间索引，经纪人排班会用到调度算法。提前思考这些场景，不仅对笔试有帮助，在后续的面试中也能展示出对业务的理解，这在面试中是很加分的。

说实话，贝壳这套卷子单独拎出来看并不算最有难度的。横向对比其他大厂的校招算法题，它的深度不如字节跳动的面试题，广度不如阿里的笔试。但它的参考价值在于：题目设计得很“标准”，既覆盖了核心考点，又有一定的场景包装和思维深度。把它练透一遍，基本能应对大多数互联网公司的校招算法题。

从我带过的学生情况看，能在这套卷子上拿高分的人，几乎都有一个共同特点：他们不是靠背题取胜，而是真的理解了每个算法背后的设计思想和适用边界。这也是我写这篇复盘最想传递给读者的信息——刷题是手段，理解才是目的。把KMP的前缀函数想透了，你就不会再对字符串匹配题发怵；把动态规划的状态定义想清了，你就能应对各种变体题。这套卷子真正的价值不是帮你拿到贝壳的offer，而是帮你把算法基本功打磨扎实，这比任何offer都值钱。