B站算法岗笔试复盘：KMP、堆排序与动态规划高频考点详解

2019年秋招季我坐在电脑前打开B站技术岗算法的在线笔试链接。第一套笔试题的倒计时是120分钟页面上混着选择题和编程题。做完之后我的第一感受是这套题没有偏题怪题全是高频经典考点但题量密集稍不留神就会在基础细节上翻车。后来很多朋友问我要复盘我断断续续整理了很久这篇就把核心考点和手算过程完整展开希望能帮到正在准备算法岗笔试的人。这套题适合谁看如果你是投递算法工程师、推荐算法、音视频算法的应届生或者只是想检验自己数据结构与算法基本功的开发者都可以用这篇作为模拟练习。具体到题目本身KMP的next数组、堆排序、01背包、KL散度相关概念都出现了覆盖面和B站技术栈有很强关联。提示不同渠道流传的题目版本可能略有差异next数组定义更是五花八门。我会把遇到的版本讲清楚并说明不同定义之间的差异避免你因为定义不一致而丢分。1. 这套题给我的整体印象高频考点密度极高1.1 考点分布不算意外但手算占比很高先明确一个判断这套算法笔试题和坊间流传的大厂必考LeetCode原题不太一样。它更偏向基础、偏手算、偏经典。题型按占比排大概是数据结构与算法约65%机器学习/深度学习基础约20%数学与逻辑题约15%。选择题里有不少需要当场手算的题比如 KMP 的 next 数组、堆排序的调整次数、快速排序的某轮划分结果。这类题在 LeetCode 上很少碰到但在B站这类公司的笔试题里非常实用尤其在推荐、搜索等算法岗位后续面试中也会被追问。B站作为内容社区算法岗主要分布在推荐、搜索、音视频和风控方向。所以笔试题不会只考纯粹的 LeetCode还会带一点机器学习概念题。但要注意即使机器学习题占分不多也不能直接放弃因为这一部分往往是笔试分数拉开差距的地方。选择题十几道编程题三到四道每一道的分值都不小。1.2 编程题风格题干短边界条件多编程题风格给我最深的印象是题干短、边界多。比如快速幂题目可能只有一句话计算 a^b mod m。但如果你没处理 b0、a 很大、m1 这种情况就会漏分。又比如01背包问题题目会故意把物品价值和重量写成很大诱导你用 int 而不用 long。这些都是真实的得分点。所以后来我提醒自己写完代码一定要主动列一遍边界条件不要等测试用例来暴露问题。在线笔试的编译器往往只给出有限的报错信息边界条件只能靠自己在脑子里过。我总结了一个固定检查顺序先看输入范围再看是否可能为空值再看是否可能溢出最后再跑一遍示例。这个顺序在多家公司的笔试中都帮我提前发现了问题。1.3 和同批次互联网公司笔试的横向对比我参加过那一年好几家公司的算法岗笔试横向对比看B站这套题的难度不是最难的但覆盖面很稳。字节跳动、快手的题明显更偏工程和代码量B站第一套题则更像是算法基础能力验收。如果你刷 LeetCode 只刷 medium 和 hard 原题反而容易忽略这种手写基础算法的能力。我印象里有几个周围同学就是在选择题的手算环节浪费了太多时间导致后面编程题没写完。这是一个很典型的失败路径。所以后来我在准备笔试时会刻意把手算题单独拿出来练。LeetCode 可以帮你提高编码手感但手算 KMP、手算排序过程、手推反向传播梯度的能力必须靠专项训练。B站这套题就是很好的专项训练材料。2. KMP的next数组一道经典手算题拆给你看2.1 原题与定义还原网上流传最广的一道题是对于模式串 p abacaba求其 next 数组。next[i] 在不同资料里有两种常见定义定义Anext[i] 表示 p[0:i] 这个子串中最长相等前缀后缀的长度下标从0开始允许 next[0] 0。定义Bnext[i] 表示前 i 个字符组成的子串的最长相等前后缀长度i 从1开始。这套题选用了哪种定义直接影响答案的表示方式但计算逻辑完全相同。我按定义A来讲同时给你换算思路。关键点最长相等前缀和后缀必须严格短于当前子串本身不能直接把整个子串既当前缀又当后缀。比如子串 abacaba你不能说最长相等前后缀长度是7因为失配时跳转没有任何意义。2.2 逐位手算abacaba 的完整过程按照定义Anext[i] 对应长度为 i1 的子串 p[0:i]。我拆成长度视角来计算长度1子串 a只有一个字符没有严格短于自身且相等的前后缀长度为0。next[0]0。长度2子串 ab前缀只能取 a后缀只能取 b不相等长度为0。长度3子串 aba候选长度1时前缀 a后缀 a相等候选长度2时前缀 ab后缀 ba不相等。所以最长相等前后缀长度为1。长度4子串 abac候选长度1前缀 a后缀 c候选长度2前缀 ab后缀 ac候选长度3前缀 aba后缀 bac。都不相等所以是0。长度5子串 abaca候选长度1前缀 a后缀 a相等候选长度2前缀 ab后缀 ca候选长度3前缀 aba后缀 aca候选长度4前缀 abac后缀 baca。只有长度1满足所以是1。长度6子串 abacab候选长度1前缀 a后缀 b候选长度2前缀 ab后缀 ab相等候选长度3前缀 aba后缀 cab候选长度4前缀 abac后缀 acab再看更长也不成立。所以最长是2。长度7子串 abacaba候选长度1前缀 a后缀 a相等候选长度2前缀 ab后缀 ba候选长度3前缀 aba后缀 aba相等候选长度4前缀 abac后缀 caba候选长度5前缀 abaca后缀 acaba候选长度6前缀 abacab后缀 bacaba。最大相等长度是3。因此定义A下得到 next [0, 0, 1, 0, 1, 2, 3]。如果题目用的是从1开始编号的 next[1..7]同样得到 [0, 0, 1, 0, 1, 2, 3]只是下标含义不同。如果用的是失配指针版本即 next[0] -1 的大学教材风格那么数组会变成另一种形式。这里特别提醒不同版本之间不是简单的整体减一必须严格看题面给出的 next 定义。我在笔试时养成的习惯是先看题目有没有给示例如果给了就用示例验证自己的定义如果没有给就按最长相等前后缀长度这个最通用定义来答。2.3 为什么会在这里丢分我自己复盘时发现KMP next数组的错误集中在四个地方第一把候选长度从1开始枚举忽略了严格短于当前子串这个限制导致算出来的 next[6] 变成7。第二把回文串思维带进来看到 abacaba 对称就以为 next 会对称实际上 next 数组并不要求对称。第三把 next 和 nextval 混淆。nextval 是在 next 基础上做进一步压缩当 p[j] p[next[j]] 时继续向前跳转。题目如果问 nextval答案会完全不同。第四输出格式问题有的题要求不带逗号连续输出比如 0010123有的要求带逗号或下标说明答错格式也会扣分。我考场上用的是逐位画前缀后缀表的办法。不建议心算时间允许就画一个7行的表格每一行写当前子串的候选前缀和后缀再逐项比较。这种办法看起来笨但准确率极高。在线笔试的记事本或草稿纸上完全来得及画。3. 排序与堆基础题里最容易被忽略的边界3.1 排序算法复杂度横向对比B站这套题的选择题部分排序算法是常客。下面这个表建议直接背下来排序算法最好时间复杂度平均时间复杂度最坏时间复杂度空间复杂度稳定性冒泡排序O(n)O(n^2)O(n^2)O(1)稳定插入排序O(n)O(n^2)O(n^2)O(1)稳定选择排序O(n^2)O(n^2)O(n^2)O(1)不稳定快速排序O(n log n)O(n log n)O(n^2)O(log n)不稳定归并排序O(n log n)O(n log n)O(n log n)O(n)稳定堆排序O(n log n)O(n log n)O(n log n)O(1)不稳定记忆技巧稳定的排序算法只有冒泡、插入、归并。选择排序和堆排序都是选一个放到最终位置快排由于 partition 交换跨距离都不稳定。选择题如果问下列哪些排序算法在最坏情况下时间复杂度不是 O(n^2)答案就是归并、堆。如果问额外空间最少的 O(n log n) 算法答案是堆排序。这些考点在B站笔试题里几乎年年都有变体。3.2 手写堆排序的三个易错点编程题如果考排序B站喜欢让手写堆排序或者快排。堆排序高频易错点集中在三处。第一建堆方向。升序排序必须建大根堆很多人惯性写小根堆结果排出来是降序改半天才发现。第二最后一个非叶子节点的下标是 n/2 - 1数组0基不是 n/2。第三下沉操作时要同时比较左右孩子并选择较大的孩子交换。如果只和左孩子比较遇到右孩子更大时就会漏。我贴一段可以快速背诵的 Java 版本public void heapSort(int[] nums) { int n nums.length; // 建堆从最后一个非叶子节点开始下沉 for (int i n / 2 - 1; i 0; i--) { siftDown(nums, i, n); } // 逐个取出堆顶 for (int i n - 1; i 0; i--) { swap(nums, 0, i); siftDown(nums, 0, i); } } private void siftDown(int[] nums, int root, int size) { while (2 * root 1 size) { int child 2 * root 1; if (child 1 size nums[child 1] nums[child]) { child; } if (nums[root] nums[child]) { swap(nums, root, child); root child; } else { break; } } }注意第二层循环的 size 是当前待排序区间长度已经交换到末尾的元素不参与调整。这是每轮排序后重新下沉的前提。如果你笔试时用了递归写法注意递归深度不会超过 log n一般没问题但迭代写法的边界更好控制。3.3 快排的 partition 为什么不能乱写快排的 partition 有很多写法推荐背一种不容易越界的Lomuto 分区。基准取最后一个元素i 指向小于基准区间的末尾j 遍历前 n-1 个元素。代码很短int partition(int[] nums, int l, int r) { int pivot nums[r]; int i l; for (int j l; j r; j) { if (nums[j] pivot) { swap(nums, i, j); } } swap(nums, i, r); return i; }这种写法核心是 i 指针先指向边界遇到比基准小的元素就交换最后把基准放到 i 的位置。笔试时如果你用这种写法至少不会因为 while 循环边界写错而死循环。如果题目要求输出第一趟排序后的数组那就必须手动模拟不能依赖代码。模拟时要注意快排每趟把基准放到最终位置基准左右两侧分别小于、大于基准但左右内部不一定有序。4. 动态规划与贪心从背包到区间问题4.1 为什么算法岗笔试离不开背包动态规划在B站算法岗笔试中几乎是必考的。原因很直接推荐系统、视频调度、广告排序里大量问题都能抽象成资源分配背包问题是理解资源分配最基本的模型。第一套笔试题里的编程题据我回忆有一道就是物品重量价值加容量限制求最大价值。这种题看似简单但错误率并不低主要集中在初始化、一维数组遍历顺序、容量边界。01背包的标准状态转移dp[i][j] max(dp[i-1][j], dp[i-1][j - w[i]] v[i])i 是前 i 个物品j 是当前背包容量。第 i 个物品不取或取取的时候要确保 j w[i]。二维版本很直观但笔试要求空间通常用一维滚动数组。def knapsack(N, W, w, v): dp [0] * (W 1) for i in range(N): for j in range(W, w[i] - 1, -1): dp[j] max(dp[j], dp[j - w[i]] v[i]) return dp[W]关键点是内层循环必须倒序。为什么因为一维 dp 覆盖的是上一轮状态如果正序遍历j 从小到大更新后面的 j 可能使用到同一轮已经更新过的 dp[j - w[i]]等于允许一个物品被选多次这就是完全背包的行为。01背包要的是每个物品最多选一次所以必须倒序遍历保证 dp[j - w[i]] 还是上一轮的结果。这个区别笔试选择题非常爱考。如果题目改成完全背包只需要把内层循环改成从小到大的正序遍历。4.2 贪心算法区间调度问题贪心算法在B站笔试题里也出现过最常见的是会议室/活动安排给一组活动开始和结束时间求最多能安排多少个不冲突的活动。解法是先按结束时间升序排序然后贪心地选最早结束且不与之前选中的活动重叠的活动。为什么按结束时间排序而不是按开始时间因为结束早能为后续留下更多时间这是贪心选择性质的直观体现。从证明角度说假设最优解里第一个选中的活动不是结束最早的那个那么把最优解的第一个活动替换成结束最早的活动不会与后续活动冲突因为最早结束活动的结束时间不晚于原最优解第一个活动的结束时间而原最优解第二个活动的开始时间一定不早于第一个活动的结束时间。所以替换后仍然合法。这就是贪心算法最核心的贪心选择性质。笔试题不要求严格形式化证明但选择题可能会问贪心策略的证明方法是什么要能写出贪心选择性质 最优子结构。如果只写按结束时间排一下而不讲为什么在面试追问中很容易露馅。4.3 状态压缩 DP 的速成模板如果你时间充裕建议把状压 DP 的模板背下来。B站第一套题有没有考状压我印象不深但同届技术岗的题库里有。状压 DP 常用于棋盘摆放、集合覆盖等小规模问题。核心是用一个 int 的每一位表示集合中某个元素是否被选取例如 dp[mask] 表示当前选取集合为 mask 时的最优值。状态转移通常是枚举下一个加入的元素for mask in range(1 n): for i in range(n): if mask (1 i) 0: nmask mask | (1 i) dp[nmask] min(dp[nmask], dp[mask] cost[mask][i])这种题 n 一般不超过 20因为 2^n 一旦太大就会超时。遇到集合很小、求排列最优的题目优先往状压 DP 上想。背模板的时候一定要理解为什么外层是 mask内层是元素。如果反过来会导致重复状态的引入逻辑混乱。5. 机器学习与深度学习基础算法岗笔试的第二阵地5.1 KL散度与ELBO的关系B站2019秋招的时候深度学习已经在笔试里频繁出现。这套题的选择部分有一道让我印象很深问 KL 散度是否为距离度量。答案是它不是距离因为不具备对称性也不满足三角不等式。KL 散度定义为KL(P||Q) Σ P(x) log(P(x)/Q(x))它衡量的是用 Q 分布去近似 P 分布时损失的信息量。由于 log 里的 P/Q 和 Q/P 不相等所以 KL(P||Q) 不等于 KL(Q||P) 一般成立。这一特性在 VAE 的推导里很关键因为 VAE 要优化的是证据下界 ELBO而不是直接优化对数似然。ELBO 的常见形式log p(x) ≥ E_{q(z|x)}[log p(x|z)] - KL(q(z|x) || p(z))这个式子左边是真实数据分布下的对数似然右边第一项是重构误差第二项是隐变量后验与先验的 KL 散度。最大化 ELBO就是在最小化重构误差和隐变量分布差异之间取一个平衡。B站算法岗如果涉及视频生成、图像生成这类概念是必问的。即使笔试题只考定义你也要能写出公式并且说清楚每一项的含义。5.2 反向传播手算题链式法则的考场应用机器学习基础题里反向传播是另一类高频题。最简单的例子是复合函数f (a b) * (b c)给定 a 1, b 2, c 3求 ∂f/∂b。令 u a bv b cf u * v。那么∂f/∂b v * ∂u/∂b u * ∂v/∂b (b c) * 1 (a b) * 1 5 3 8这类题在笔试卷上不是靠 numpy 算的你必须手推。如果遇到多层的比如 h1 W1·x b1, a1 sigmoid(h1), h2 W2·a1, loss MSE(h2, y)那就要一步步算梯度先算 ∂loss/∂h2再算 ∂h2/∂a1再算 ∂a1/∂h1最后得到 ∂loss/∂W1。考场时间有限建议把链式法则框架写清楚不要直接写结果。我习惯在草稿纸上画出计算图标出每个中间变量再沿着反向路径求梯度这样不容易漏项。5.3 一些容易被忽视的机器学习概念除了 KL 散度聚类、KNN、决策树、集成