当前位置：首页 > news >正文

贝壳算法笔试2023届卷2解析：KMP、BM25与优化算法全梳理

news 2026/8/31 4:16:15

贝壳找房的校招算法笔试，在居住服务赛道里算是最有辨识度的一套题。2023届的卷2整体难度不低，既要啃数据结构硬骨头，又要处理跟业务强绑定的编程题，还塞了几个让人意外的优化算法考点。我考完当晚就把题目回忆整理了一遍，今天把这份解析和备考思路完整写出来，给后面准备贝壳算法岗的同学做个参考。

关于卷面内容需要先说明一下：下面所有题目均为考场回忆整理，措辞不是原卷原文，但核心考法和考点方向是准确的。贝壳的题每年会有调整，但出题思路基本稳定，把这套卷子吃透，对你理解这家公司算法团队在找什么人会很有帮助。

1. 卷面整体印象与贝壳算法岗的出题思路

1.1 题型分布与时间压力

2023届算法卷2一共是三大块：单选题、多选题、编程题，外加两道选做题。考试时间给的是120分钟，实际做下来时间相当紧张，我周围的考生普遍反映编程题只能完整做出两题到两题半。

单选题大概15道，集中在数据结构、排序、复杂度计算、经典算法原理这些基础层面。多选题8道左右，难度有明显提升，主要坑在多选题的错选漏选都不得分，这就逼着你每个选项都得有把握才敢选。

编程题三题，分值递增，最后一题直接占了大头。选做题二选一，一道偏机器学习检索方向，一道偏运筹优化方向，两道题面都挺长，需要先花几分钟读懂业务场景才能动手。整个卷子的设计逻辑很清楚：先筛基础算法功底，再筛代码实现能力，最后筛你在具体业务场景下能不能设计出合理解法。

1.2 贝壳业务如何"借壳"出题

贝壳找房做的是居住服务，核心业务链条里包含房源检索排序、经纪人任务调度、智能估价、楼盘字典数据结构、用户与房源的匹配推荐。这些业务场景几乎被原封不动地搬进了笔试题。

比如编程题里出现"经纪人从门店出发带客户看多套房源"的路线规划，选做题里出现"用户搜索词与房源描述的相关性排序"，压轴题直接让设计"经纪人—带看任务"的分配方案。这种出题方式的好处是对校招生公平——你不懂房地产也能做，但如果你能意识到题目背后的业务含义，答题时会更主动。

我的直观感受是，贝壳算法岗比较看重候选人的两件事：一是基础算法是不是真的扎实，不是背答案那种，而是能应对变形题；二是面对业务问题时，有没有能力把业务描述抽象成数学问题。这两件事在卷面上体现得特别直白。

1.3 与卷1的横向对比

考场上有人提到上个月的卷1，我当时也刷过网上流传的版本。对比下来，卷2的整体风格有几点明显变化：选择题里对字符串匹配知识点的考查比重加大，KMP、字符串哈希都有涉及；编程题第二题的图论属性增强，从卷1的简单模拟题升级成了带权最短路问题；选做题增加了对算法原理的追问，不只是让你给出结果，还要说明为什么这个算法在这个场景下有效。

这种变化透露出一个信号：贝壳算法团队在校招筛选上，正在从"能写代码"向"懂算法原理并且能落地决策"方向迁移。卷2里优化算法相关题目明显增多，模拟退火、粒子群这类元启发式算法都作为选项或背景出现了。你不需要全部精通，但至少要知道它们各自擅长解决什么样的问题。

2. 选择题的硬核考点：KMP、排序与复杂度陷阱

2.1 手算模式串 "abacaba" 的 next 数组

选择题里有一道KMP相关的题，给的是模式串 p = "abacaba"，要求判断 next 数组的某一位取值。这道题在考生里讨论度很高，因为KMP的 next 数组在不同教材里有两种定义方式，理解不一致非常容易翻车。

我当时按照最常见的定义来算：next[i] 表示模式串 p[0..i-1] 这个子串的最长相等前后缀长度。逐个位置计算如下：

i = 1，子串为 "a"，最长相等前后缀为 0
i = 2，子串为 "ab"，前缀集合 {a}，后缀集合 {b}，无交集，取 0
i = 3，子串为 "aba"，前缀 {a, ab}，后缀 {a, ba}，最长公共前后缀是 "a"，长度为 1
i = 4，子串为 "abac"，前缀后缀无共同部分，取 0
i = 5，子串为 "abaca"，最长相等前后缀是 "a"，长度为 1
i = 6，子串为 "abacab"，最长相等前后缀是 "ab"，长度为 2
i = 7，子串为 "abacaba"，最长相等前后缀是 "aba"，长度为 3

按这个定义，next 数组就是 [0, 0, 0, 1, 0, 1, 2, 3]，下标从0到7。如果你在别的教材里看过另一种定义——next[i] 表示失配时模式串跳转到的位置，那结果会变成 [-1, 0, 0, 0, 1, 0, 1, 2]。两种都有道理，考试时看题目给的定义方式再计算，我当时在草稿纸上把两种都列了出来才选的答案。

这道题背后真正想考察的其实是"你知不知道 next 数组是怎么一步步算出来的"，而不是单纯背代码。字符串匹配在搜索、推荐、匹配场景里太常用了，KMP 作为经典线性复杂度算法，值得多花时间把它的推导过程研究明白。

2.2 排序算法在不同数据分布下的表现差异

多选题里有一道排序题，问在一个几乎有序的大数组上，哪些排序算法的表现会退化到接近最坏情况，哪些算法能够保持稳定效率。

我在考场上的思路是先排除稳定的。归并排序在任意输入下时间复杂度都是O(n log n)，不会因为数据有序而退化；堆排序的建堆和调整过程也跟数据分布关系不大，复杂度稳定在O(n log n)。会退化的是快速排序，如果实现方式固定取第一个元素作为基准，在已经有序的数组上每次分区都极度不平衡，递归深度变成n，时间复杂度退化到O(n²)。考点就在这里——不是"快排快不快"，而是"你的快排是怎么选基准的"。

当时还有个选项涉及冒泡排序。别笑，这题出得很典型。如果在冒泡排序里加了"某轮无交换就提前结束"的优化，那在几乎有序的数组上冒泡排序反而会很快结束；如果没加优化，它依然是一轮一轮机械比较，O(n²)跑满。这个细节区分度很高，很多人没注意到优化标志的存在。

排序相关选择题我多提一嘴：桶排序、桶思想的思想在数据分析里用得很多，但在笔试选择题里它通常作为"排序下界"的讨论背景。基于比较的排序时间复杂度下界是O(n log n)，而不基于比较的排序（计数排序、基数排序、桶排序）可以做到线性复杂度，代价是空间。这些概念要形成知识网络，不要单独记。

2.3 贪心、快速幂与"数学底子题"怎么考

卷2里出现了至少三道跟数学基础强相关的选择题。一道是快速幂，给了一个中等大小的底数和指数，让你算模运算结果。快速幂的核心思想是把指数按二进制拆分，比如计算 a^13，13的二进制是1101，于是 a^13 = a^8 × a^4 × a，每一步只需反复平方底数，整体复杂度从O(n)降到O(log n)。这是很多密码学、哈希算法的基础，出现在算法卷里不意外。

一道是贪心算法的经典题——最少用多少硬币凑出某个金额。这类题容易让考生惯性思维直接按面值从大到小贪心，但题目故意设计了一个反例面值组合，此时贪心并不能得到最优解，必须用动态规划。这种"伪贪心"陷阱在校招笔试里出现频率非常高，考的就是你能不能识别贪心策略的适用条件。贪心成立的前提是"局部最优能推出全局最优"，比如硬币面值是倍数关系时才成立；而一般货币体系里面值之间并不是严格倍数，此时只能靠DP。

还有一道给了递推关系，求第n项，问时间和空间复杂度最优能到多少。这就涉及状态压缩DP，用滚动数组把空间复杂度从O(n)压到O(1)。题目本身不难，但很多人习惯性开一维数组存所有中间结果，忘了只需要保留前两项，白白丢分。这类"能不能再优化一下"的意识，贝壳的笔试题里反复在考。

3. 编程题第一题：经纪人带看路线与最短路算法

3.1 原题回忆与输入输出设计

编程题第一题给了一个比较经典的业务场景：一个经纪人要从门店出发，带着客户依次去看若干个房源，每个房源看完后可以选择直接去下一个房源，也可以先回门店再出发。所有门店和房源之间形成一个无向带权图，边的权值表示通行时间。题目输入是节点数 n、边数 m、门店节点编号、需要带看的房源节点列表，输出是从门店出发、带看完所有房源再返回门店的最短总时间。

这个题的关键在于读题要仔细，因为它没有要求"按给定顺序"带看，而是允许你自由安排带看顺序。这就把问题的复杂度直接拉高了——如果允许自由排序，本质上是在求经过一些指定节点的最短回路，是旅行商问题。

我看到题面第一反应是难度跳跃有点大，但再一想，贝壳这套卷子确实有意识地在考察"你能不能识别出某个问题其实是TSP"。当你识别出来之后，就要根据数据范围决定用什么算法。

3.2 最优解设计思路与复杂度分析

我的做法分两步走。先跑Floyd或者Dijkstra求所有节点之间的最短距离，但这一步其实可以更精细——原图的节点数可能很大，但真正要做路径规划的只有门店加需要带看的房源，总数不大时，只需要以这些关键节点为源点分别跑一次Dijkstra，得到关键节点之间的两两最短距离。这个操作在数据范围比较大的时候可以节省大量时间。

拿到关键节点之间的最短路矩阵后，问题就变成了一个"小规模TSP"。带看房源数量是k的时候，可以用状态压缩动态规划处理：dp[S][i] 表示已经带看完集合 S 里的房源，当前停在房源 i，花费的最少时间。状态转移时枚举下一个要看房源 j，如果 j 不在 S 里，就尝试从 i 走到 j。初始状态是 dp[1<<i][i] = dist[门店][i]，答案是 min(dp[全集合][i] + dist[i][门店])。状态数 O(2^k × k)，每个状态转移 O(k)，总复杂度 O(2^k × k²)，k 在 15 以内都能跑得动。

如果你没学过状态压缩DP，暴力的全排列枚举也能过一部分测试用例。k ≤ 8 时，全排列 k! 也就是40320种，加上每种的路径求和，完全可以接受。所以这道题的数据范围设定，其实给了至少两层解法空间——基础较好的用状态压缩DP拿满分，基础一般的用排列枚举也能拿不少分。这种"层层递进"的判分设计我认为是合理的，能有效区分不同水平的候选人。

考虑效率更极致的做法，可以先对所有关键节点跑一遍Dijkstra，预处理关键节点两两最短路，再用状态压缩DP，复杂度就是 O(k(n+m) log n + 2^k k²)，这是这道题的正解。考场时间有限，不建议直接上 Floyd，O(n³) 在大数据下会超时。

3.3 边界条件与易错点：别在最简单的地方丢分

这道题的易错点不在算法，而在边界处理。第一个坑是图可能不连通，某些房源节点可能无法从门店到达，此时应该输出 -1，而不是跑出一个奇怪的大数。第二个坑是可能有多个房源在同一节点，这种情况要注意去重，否则路径规划会认为要访问同一个节点多次。第三个坑是节点编号从0开始还是从1开始，题目没明确说明的话，用样例数据验一下再写，边读边验证能省去不少调试时间。

我考场上还犯过一个低级错误：自己把"按给定顺序带看"当成题目的隐含条件，导致第一版代码完全跑偏。后来重读题面发现是"可以自由排序"，这是两种完全不同的算法路径。提醒所有考生，编程题动笔前先把题目里的"自由""任意""至少""若干"这类词圈出来，它们往往决定了解法方向。

4. 选做题之一：房源检索排序与BM25算法实战

4.1 题面回忆：用户搜索词与房源描述的相关性排序

选做题有一道跟搜索引擎排序强相关的题目，题干模拟了一个简化版房源检索场景：给定若干条房源描述文本，每条描述包含区域、户型、面积、朝向、周边设施等信息。用户输入一个查询词，要求设计一个方案给房源打分排序，输出相关性最高的TopN房源。

这道题本质上是信息检索中的文本相关性问题，最经典的解法就是BM25。我当时看到这题眼睛一亮——BM25是搜索引擎和推荐系统里最常用的文本匹配算法之一，贝壳作为信息服务平台，考这个太合理了。

4.2 BM25匹配分数的计算逻辑

BM25的核心思想可以拆成两个部分。一部分是词频（TF），即查询词在文档中出现的次数越多，文档越相关；另一部分是逆文档频率（IDF），即包含该查询词的文档数越少，这个词越能区分文档，权重越高。两者综合起来，就是BM25的评分公式：

score(D, Q) = Σ(IDF(qi) × (f(qi, D) × (k1 + 1)) / (f(qi, D) + k1 × (1 - b + b × |D| / avgdl)))

这个公式看着吓人，实际思想很朴素。f(qi, D) 是词 qi 在文档 D 中的出现次数；|D| 是文档长度，avgdl 是平均文档长度；k1 和 b 是超参数，一般取1.2到2.0和0.75。k1 控制词频的饱和效应，出现次数超过一定量后，再多出现的边际收益会越来越小；b 控制文档长度的影响，长文档的匹配分值会被适当压低，避免长文档靠字数刷词频占便宜。

实现思路就是先对房源描述做分词，统计词频和文档频次，然后对每个查询词计算相关度，最后累加排序。在笔试题里直接调 jieba 分词再自己实现BM25公式，或者干脆用内存里的倒排索引，都能跑通。

4.3 检索模型的工程化变形：分数融合和冷启动场景

BM25这道题背后其实还有一层延伸思考，笔试题不会明说但要你具备这种意识：线上真实场景里，搜索排序往往是多路召回加多信号融合。BM25只是文本相关性的一路信号，除了相关性，还要考虑房源质量分、经纪人响应速度、距离用户当前位置远近、价格匹配度等。

如果你能在写这题的时候主动提一句"后续可以在BM25基础上叠加业务特征进行线性加权或GBDT排序"，这题的答题层次会明显提升。阅卷人想看的不是只会调库，而是理解一个算法在真实系统里是扮演某一环的。

另外一个跟推荐冷启动相关的考点也在选择题里出现过，就是KNN算法的应用能力。KNN在房源推荐冷启动阶段可以做用户相似度匹配——新用户没有行为记录时，用他输入的搜索偏好（价格区间、面积、区域）找到最相似的老用户，把老用户感兴趣的房源推荐给他。KNN实现简单、解释性强，很适合作为冷启动阶段的baseline，但它的问题也明显：计算量随样本量线性增长，高维特征下距离度量不够稳定，实际使用时一般会先做特征筛选或降维。

5. 压轴题：经纪人任务调度与启发式优化算法的用武之地

5.1 压轴题描述：经纪人—带看任务的多约束分配

压轴编程题是一道明显有现实业务背景的调度题。题面大意是有若干个经纪人和若干个带看任务，每个经纪人对不同房源的熟悉程度不同，因此完成带看的效率和评分也不同。每个经纪人一次只能带看一个任务，每个任务只需要一个经纪人。要求设计一个分配方案，使得所有经纪人完成任务的整体收益最大，或者整体完成时间最小。

第一眼看起来，这就是经典的二分图最大权匹配问题，可以用KM算法（匈牙利算法的带权版本）求解。二分图左侧是经纪人节点，右侧是任务节点，边的权值是匹配收益，求最大权完美匹配。这个知识点在热词里也出现了，说明命题人确实有意识地在考察经典图算法，而不是随便给道模拟题充数。

如果经纪人数量和任务数量不相等，还要先做补零处理，把图补成完美匹配的形式再跑KM。这是很多人做这道题容易卡住的地方——原题可能设定了经纪人数量多于任务数量，或者反过来，不补零直接套模板会出错。

5.2 为什么说粒子群、模拟退火、强化学习是"加分项"

压轴题的最后一小问，问的是"如果任务数量增加到较大规模，精确算法无法在有限时间内求出最优解，你会采用什么策略近似求解，并说明理由"。这种开放性问题才是整张卷子真正拉开差距的地方。

这道题最容易想到的策略是贪心——按收益从高到低排序，依次把每个任务分配给当前最优的经纪人。贪心速度快、实现简单，但容易陷入局部最优。我当时在答题里提了两种改进方向，一是模拟退火，二是粒子群算法。

模拟退火的核心思想来自金属冶炼中的退火过程，金属高温时分子活跃，随着温度降低逐渐稳定到低能状态。用在组合优化里，就是从当前解出发，通过交换两个任务的分配产生新解，如果新解更优就接受它，如果新解更差，也有一定概率接受，这个概率由 Metropolis 准则给出——温度越高、目标值变差越多时概率就越小。这种"允许暂时变差"的机制，正是跳出局部最优的关键。

粒子群算法则是模拟鸟群觅食行为，每个候选解是一只在解空间里飞翔的"粒子"，粒子会记住自己历史上最好的位置，同时参考整个群体历史上最好的位置，调整自己的飞行速度。对调度问题来说，粒子群通过反复迭代，能在较短时间里找到质量不错的可行解。它的优势在于实现简单、参数不多、对连续和离散问题都有效，缺点是容易早熟收敛，需要配合足够的迭代轮数和合适的参数设置。

如果你对强化学习有了解，还可以提到多智能体强化学习在调度场景的应用——每个经纪人看作一个智能体，通过环境反馈学习协作分配策略。但这个方向在笔试题里属于加分中的加分，不建议没有相关经验的人硬写，容易露怯。我当时只在最后提了一笔，重头放在了模拟退火和粒子群的对比上。

5.3 常见错误：把调度题做成贪心之后直接交卷

这题有个明显的丢分点：只写贪心解法而没有后续分析。不是说贪心不正确，而是在"追求最优解"的压轴题语境下，你的分值是跟"问题难度认知"挂钩的。完全不做讨论直接交卷，虽然能过一部分测试用例，但拿不到较高分数。

另一个错误的思路是把这题当成"每个任务都独立选择最优经纪人"，忽略了一个经纪人同时只能接一个任务的约束。这个约束恰恰是调度问题和非调度问题的分界，忽略它等于没有理解题目的业务含义。做调度类笔试题时，先把约束条件列全，再思考算法，效率会高很多。

6. 考后复盘：这套卷子真正想筛什么能力

6.1 代码基本功决定你能拿多少保底分

复盘整张卷子，最核心的结论是：代码基本功决定了你的下限。选择题考察KMP next数组手算，考察排序算法在不同数据分布下的表现，考察快速幂和贪心适用条件——这些都是计算机专业的基本功。这些题没有技巧，只能靠平时多写多练。

编程题即使不会状态压缩DP，也可以用全排列枚举拿部分分；即使不会BM25公式推导，用简单的TF-IDF也能完成排序；即使不会模拟退火，分析清楚约束条件也能给出合理的贪心近似方案。这些解法都拿不到满分，但能保证你不至于交白卷。保障底分靠的是基本功和审题能力。

6.2 抽象建模能力决定你能走多远

卷2真正拉开差距的，是"能不能识别这道题其实是什么问题"。带看路线题背后是TSP，经纪人调度题背后是二分图最大权匹配，房源检索题背后是BM25排序模型。如果你能识别出它们背后的经典问题模型，解题思路就顺理成章了。

这种抽象建模能力，真的需要靠平时刷题时有意识地训练。每次遇到一个长题面的题目，先问自己三个问题：这是搜索/动态规划/图论/匹配/排序中的哪类问题？数据范围决定我应该用什么复杂度的算法？业务描述里的哪些信息是干扰项，哪些是真正的约束条件？训练一段时间后，读完题面就能条件反射地画出问题模型，这种状态上去考场是真的有用。