2019年秋招的B站算法卷我记得特别清楚。打开笔试链接的时候倒计时已经开始页面里同时塞了选择题、编程题和简答题量大且杂。有人以为算法岗笔试就是刷LeetCode结果一上来就被一道KMP next数组的手算题卡住后面动态规划的状态转移又没写完最后只能草草交卷。这套题其实很有代表性它不完全是刷题路子而是把经典算法、数据结构、机器学习基础和一个视频平台的技术直觉混在一起考。这篇文章就围绕这套题做一个完整复盘把每类考点的拆解思路、手算过程和代码模板都整理出来给准备校招算法岗的同学一个可复现的复习路径。1. 打开试卷先看什么这套题的整体结构与出题风格1.1 三块题型与应对节奏B站这套技术岗算法卷题型大致分成三块选择题、编程题、简答题总时长一般在两小时左右。选择题覆盖的范围很杂从数据结构、排序算法的时间复杂度到概率统计、机器学习基础概念都有编程题则是经典算法为主偶尔套一层业务背景简答题通常描述一个具体场景让你给出方案或者推导过程。我的建议是拿到试卷先把所有题目快速扫一遍标记出“一眼会”“需要想”“完全没思路”三类。优先写会做的编程题因为编程题分值最高且判分客观选择题控制在每题一分钟左右不会的先跳过简答题放到最后用剩余时间把思路写清楚哪怕不能完整实现也要写出关键步骤和公式评卷人通常会按点给分。1.2 B站出题偏好的两个信号从这套题能看出两个信号。第一个信号是“经典算法考得深但不过偏”比如KMP、堆排序、Dijkstra、快速幂这些都是数据结构与算法课程里的核心内容出题人考察的是你是否有扎实的基础而不是会不会冷门黑魔法。第二个信号是“会结合业务场景包装”比如用弹幕、推荐、视频转码来出题本质还是考经典模型但如果你能顺手点出业务含义分数会明显不一样。所以准备方向很清晰把LeetCode上高频题刷熟同时把《算法导论》里的基础章节过一遍尤其是字符串、图论和动态规划三大块。机器学习基础、图像处理的基础算子、控制算法的基础概念也要有个了解。接下来根据这套题的具体考点逐个拆解。2. 字符串题模式串abacaba的next数组手算也是一种能力2.1 next数组到底在算什么这道题一出现很多人的第一反应是懵。KMP大家都背过但让手算next数组很多人会漏掉定义差异。题目里明确写了next[i]的定义这里必须严格按题目给的版本走。常见的定义有两种版本Anext[i]表示模式串前i个字符组成的子串中最长相等真前后缀的长度next[0] -1next数组长度为模式串长度 1。版本Bnext[i]表示模式串p[0..i]这个前缀的最长相等真前后缀长度next数组长度与模式串长度相同。两种定义在代码上的偏移不一样但本质都是同一件事当前位置失配时模式串指针该回退到哪里。手算时最容易错的就是把两个版本混用。先按版本B来推因为更直观。模式串 p abacaba长度7。逐位计算i 0子串 a无真前后缀next[0] 0。i 1子串 ab前缀 a后缀 b不相等next[1] 0。i 2子串 aba前缀 a 后缀 a长度1next[2] 1。i 3子串 abac前后缀长度从3往下试aba vs bac 不等ab vs ac 不等a vs c 不等next[3] 0。i 4子串 abaca最长相等前后缀是 anext[4] 1。i 5子串 abacab试长度2ab abnext[5] 2。i 6子串 abacaba试长度3aba abanext[6] 3。所以按版本Bnext数组是 [0, 0, 1, 0, 1, 2, 3]。如果按版本A在开头补一个 -1则结果是 [-1, 0, 0, 1, 0, 1, 2, 3]这两种写进代码里都能工作关键是和失配时j next[j]的跳转逻辑保持一致。2.2 手工推导的三个技巧手算next数组有个比逐位硬试更快的技巧当计算next[i]时先看next[i-1]利用已经算出的结果。还是以 abacaba 为例算到 i 6 时前一位 next[5] 2说明子串 abacab 的前缀 ab 和后缀 ab 相等。此时新字符是 a而前缀 ab 后面的字符正好是 p[2] a相等所以 next[6] next[5] 1 3。如果不等就要回退到 next[next[5]]也就是 next[2] 1再比较。这个“利用上一步结果”的思路其实就是KMP构造next数组的DP本质。笔试时如果时间紧可以直接在纸上用这个递推法比暴力比较快得多也不容易漏。2.3 KMP代码与常见的错位问题用手算题对照代码来理解更好。下面是版本B的KMP匹配代码#include bits/stdc.h using namespace std; vectorint buildNext(const string p) { int m p.size(); vectorint next(m, 0); for (int i 1, j 0; i m; i) { while (j 0 p[i] ! p[j]) j next[j - 1]; if (p[i] p[j]) j; next[i] j; } return next; } int kmpSearch(const string s, const string p) { vectorint next buildNext(p); int n s.size(), m p.size(); for (int i 0, j 0; i n; i) { while (j 0 s[i] ! p[j]) j next[j - 1]; if (s[i] p[j]) j; if (j m) { return i - m 1; // 匹配起始位置 } } return -1; }这段代码里next[j-1]是很多人的坑。因为上面求next数组时next[i]表示的是p[0..i]这个前缀的最长相同前后缀长度长度本身是“最后那个位置的下标 1”所以回退时要用next[j-1]。如果你用的是版本Anext[0] -1那种回退逻辑就变成j next[j]两者不能混用。笔试时如果这道题要求写完整KMP我会建议直接写版本B因为和前缀函数的概念一致面试官看起来也更舒服。手算题则先确认题目给的next[i]定义再决定要不要在开头补 -1。2.4 这道题在真实业务中怎么用KMP在B站这类视频平台的典型用处是敏感词过滤和弹幕关键词匹配。一个用户发了一条弹幕需要快速判断里面是否包含某个违规词不可能对每个词都调一次字符串查找的库函数而是把所有违规词建成一个AC自动机KMP的多模式扩展一次扫描就能命中所有词。理解单模式KMP再理解AC自动机就是在Trie树上做KMP的失败指针跳转会顺畅很多。3. 排序与数据结构堆排序之外还要能讲清楚取舍3.1 排序算法的选择逻辑这套题的选择题部分几乎必然会考排序。常见题型是给你一个场景问你选哪种排序或者直接问时间复杂度、稳定性。比如数据量小且基本有序插入排序最合适O(n)最好情况常数极小。数据量大且要求稳定归并排序O(n log n)稳定但需要额外O(n)空间。数据量大且不要求稳定快速排序平均O(n log n)常数小。需要实时求TopK堆排序或者直接用堆这个数据结构。数据范围有限比如成绩0到100计数排序可以做到O(n)。笔试里常出现的一个细节是“快速排序的最坏情况”。如果每次选的基准都是当前区间最小或最大值快排会退化成O(n^2)所以现代工程实现里会用三数取中或随机选基准。这道题如果问“以下哪个排序在最坏情况下时间复杂度最优”答案通常是堆排序或归并排序不是快排。3.2 堆排序裸写模板编程题偶尔会要求手写堆排序或者用它解决TopK问题。堆排序的代码容易在调整堆时出错我建议背一个固定模板void heapify(vectorint nums, int n, int i) { int largest i; int l 2 * i 1, r 2 * i 2; if (l n nums[l] nums[largest]) largest l; if (r n nums[r] nums[largest]) largest r; if (largest ! i) { swap(nums[i], nums[largest]); heapify(nums, n, largest); } } void heapSort(vectorint nums) { int n nums.size(); for (int i n / 2 - 1; i 0; i--) heapify(nums, n, i); for (int i n - 1; i 0; i--) { swap(nums[0], nums[i]); heapify(nums, i, 0); } }注意几个易错点建堆的起始位置是n/2 - 1不是n-1堆排序升序排序建的是大顶堆heapify里每次要和两个子节点都比较不是只比一个递归调用时n要传当前堆的大小而不是数组总大小。这四点是笔试手写堆排时最常见的扣分点。3.3 从排序到TopK笔试里的隐藏题B站这套题里有一类题不会明说“TopK”但会给一个场景比如“上亿条视频播放日志要找出播放量前100的视频怎么做”。正确思路不是全量排序而是维护一个大小为100的小顶堆遍历一遍把大于堆顶的元素替换进去。时间复杂度O(n log k)空间O(k)。如果进一步问“内存不够装下全部数据怎么办”就可以说用外部排序 堆的经典组合或者使用类似MapReduce的分布式思路在每台机器上算局部TopK再归并。这道题考的不是堆排序本身而是你是否懂得在大数据场景下避免不必要的全量排序本质上是对“排序成本”的理解。4. 图论题Dijkstra是底线二分图是加分项4.1 优先队列Dijkstra的模板与边界图论在B站算法卷里出现频率不低Dijkstra算是最常考的单源最短路算法。笔试如果出Dijkstra通常会给一个非负权图问你从源点到各点的最短距离或者让你写算法实现。优先队列版本是必须掌握的vectorint dijkstra(vectorvectorpairint,int graph, int src) { int n graph.size(); vectorint dist(n, INT_MAX); dist[src] 0; priority_queuepairint,int, vectorpairint,int, greaterpairint,int pq; pq.push({0, src}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (d dist[u]) continue; for (auto [v, w] : graph[u]) { if (dist[u] w dist[v]) { dist[v] dist[u] w; pq.push({dist[v], v}); } } } return dist; }这里比较隐蔽的坑有三个一是图中节点编号从0还是从1开始这决定graph的初始化大小和返回时的下标调整二是优先队列默认是大顶堆要传greater来变成小顶堆三是dist更新的判断条件一定是dist[u] w dist[v]不要写成dist[v] dist[u] w之后漏掉更新。三个坑都避开这题基本稳了。4.2 二分图匹配从匈牙利到HK二分图的题在互联网公司笔试里属于中等偏上的难度但B站作为内容平台确实会考这类模型。热搜词里出现“二分图 hk算法”说明很多人对匈牙利算法和Hopcroft-Karp算法的区别有疑问。简单说匈牙利算法是每次找一个增广路O(VE)HK算法是先通过BFS构建分层图再用DFS找多条不相交增广路最坏O(E sqrt(V))。笔试中如果考到大概率是考二分图判定染色法或者最大匹配数。判断二分图用BFS染色即可颜色只有0和1两个值bool isBipartite(vectorvectorint graph) { int n graph.size(); vectorint color(n, -1); queueint q; for (int i 0; i n; i) { if (color[i] ! -1) continue; color[i] 0; q.push(i); while (!q.empty()) { int u q.front(); q.pop(); for (int v : graph[u]) { if (color[v] -1) { color[v] color[u] ^ 1; q.push(v); } else if (color[v] color[u]) { return false; } } } } return true; }如果考最大匹配不会让你在笔试里从零写HK而是给你一个场景让你抽象成二分图然后说用匈牙利或HK求解。关键在于看出“左右两边是两类不同对象”这个结构。比如视频和用户的分发关系、视频审核任务与审核人力分配本质上都是二分图匹配。4.3 图算法在视频推荐里的落点B站推荐系统的候选召回和粗排里图算法用得非常多。用户看视频会产生一个用户-视频二部图之后可以基于Graph Embedding做游走和表示学习在最短路这个层面视频之间的相关跳转可以抽象成一张有向带权图线上的视频转码资源调度也可以建模成图的最短路径或流问题。笔试里考Dijkstra不只是考你会不会堆优化也在看你能不能把一个业务场景抽象成图并选择正确算法。做题时多想一想这个题在公司实际业务中对应什么场景面试环节讲项目时会有很大优势。5. 动态规划与快速幂把送分题变成稳拿题5.1 一看状态转移二看边界条件动态规划是每一场算法笔试的重头戏B站这套题也不例外。编程题里通常至少有一道DP比如最长上升子序列、01背包、编辑距离这类经典题。我被问过一个很典型的DP题给一个数组求连续子数组的最大和。这题虽然简单但很多人状态定义搞不清楚。正确做法是令dp[i]表示以第i个元素结尾的最大子数组和那么dp[i] max(dp[i-1] nums[i], nums[i])答案就是dp数组里的最大值。如果一时没反应出来可以用“到当前为止的子数组和 是否重新开始”来理解本质上是两个选择把当前元素接在前面的连续段后面或者从当前元素重新开头。更复杂的DP题状态转移会更长但笔试常见的坑集中在边界条件。比如二维DP的dp[0][j]和dp[i][0]要不要初始化、循环从0还是1开始、最终答案是dp[n]还是dp[n][m]这些细节比状态转移方程更容易丢分。我的建议是每次写完DP后手动代入一个最小用例去跑一遍边界。5.2 快速幂的位运算写法这套题的选择题或编程题里可能出现快速幂尤其是某些组合数、模运算的题目会用到。快速幂的核心思想是把指数按二进制拆解边遍历边累乘。一个在模意义下的模板long long fastPow(long long a, long long b, long long mod) { long long res 1; while (b 0) { if (b 1) res res * a % mod; a a * a % mod; b 1; } return res; }要注意的地方是a和res的类型在乘法过程中可能溢出最好用long long取模的mod如果是质数还可以和费马小定理结合用来求逆元。这里最容易犯的错是把模运算放到最后导致中间结果溢出正确做法是乘法过程中每一步都取模。5.3 贪心还是DP出题人留的陷阱很多题目看起来可以用贪心但实际上要DP比如“给定一个数组求最大子序列和不一定连续”这类就要求先排序再判断和连续子数组的解法完全不同。做题时如果发现贪心策略需要额外假设比如“当前选择不影响后续”就要警惕是不是要用DP。简单区分方法贪心是每步做局部最优DP是通过状态转移保留所有可能的较优解最后统一取最优。笔试里如果拿不准优先写DP因为给出状态转移和边界条件后证明复杂度也更清晰。另外快速幂经常和DP算法结合出现在矩阵快速幂优化线性递推题里比如斐波那契数列第n项n达到10^18时不能用O(n)递推要用2x2矩阵的快速幂。这类题如果出现在选择题里考察点通常是“时间复杂度是什么”而不是要求实现复习时知道这个套路就够了。6. 机器学习与控制类考点算法岗的“非LeetCode”成分6.1 聚类算法K-Means及其初始化B站算法岗笔试题里机器学习相关内容占比不低。选择/简答里常见聚类算法考察热搜词里的“聚类算法”指向这一点。最基础的是K-Means随机选K个初始质心或K-Means。每个样本归属到距离最近的质心。重新计算每簇的质心。重复直到质心变化小于阈值。简单题会这样出“K-Means一定能收敛到全局最优吗”答案是否定的它只能保证收敛到局部最优且结果受初始化影响很大。改进方案有K-Means按距离加权概率选初始中心让初始质心尽量分散再有就是高斯混合模型GMM配合EM算法。这一块在笔试中不需要你推导太深的数学但要把基本流程和优缺点讲清楚。如果把K-Means和B站业务联系起来常见场景是用户画像分群、视频内容聚类。比如给用户行为特征做归一化然后用聚类把用户分层后续再做个性化运营。回答简答题时能提到“特征标准化”和“K值选取”这两个关键点会显得更专业。6.2 图像锐化的拉普拉斯算子热搜词里还有“图像锐化的拉普拉斯算法”这也是B站这类视频平台可能会考的计算机视觉基础题。拉普拉斯算子是一种二阶微分算子用于强调图像中的灰度突变区域。常见的卷积核是0 -1 0 -1 4 -1 0 -1 0或者包含对角线的版本-1 -1 -1 -1 8 -1 -1 -1 -1锐化的公式是输出图像 原图 拉普拉斯算子的卷积结果。因为拉普拉斯提取的是边缘和高频信息把它加回到原图上就能让边缘更加突出。实际代码中要注意卷积核的和要为0否则输出会整体变亮或变暗另外像素值需要截断到0到255范围不能溢出。这些细节在选择题中出现频率很高。如果要更深入还会考到高斯滤波和高斯拉普拉斯LoG或者对比Sobel算子和拉普拉斯算子的区别。Sobel是一阶导数对噪声敏感度较低拉普拉斯是二阶导数对噪声更敏感所以实际中通常先高斯模糊再用拉普拉斯。这类题出现在算法岗笔试里主要看你有没有基本的图像处理常识。6.3 PID、模拟退火、粒子群这类“杂学”怎么复习这套题的选择题里还可能出现PID算法、模拟退火、粒子群算法、剪枝算法、FOC算法、MPPT算法等概念。这些内容很杂但考察方式基本都一样只问你“基本原理或应用场景”不要求深究内部推导。复习时可以用一个方法每类算法只记三件事——是什么、解决什么问题、典型应用场景。比如PID通过比例、积分、微分三个环节进行闭环控制用于无人机飞控、电机调速、温度控制。模拟退火基于物理退火过程的随机搜索算法用于求解组合优化问题允许以一定概率接受更差解来跳出局部最优。粒子群模拟鸟群觅食行为的群智能优化算法用于连续函数优化、神经网络参数调优。剪枝算法在搜索树中提前排除不可能产生最优解的分支常用于博弈树搜索和决策树构建。RetE算法规则引擎中的高效模式匹配算法通过构建网络结构来减少规则匹配时的重复计算。出现这些考点说明一个趋势算法岗笔试除了LeetCode也在考察候选人的知识广度。看到不会的题不要慌用已有的机器学习/控制论常识去猜一个最合理的答案正确率往往比空着高很多。7. 复盘与实战笔试当天的时间分配与代码习惯7.1 两小时怎么分配综合看下来这套卷子的整体难度属于中等偏上但时间很紧张。比较合理的分配方式是前5分钟通读全部题目标记难度先不急着做任何一道题。前40分钟完成所有一眼就会的选择题并尽力完成第一道编程题。第40到80分钟专注第二道编程题和较难的选择题第二道编程题即使写不完全也要写出核心代码框架。最后40分钟回头补遗漏的选择题处理简答题重点把思路、公式、步骤写清楚。这样分配的原因是编程题分值权重高且通常需要思考和调试不能放到最后赶简答题虽然长但按点给分只要写对关键词就有分比死磕难题划算。7.2 四个最容易扣分的细节我见过好几个人笔试代码写对了却因为边角细节扣掉大分。以下四个点每次笔试前都要默念一遍边界条件数组为空、n等于1、图不连通、字符串含空串等都要在代码里显式处理。类型范围涉及乘法、加法累加的变量用long long不要用int去赌它不溢出。下标起点题目给的编号是从0开始还是从1开始一定要看清楚。很多Dijkstra和DP题就栽在这里。输出格式要换行、要打印下标还是打印值、保留几位小数这些细节最容易扣分且毫无技术含量。7.3 从笔试到面试的一道题闭环笔试之后往往紧接着面试面试官可能会拿着你笔试的代码问你“你觉得这个代码还有什么可以优化的地方”最好的准备方式是在笔试过后把每道做过的题重新做一遍并补上复杂度分析、边界条件讨论和优化思路。做完一道题之后可以顺手问自己三个问题时间复杂度和空间复杂度是多少如果数据规模扩大10倍这个解法还行不行如果题目条件改一个地方解法会怎么变这套题里出现过的KMP、堆排序、Dijkstra、快速幂、K-Means、拉普拉斯锐化每一个都可以作为面试深挖的起点。比如KMP之后可能会问AC自动机堆排序之后可能会问外部排序Dijkstra之后可能会问A*算法快速幂之后可能会问矩阵快速幂和线性递推。把笔试题目扩展成一张知识点网络才是这类套题最大的价值。7.4 关于真题的一套复习闭环如果你也想拿这套题练手我建议按这个顺序来先限时做一遍真题统计每类题型的正确率再把错题对应的知识点整理成清单逐个补基础然后回到LeetCode上把对应标签的中等题刷一遍最后重新做一遍原题看能否在更短时间内完成。这样一轮下来比盲目刷300道题效率要高得多。我个人在准备秋招那会儿是把每一套笔试题都当成一次小型面试来对待的做完之后写复盘笔记记录卡壳点、错误原因和优化方案。这套方法后来带校招生时也验证过能把一套真题吃透的人笔试成绩通常都不会差。希望这份复盘能帮你少走一些弯路。
