B站算法岗秋招笔试题复盘：从KMP到动态规划的核心考点

2019年B站秋招技术岗的算法笔试题，第二套，当年在求职群里讨论度很高。很多人做完第一反应是：选择题怎么这么杂？KMP、排序、机器学习、图像处理全都掺在一起，编程题反而比较常规。我后来把整套题认真复盘了一遍，发现这套题其实是B站算法工程师日常工作的缩影——既有纯算法基础，也有业务场景理解，还有工程实现能力。

这套题适合两类人看：一类是正在准备大厂算法岗校招的同学，可以直接把它当模拟卷做；另一类是已经在做推荐、搜索、音视频相关算法的工程师，也能从中看到面试官真正想考察的底层能力。接下来我会按实际做题顺序，把考察方向、高频考点、编程题思路、业务场景题以及我踩过的坑，一条条拆开讲清楚。

1. 这套题到底考什么：整体风格与考察方向

1.1 选择题出题范围：比想象中要宽

B站的算法岗位不是单一的“推荐算法工程师”，还有内容理解、视频理解、图像算法、音频算法、搜索算法等方向。所以笔试题覆盖面会刻意拉得比较宽。这也是为什么很多人觉得第二套题“杂”。

从题目类型看，选择题大致可以分成四块：

• 数据结构与基础算法：KMP的next数组、堆排序稳定性、快速排序复杂度、贪心算法判断、Dijkstra适用条件、快速幂等。
• 机器学习与深度学习基础：KNN属于什么学习方式、K-means的收敛特性、KL散度是否对称、粒子群优化思路、卡尔曼滤波的预测-更新两步等。
• 图像与音视频基础：Sobel算子检测什么、音频重采样解决什么问题、图像分类任务的基本流程等。
• 业务场景题：搜索相关度怎么算、推荐排序怎么设计、如何评估一个内容理解模型等。

这里有一个很重要的信号：B站对算法岗的期待不是“会调包”，而是真正理解算法原理，并且能把算法落到视频业务场景里。比如考KL散度，表面是在考数学，实际是希望你理解生成模型、变分推断里的核心概念，因为做视频内容理解或者用户行为建模时，这些概念会反复出现。

1.2 编程题命题风格：经典题为主，坑在细节

第二套题的编程题是两道，难度中等偏上，类型上以字符串和动态规划为主，偶尔会来一道图论题。整体风格就是：不考偏题怪题，但会在边界条件和优化思路上埋坑。

在线笔试环境一般是牛客网或者赛码网，需要自己处理输入输出。这一点看着不起眼，实际考试时影响很大。我记得当年有人第一道字符串题用getline读入，结果本地跑得好好的，一提交就超时或者读不到数据，原因就是没注意平台的语言环境和输入格式差异。

选择题覆盖面广，编程题偏基础，这两者叠加起来，其实是在考察一件事：基础是否扎实到能稳定输出。

2. 高频基础算法考点：这些题错过一次就长记性

2.1 KMP算法与next数组：字符串匹配的地基

第二套题里有一道非常典型的KMP选择题，题干是：对于模式串 p = "abacaba"，其 next 数组是什么？很多同学看到这种题就慌，其实KMP的next数组计算有固定套路，只要理解“最长相同前后缀”这个定义，就能一步步推出来。

先说明一下next数组的不同定义。有些教材把next[i]定义为：模式串前 i+1 个字符组成的子串中，最长相同前后缀的长度。有些版本则定义为失配时模式串指针应该跳转到的下标。两种定义下结果不同，但推导逻辑一样。B站这套题我印象里用的是“最长相同前后缀长度”这个定义，也就是前缀表中常见的形式。

以 p = "abacaba" 为例，从左到右逐个子串计算：

所以按这个定义，next数组是 [0, 0, 1, 0, 1, 2, 3]。如果题目定义的是“失配跳转位置”，那通常会在next[i]基础上再整体左移或减1，这个时候就要格外小心，必须先看清题目给出的定义再作答。

这道题考察的不只是记忆，而是是否真的理解“前后缀匹配”这个核心思想。实际业务里，B站的搜索联想词、弹幕敏感词过滤、稿件标题匹配等场景都会用到字符串匹配，KMP不是纸上谈兵。

实操建议：考前不要死记next数组的例子，动手把模式串的各个前缀子串写出来，自己标一遍最长相同前后缀，比背十遍都管用。

2.2 排序算法全家桶：稳定性和复杂度不能只背结论

第二套题有一道选择题问：下列排序算法中，哪些是不稳定的？选项里通常会有快速排序、堆排序、归并排序、直接插入排序。这道题的正确解法不是靠“死记结论”，而是理解“稳定性”到底指什么——相同元素的相对顺序在排序前后是否保持不变。

直接说结论：

堆排序为什么不稳定？因为堆排序在“交换堆顶和末尾元素”时，可能会把相同元素的相对顺序打乱。举个例子，数组 [5a, 5b, 3]，建堆后5a和5b可能交换位置，排序结束后5a跑到5b后面去了，这就是不稳定。

我在考场上有一个习惯：遇到排序稳定性的题，直接在脑子里跑一个三个元素的例子，比如 [2a, 2b, 1]，想一下排序结束后2a和2b的顺序会不会变。这个方法比硬背表格可靠得多。

堆排序本身的实现也要会。核心是“建堆 + 交换堆顶 + 向下调整”三步。笔试如果出编程题让你手写堆排序，先把调整函数写对：

void heapify(vector<int>& arr, int n, int i) { int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left < n && arr[left] > arr[largest]) largest = left; if (right < n && arr[right] > arr[largest]) largest = right; if (largest != i) { swap(arr[i], arr[largest]); heapify(arr, n, largest); } } void heapSort(vector<int>& arr) { int n = arr.size(); for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); for (int i = n - 1; i > 0; i--) { swap(arr[0], arr[i]); heapify(arr, i, 0); } }

这里有一个隐蔽的坑：建堆要从最后一个非叶子节点开始，也就是 n/2 - 1，而不是从0开始。如果这里写错，建出来的堆不满足堆性质，整个排序结果都会错。

2.3 贪心、Dijkstra与动态规划怎么区分

选择题里还常考一类题：下列算法中使用了贪心策略的是？选项一般有Dijkstra、Prim、Kruskal、动态规划、回溯等。

贪心算法的核心是“每步都做当前看起来最优的选择，并期望最终结果最优”。它成立的前提是问题具有贪心选择性质，也就是局部最优能推出全局最优。比如活动选择问题、Huffman编码、找零钱问题里的某些情况。

Dijkstra算法就是典型的贪心。它维护一个“已确定最短路径”的集合，每次都从优先队列里取出当前距离源点最近的节点，然后松弛它的邻接边。这个过程里，一旦一个节点被确定，就不再更新它——这正是贪心的体现。

这里必须记住：Dijkstra要求边权非负。为什么？因为当某节点u被拿出优先队列时，算法认定dist[u]已经是最短路径了，如果后面出现一条负权边能绕到u并让dist[u]更小，那这个认定就失效了。用负权边时得用Bellman-Ford或SPFA。

动态规划和贪心的区别在于：动态规划会保存子问题的解，并考虑所有可能的选择路径；贪心每步只做一种选择，不会回头看。笔试常考的经典动态规划题包括最长上升子序列、最长公共子序列、背包问题、编辑距离等。B站这套题在选择题里会问“哪些问题适合用动态规划解决”，本质上就是考对这两个概念的区分。

2.4 快速幂：数论题的“万能钥匙”

快速幂在算法岗笔试里出现的概率很高，尤其是要算组合数、概率期望的时候。B站这套题虽然没直接考很深的数论，但快速幂属于“基本功”，我建议每个人都能在30秒内默写出来。

核心思路很简单：把指数 b 看成二进制，从低位到高位看，如果当前位是1，就乘上对应的 a 的幂次；每次把 a 平方一次，b 右移一位。这样时间复杂度从 O(b) 降到 O(log b)。

long long fastPow(long long a, long long b, long long p) { long long res = 1; a %= p; while (b > 0) { if (b & 1) res = res * a % p; a = a * a % p; b >>= 1; } return res; }

几个容易踩的点：

• 底数 a 要先取模，防止 a 很大时溢出。
• 结果 res 初始化为1，而不是0。
• 指数 b 为0时，循环不执行，直接返回1，这符合数学定义。
• 如果 p 很大，中间乘法可能溢出 long long，这时需要换成更大范围的数据类型或者用快速乘。

我当时第一次写快速幂就栽在“a = a * a % p”这行上，如果忘记对中间结果取模，算到后面数据直接溢出，结果完全不对。

3. 机器学习与深度学习考点：不做只会调包的算法岗

3.1 KNN、K-means与聚类算法

B站算法岗笔试里，机器学习基础题不会考得很偏，但非常爱考“概念对比”和“边界条件”。KNN和K-means是高频题目。

KNN是监督学习还是无监督学习？答案是监督学习，因为它需要带标签的训练数据。KNN又被称为“惰性学习”，因为它在训练阶段几乎不做任何事，只是把样本存起来，真正计算发生在预测阶段。预测时，计算待预测样本与所有训练样本的距离，取最近的K个邻居投票决定类别。

KNN里的K是一个超参数。K选得太大，会把距离很远的样本也拉进来，造成欠拟合；K选得太小，容易受噪声影响，造成过拟合。特征也需要标准化，否则量纲大的特征会主导距离计算，比如“年龄”和“年收入”放在一起，收入数值可能把年龄的影响完全淹没。

K-means则是典型的无监督聚类算法。它的流程是：先随机选择K个点作为初始簇中心，然后交替执行“分配”和“更新”两步，直到中心点不再显著变化。这里的“K”需要预先指定，而且初始中心选得不好，可能会收敛到局部最优解。所以实际使用中一般会跑多次，选目标函数最优的结果。

选择题常问的点是：K-means迭代过程中，如果某个簇为空怎么办？或者，K-means对离群点是否敏感？答案是对离群点敏感，因为簇中心计算用的是均值，离群点会把均值拉偏。

3.2 从KL散度到模型评估

KL散度（Kullback-Leibler divergence）在笔试题里出现的频率不低，因为它和许多现代机器学习方法直接相关。题目往往不会让你手算复杂的公式，而是考概念性质。

KL散度的定义是：

KL(P || Q) = Σ P(x) * log(P(x) / Q(x))

它衡量的是：用分布Q去近似真实分布P时，额外需要多少信息量。KL散度有两个很关键的性质：

• 非负性：KL(P || Q) >= 0，当且仅当P和Q相同或几乎处处相同时取0。
• 非对称性：KL(P || Q) 一般不等于 KL(Q || P)。

非对称这一点是选择题的高频考点。很多人凭直觉觉得“差异”应该是对称的，但KL散度不是严格的“距离”度量。

KL散度和ELBO的关系也值得记一下。变分自编码器（VAE）的核心推导就是：最大化ELBO，等价于最小化 KL(后验分布 || 先验分布) 加上一个重构误差。B站笔试如果出生成模型相关的题，很可能绕不开这个概念。

机器学习模型评估这块，选择题喜欢考“过拟合和欠拟合的判断”“训练集、验证集、测试集的作用”“AUC的含义”等。对于B站这种内容平台，算法工程师需要关心推荐模型在线上是否真的有效，所以离线评估指标和在线AB实验的差异也是考点。

3.3 粒子群、模拟退火、卡尔曼滤波：优化与状态估计

除了深度学习和经典统计机器学习，B站这套笔试题还出现了一些更工程向的算法概念，比如粒子群算法、模拟退火、卡尔曼滤波。看起来像“冷门知识点”，其实和视频业务有直接关系。

粒子群算法（PSO）的原理是模拟鸟群觅食。每个粒子代表解空间中的一个候选解，它有自己的位置和速度。迭代时，每个粒子会受两个因素影响：一个是粒子自身历史最优位置（pbest），另一个是整个群体的最优位置（gbest）。速度更新公式是：

v = w * v + c1 * r1 * (pbest - x) + c2 * r2 * (gbest - x)

其中 w 是惯性权重，c1 和 c2 是学习因子，r1 和 r2 是随机数。粒子群算法本身是一种启发式全局优化方法，不依赖梯度信息，适合用在目标函数不光滑或者难以求导的优化问题上。

模拟退火算法的核心是“以一定概率接受更差的解”。算法的起点是一个初始温度，温度高的时候接受差解的概率大，随着温度逐渐降低，接受差解的概率变小，最终收敛到较优解。这个“接受概率”通常写作 exp(-ΔE / T)，其中 ΔE 是当前解和新解之间的目标函数差，T 是当前温度。它和粒子群一样，都是为了跳出局部最优。

卡尔曼滤波则是状态估计领域的基础算法。它有两个核心步骤：预测和更新。预测阶段用状态转移方程（比如运动模型）估计下一时刻的状态，更新阶段把传感器观测值和预测值加权融合，得到更精确的后验估计。这个过程有点像是“黄金分割”式的加权平均，关键是卡尔曼增益K的计算。

在B站，卡尔曼滤波可以用于视频目标跟踪中的轨迹平滑。比如检测算法输出目标位置时会有抖动，用卡尔曼滤波可以把轨迹变得更稳定。粒子群和模拟退火则可能出现在算法调参、工程优化等场景。笔试题一般只考“原理”和“适用场景”，但如果你能结合业务举出一两个例子，会显得更有优势。

4. 编程题实战复盘

4.1 字符串题：最长无重复字符子串

第二套编程题里有一道字符串处理题，和“最长无重复字符的子串”非常接近。题目描述通常是：给定一个字符串 s，请找出其中不含重复字符的最长子串的长度。比如 s = "abcabcbb"，答案是3，因为最长无重复子串是 "abc"。

这道题的正解是滑动窗口。用两个指针 left 和 right 维护一个窗口，right 不断向右移动，同时用哈希表记录每个字符最后出现的位置。当遇到一个已经在窗口内出现过的字符时，把 left 移到该字符上一次出现位置的下一个位置，保证窗口内没有重复字符。

int lengthOfLongestSubstring(string s) { unordered_map<char, int> lastIndex; int left = 0, ans = 0; for (int right = 0; right < s.size(); right++) { char c = s[right]; if (lastIndex.count(c) && lastIndex[c] >= left) { left = lastIndex[c] + 1; } lastIndex[c] = right; ans = max(ans, right - left + 1); } return ans; }

这里最关键的一步是 left 的更新逻辑。不能简单地写成 left = lastIndex[c] + 1，必须加一个条件 lastIndex[c] >= left。为什么？因为哈希表里记录的这个字符上次出现位置，可能已经不在当前窗口内了。如果上一次出现的下标比 left 还小，说明那个重复字符早就被排除在窗口之外，不需要移动 left。这个细节非常容易错，我在面试别人时发现很多人栽在这里。

时间复杂度是 O(n)，空间复杂度是 O(min(n, 字符集大小))。如果字符串是纯ASCII，字符集大小固定为128或者256，空间可以认为是O(1)。

4.2 动态规划题：最长上升子序列

另一道编程题常考的是最长上升子序列（LIS）。题目描述是：给定一个无序整数数组，找到其中最长严格上升子序列的长度。比如 nums = [10, 9, 2, 5, 3, 7, 101, 18]，答案是4，最长上升子序列是 [2, 3, 7, 101] 或 [2, 5, 7, 101]。

最直观的解法是动态规划，O(n^2)。定义 dp[i] 表示以 nums[i] 结尾的最长上升子序列长度，转移方程是：

dp[i] = max(dp[j] + 1)，其中 0 <= j < i 且 nums[j] < nums[i]

int lengthOfLIS(vector<int>& nums) { int n = nums.size(); vector<int> dp(n, 1); int ans = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) { if (nums[j] < nums[i]) { dp[i] = max(dp[i], dp[j] + 1); } } ans = max(ans, dp[i]); } return ans; }

O(n^2) 的解法虽然能过小数据，但笔试里如果数组长度到10^5，就会超时。更优的做法是“贪心 + 二分”，维护一个 tails 数组，其中 tails[i] 表示长度为 i+1 的上升子序列的最小末尾元素。

遍历每个元素 num，在 tails 数组中二分查找第一个大于等于 num 的位置，如果找到就替换，如果找不到就追加到末尾。最终 tails 的长度就是最长上升子序列长度。

int lengthOfLIS(vector<int>& nums) { vector<int> tails; for (int num : nums) { auto it = lower_bound(tails.begin(), tails.end(), num); if (it == tails.end()) { tails.push_back(num); } else { *it = num; } } return tails.size(); }

这里的“替换”为什么有效？因为对于同一个长度的上升子序列，结尾元素越小，后面就越容易接上更大的数。所以贪心地让 tails 里的每个元素尽量小，是在为未来的扩展留空间。

笔试中建议这样安排：先写O(n^2)的DP并确保正确，如果时间充裕或者知道更优解，再改成O(nlogn)的版本。有时候面试官看的是“你能写出一个正确解法，并且能分析它的复杂度”，而不是盲目追求最优。

4.3 图论题的通用解法

第二套题不一定每场都考图论，但Dijkstra、拓扑排序、并查集这些是算法岗的高频备选。如果遇到图论题，先判断是什么类型：

• 单源最短路径、边权为正：Dijkstra + 优先队列。
• 边权有负：Bellman-Ford或SPFA。
• 多源最短路径：Floyd，但要注意O(n^3)的复杂度限制。
• 判断有向图是否有环：拓扑排序，用入度数组 + 队列。
• 连通分量、动态连通性：并查集。

Dijkstra用优先队列优化后，时间复杂度是 O((V+E)logV)，能高效处理稀疏图。我建议把模板背到能无脑写出来的程度，因为考场上没有时间现场推导。

拓扑排序适用于有依赖关系的场景，比如B站的后台任务调度、课程学习顺序等。如果一个任务依赖另一个任务，拓扑排序能给出合法的执行顺序。这一类题胜在代码模板固定，多加练习就能快速写出。

5. 场景与业务题：算法岗不只是刷题

5.1 图像和音频基础题

B站作为视频平台，算法岗笔试出现图像和音频相关的选择题非常正常。第二套题里就涉及了一些基础概念。

Sobel算子是一种常见的边缘检测算子。它有两个卷积核，一个检测水平方向变化，一个检测垂直方向变化。用这两个核对图像做卷积，得到的是梯度分量，然后计算梯度幅值，从而判断当前像素是否处于边缘位置。原理上它属于一阶微分算子，对噪声比较敏感，所以实际使用时常先做高斯模糊再算Sobel，也就是常见的Canny边缘检测流程里的一个环节。

音频重采样算法解决的是“采样率转换”问题。比如一段录音的采样率是44100Hz，但项目需要把它转成16000Hz，这时候就要做重采样。简单粗暴的做法是线性插值，但会造成频谱混叠和高频失真；更专业的做法是使用sinc插值或者带抗混叠滤波器后重采样。B站客户端播放器、语音审核、视频转码等场景都会涉及音频重采样。

备这一类题不需要会手推公式，但要知道“为什么需要重采样”“直接插值会有什么问题”“工程上怎么处理更稳”。这比死记一个算法的实现细节更符合B站笔试的调性。

5.2 从BM25到推荐搜索场景题

搜索相关度的计算里，BM25是一个绕不开的排序公式。它综合考虑了词频（TF）、逆文档频率（IDF）和文档长度归一化。简单理解：一个词在文档中出现得越多，对相关度贡献越大；但词越常见（比如“的”“了”），IDF权重越小，避免常见词主导排序。BM25在小规模搜索场景下效果稳定，而且可解释性强，所以很多中小型系统都直接用BM25做召回或者粗排。

B站笔试场景题如果问“如何设计搜索排序策略”，可以这样回答：

• 召回阶段：BM25 + 向量召回 + 热门兜底，保证不遗漏。
• 精排阶段：用点击、播放时长、完播率等行为数据，训练一个模型，比如LR、GBDT或DNN。
• 重排阶段：做多样性打散、去重、内容质量过滤，避免用户看到一个列表全是同一个作者或者同一类视频。

这类题没有标准答案，关键看逻辑是否完整，能否从“用户需求”和“平台生态”两个角度同时思考。我当时准备场景题时，把B站的核心场景列了一遍：搜索、推荐、弹幕审核、视频去重、转码调度、内容理解。每个场景都整理了一套“问题定义-数据来源-算法选型-评估指标”的标准思路，笔试时就算遇到没见过的题，也能套用这个框架。

6. 备考建议与避坑指南

6.1 时间分配与做题顺序

B站算法岗笔试题量说不上大，但90分钟内要同时处理选择题和编程题，时间并不宽裕。我的建议是：

• 选择题控制在35到40分钟内，遇到不会的先标记，不要死磕。有些选择题本身就是在干扰你，投入太多时间反而影响后面的编程题。
• 编程题先读三遍题，想清楚输入输出格式再动手。很多错误不是算法本身，而是没搞懂“读一行还是读多行”“输出是否需要换行”。
• 先写暴力解法保住分数，再用剩下的时间优化。比如LIS先写O(n^2)的DP，如果时间充足再改二分版本。

做题顺序上，我习惯先做编程题，再做选择题。原因是编程题分值占比大，而且一旦进入状态，思路流畅的时候写代码效率最高。选择题如果放在后面时间紧张，蒙对的概率也比编程题高。

6.2 我踩过的坑和常见失误

说实话，我当年复习算法岗笔试时踩过不少坑。这里整理了一些高频问题，做一个速查表，供大家考前扫一眼。

在线笔试还有一个很隐蔽的问题：代码编辑器通常没有编译提示，手写完代码后最好能先在本地IDE验证一遍。如果平台支持“运行自测”，一定要用给的样例测一下。有些同学喜欢在脑子里编译，结果漏了分号或者写了中文括号，白白丢分。

另外，在线笔试环境里，输入输出格式的坑真的能让人崩溃。比如题目说“第一行一个整数T，表示有T组测试数据”，但你只处理了一组；或者说“字符串可能包含空格”，你用了cin >> s，读到空格就断了。这些细节在本地可能不会暴露，但在平台上就会导致0分。建议考前把各种输入方式练熟：getline、cin、scanf、按行读取等。

6.3 考前最后一周怎么准备

最后一周不建议再啃难题偏题，回归基础是最有效的。我自己的做法是：

• 每天手写一遍基础模板：快速幂、LIS、Dijkstra、并查集、滑动窗口、二分查找。
• 把排序算法的时间复杂度、稳定性表重新过一遍，重点理解不稳定排序的原因。
• 整理过往错题，尤其是KMP next数组、DP初始化这类容易在细节上出错的题。
• 刷一定量的选择题，主要集中在机器学习基础、数据结构、算法特性判断上，保持手感和反应速度。
• 把B站笔试常见的业务场景（搜索、推荐、内容理解）梳理成自己的话术框架。

这里特别想强调“手写模板”这件事。手写并不是让你背代码，而是让你在写的过程中重新理解每一步的逻辑。比如快速幂那两行 res = res * a % p 和 a = a * a % p，如果你能一边写一边说出为什么这么做，考场上就不会卡壳。

另外，考前可以专门训练一下“看题审题”的能力。拿到一道编程题，先不要急着敲代码，把题目里的关键词圈出来：输入范围、是否多组输入、是否要求严格递增、是否允许重复字符。这些关键词直接决定了算法选择和边界处理。我吃过一次亏，题目写的是“非严格递增”，我没注意，用了严格递增的判断，结果样例都过了但提交全错。

最后说点题外话

这套题我现在回头看，最大的价值不是题目本身，而是它传递出的一个信号：B站算法岗真正看重的是“基础是否扎实，能不能在限定时间内稳定输出”，而不是会不会背冷门公式。KMP、堆排序、快速幂、LIS、K-means、KL散度，这些东西在真实工作中可能不会每天都直接用，但它们构成了一个工程师判断问题、拆解问题、优化方案的底层能力。

我当时备考时最大的体会是：不要瞧不起“简单题”，更不要在“难题”上自我感动。把KMP的next数组推导熟练到30秒内能算完，把快排和堆排序的代码写到肌肉记忆，把滑动窗口和LIS的边界条件刻进脑子里，上考场的时候心里就有底了。与其焦虑笔试会不会出偏题，不如把基础题做到百分百稳。这一套配方，对B站适用，对其他大厂算法岗同样适用。