我当年秋招的时候算法岗的笔试基本就是一场“盲人摸象”——你永远猜不到出题人会从哪个犄角旮旯里扒出一道题来。B站这套2019秋招技术岗算法第二套笔试题我在网上翻到过不少讨论帖这次结合题目本身和热门考点词重新梳理一遍完整思路。本文不贴官方答案也没人真有完整版但我会把每类题型背后的考察意图、解题切入点、最容易踩的坑全部拆开揉碎讲清楚你要是正在备战算法岗笔试这篇可以直接当“错题本复习提纲”用。1. 这套题到底在考什么先看清楚出题人的底牌很多人拿到笔试题就开始闷头刷题这是大忌。算法岗笔试和竞赛刷题不一样它本质上是公司在短时间内完成“筛选”和“排位”两个动作的工具。筛选的是“有没有基本代码能力”排位的是“在同等能力的人里谁更接近我们团队的日常业务”。看到“哔哩哔哩2019秋招技术岗算法第二套”结合当年的招聘节奏我判断这套题的重点模块分布大致是数据结构与基础算法35%-40%、机器学习/深度学习理论基础20%-25%、数学与概率统计10%-15%、编程题25%-30%。别小看这个比例它直接决定了你的复习优先级。整套题的核心逻辑可以概括为三句话数据结构是骨架。KMP、排序、贪心、堆、二分这些是基本盘不要求你达到ACM水平但至少要做到“听名字就知道思路上手能十分钟写出来”。算法岗的“算法”二字指向的是“机器学习算法”。这也是B站这类内容平台比较特别的地方它不像Google那样考特别深的系统设计也不会像某些银行IT一样考大量SQL而是会围绕推荐、审核、内容理解这些业务场景去考察你懂不懂模型原理、会不会调参、知不知道评估指标的坑。编程题真正考的是“把模糊问题变成清晰步骤”的能力。不是考你会不会某个冷门数据结构而是考你在有限时间里能不能把思路完整落地成能跑的代码。所以你要是只会刷LeetCode而机器学习基础一塌糊涂或者理论背得滚瓜烂熟但手写代码就卡壳这套题都会让你很难受。它要求的是“两条腿走路”而且两条腿都不能太短。2. 数据结构与基础算法KMP、排序、贪心、二分到底怎么考2.1 KMP的next数组背了十遍做题照样错一看到热搜词里有“在KMP算法中对于模式串pabacaba其next数组”我就知道这类题是B站笔试的常客。KMP本身在实际业务里用得并不多但它是考察“你懂不懂前缀函数本质”的一个经典试金石。出题人不可能指望你上生产环境去写一个字符串匹配算法但你要是连next数组都算不对他会怀疑你的基本功。先把这个例子讲透。模式串 p abacaba下标从0开始长度7。next数组在B站这套题里应该指的是**“当前字符不匹配时模式串应该回退到的位置”**也就是常用的next[i]表示“p[0..i]的前缀中最长的相等前后缀长度”。要注意这里不是每个版本的KMP定义都完全一样有的地方next数组第一位是-1有的地方第一位是0所以审题一定要仔细看它给出的定义。按最主流的定义next[i] 以i结尾的子串的最长相等前后缀长度前后缀不包括子串本身来算下标 i字符子串p[0..i]最长相等前后缀长度next[i]0aa0无真前后缀01bab002aaba1前缀a后缀a13cabac004aabaca115babacab2abab26aabacaba3abaaba3第二套卷子如果考的是next数组大概率会在“前后缀不能包含整个子串”这个细节上设坑很多人会把next[6]写成7因为整个子串和自身相等这就是基本功不扎实的表现。在KMP匹配过程中当主串字符和模式串字符不匹配时模式串向右移动的位数 已匹配的字符数 - 对应的失配字符的next值。这个公式也要记住。比如在主串里匹配到某个位置失配时如果你已经匹配了5个字符而失配位置对应的next值是2那么模式串应该右移3位继续比较而不是一位一位往后挪。理解这个移动过程比背代码更重要因为笔试很可能会给你一个具体的主串和模式串让你手算匹配过程中的比较次数。2.2 排序算法与复杂度的极限拉扯数据结构排序算法这类题在B站2019秋招的笔试题里属于“送分但不完全送分”的模块。送分是因为人人都会背快排和归并的复杂度不送分是因为它考得细比如排序算法的稳定性哪些排序是稳定的哪些不稳定稳定排序意味着相等元素的相对顺序不改变。冒泡、插入、归并是稳定的选择、快排、堆排是不稳定的。这个点经常和“实际业务中按多个字段排序的需求”结合考。堆排序建堆的时间复杂度很多人以为建堆是O(nlogn)其实是O(n)。证明思路是每一层的节点数乘以该层高度最终求和的结果是O(n)。如果让你手写建堆过程注意从最后一个非叶子节点开始向下调整。快排的最坏情况当数组已经有序升序或降序时如果每次选第一个元素作为pivot快排会退化成O(n²)。这也是为什么实际工程里会用“三数取中”或者随机选pivot来避免这种极端情况。外部排序如果数据量超过内存能容纳的范围比如要对一个10GB的文件排序而内存只有1GB就需要用到外部排序。它的核心思想是“分块排序多路归并”考察归并排序在海量数据场景下的应用。我的建议是不要只看理论复杂度要把每种排序的代码手写一遍至少写三遍。第一遍照着书抄第二遍合上书自己默写第三遍边写边说出每一步在干什么。这样到笔试时就算紧张手也有肌肉记忆了。2.3 贪心算法证明比算法本身更重要贪心算法在B站这套题里出现的概率很高原因有二一是它写起来代码量少适合笔试这种限时场景二是贪心算法真正的难点不在算法而在“证明这个贪心策略是正确的”这点非常能区分应试者和真正有算法思维的人。举个例子给定一组区间求最多能选出多少个互不重叠的区间。经典解法是按照区间右端点排序然后依次选择右端点最小且与已选区间不重叠的区间。大多数人知道要按右端点排序但不知道为什么。我来解释一下按右端点排序后你选择的第一个区间是所有区间里右端点最小的这给后面剩下的区间留出了最大的空间。如果你按左端点排序可能会选到一个左端点很小但右端点很长的区间后面很多区间都放不下了。这个“选最不影响后续”的思路就是贪心策略的核心。笔试中如果考贪心不光要看你能不能选出贪心策略还可能会让你写一段简短的证明。我的经验是一般用**“交换论证法”**假设最优解和贪心解在某个位置第一次不同证明可以把最优解中那个元素换成贪心解选的元素而不改变最优性。把这个逻辑写清楚比你把代码写对更让考官印象深刻。2.4 二分图与HK算法看起来很高级其实考得浅热词里出现了“二分图HK算法”这在算法岗笔试中属于“进阶档”。B站这类公司的笔试题不太可能让你在纸上完整实现HK算法Hopcroft-Karp因为它代码量大、细节多笔试时间根本不够。但它很可能这样考给你一个图判断它是不是二分图。在二分图里求最大匹配问你能不能转化成最大流或匈牙利算法问题。判断二分图的方法很简单用BFS染色从一个点出发它的邻居染成相反颜色如果某个点和它的邻居颜色一样说明不是二分图。这个必须会写代码也就二十行。如果一个图是二分图并且有边权那么求最小顶点覆盖 最大匹配数Kőnig定理最大独立集 顶点数 - 最大匹配数。这几个结论在笔试和面试里经常一起出现。把这些结论当成工具箱里的螺丝刀到对应场景就知道该拿哪一把。真要考HK算法一般也就是让你说说它的时间复杂度O(E√V)和相比匈牙利算法的优势在稠密图上更快不会让你手写。2.5 排序算法和其他基础数据结构的联动B站这套题还有一个容易出现的考点用堆解决Top K问题。给你一个包含100万个整数的文件让你找出最大的100个数。如果你的直接反应是“全读进内存排序”那说明你对“海量数据”这个概念还缺乏敏感度。正确做法是维护一个大小为100的最小堆遍历每个数时如果它比堆顶元素大就替换堆顶并调整堆。时间复杂度是O(nlogk)空间复杂度是O(k)k100完美搞定。这里面有一个细节特别容易踩坑求最大的k个数要用最小堆求最小的k个数要用最大堆。很多人会搞反。逻辑其实很好记你只关心“前k名”的边界在哪里所以堆顶就是那条“及格线”。求最大的k个数“及格线”当然是当前这k个数里最小的那个所以用最小堆堆顶就是及格线新数只要比及格线高就顶掉及格线。3. 机器学习算法理论题B站算法岗的“分水岭”3.1 从粒子群到模拟退火传统优化算法为什么还没被淘汰如果单独把“粒子群算法原理”和“模拟退火算法”列出来很多人会疑惑这些都上了年纪的算法了深度学习时代还有人用吗问这个问题的同学大概率是没做过真正的工程。粒子群算法PSO在超参数优化、神经网络权重初始化、甚至推荐系统的召回策略参数调优里依然有应用空间。它的核心思想其实特别接地气一群人粒子在搜索空间里找食物全局最优每个粒子既会记住自己历史上找到过的最好位置个体最优也会参考整个群体找到的最好位置群体最优然后在速度和位置上不断更新。模拟退火的核心则是一个很漂亮的物理想法金属降温时如果冷却得足够慢原子就能排列成最稳定的晶格结构对应到优化问题上就是避免落入局部最优解。它用“温度”来控制接受差解的概率温度高时敢于接受坏解“到处乱跳”温度低了就收敛到局部精细搜索。这种“跳出局部最优”的思想在遇到高度非凸的损失函数时尤其有价值。B站考这些其实是在考察你对“全局搜索与局部搜索的平衡”这个优化本质的理解而不是真的要让你现场实现一个粒子群。我在准备这类题时的一个技巧是不要孤立地背每个算法的流程而是把所有优化算法按“搜索策略”和“适用场景”横向对比。比如粒子和遗传算法都属于群体智能模拟退火和禁忌搜索都属于单点搜索但加入了“跳出机制”梯度下降家族则依赖梯度信息。这样梳理过之后无论笔试考原理还是面试考场景题你都能答得比较有体系。3.2 卡尔曼滤波一个工科思维极强的考点看到热词里赫然列着“卡尔曼滤波算法”我第一反应是出题人里肯定有做过视频处理或用户行为轨迹预测的人。卡尔曼滤波的适用范围远不止军工和自动驾驶在B站这类平台里对视频帧中目标位置的追踪平滑、对用户观看进度的抖动处理、对端到端时延的预测都有可能用到它的思想。卡尔曼滤波的原理可以这样理解你有两个信息源一个是系统的状态方程比如根据上一帧的位置预测这一帧在哪一个是传感器观测比如我现在检测到目标在哪两者都有噪声。卡尔曼滤波做的事情就是根据两者的协方差大小动态决定“更相信谁”。笔试不会让你推导整个卡尔曼滤波的五个公式但可能会考这些概念预测步和更新步分别做了什么。预测步用状态转移矩阵算先验估计和先验协方差更新步用观测值和卡尔曼增益去修正先验估计得到后验估计。卡尔曼增益的作用。K 的范围是0到1之间K越接近1说明越相信观测值K越接近0说明越相信预测值。和最小二乘、维纳滤波的区别。卡尔曼滤波是递推的、适用于非平稳过程维纳滤波是批处理的后来也有递推形式适用平稳过程。我当时在准备这类考点的时候有一个特别管用的笔记法把每个公式的“物理含义”写在公式旁边不写推导过程。比如预测协方差公式 P F·P·Fᵀ Q旁边写“协方差经过线性变换后再加上过程噪声的协方差”。这样一来哪怕笔试一时忘记公式也能凭含义把式子推理出来。3.3 损失函数、正则化与泛化机器学习的“品德考核”无论是KNN的K值选择、聚类算法的距离度量还是贝叶斯分类里的先验后验说到底都在回答一个问题模型如何在训练集和测试集之间保持一致的“品德”。B站这套题里我觉得最可能出现的几个具体方向是过拟合和欠拟合的识别与对策。过拟合的典型信号是训练集准确率高而验证集准确率低对策包括增加数据量、降低模型复杂度、加正则化项、早停、Dropout等。欠拟合的信号是训练集本身准确率就不高需要增加模型容量或者做特征工程。L1正则化为什么会让权重变稀疏。因为它惩罚的是权重绝对值之和在0点不可导优化过程中权重很容易被压到0附近。L2正则化惩罚的是权重平方和它会倾向于让权重整体变小但不稀疏。这是个高频考点。K-Means聚类里K值怎么选。肘部法则看SSE的拐点、轮廓系数衡量样本与自身簇的紧密度以及与其他簇的分离度、Gap Statistic方法。B站内容推荐做用户画像聚类时经常会聊到这个。3.4 KL散度、ELBO和生成模型深度学习理论的隐藏关卡热词里有一项“KL ELBO算法原理详解”我一看就知道这套题里大概率混了变分推断的内容。KL散度Kullback-Leibler divergence衡量的是两个概率分布之间的差异它在机器学习里无处不在VAE的损失函数、变分推断、甚至Softmax和交叉熵的关联里都有它的影子。ELBOEvidence Lower Bound证据下界是变分推断的核心工具。做贝叶斯推断时我们想求后验分布p(z|x)但通常求不出来因为分母上的积分没有解析解。变分推断的思路是找一个容易处理的分布q(z)让它尽量接近p(z|x)把“求后验”转化成“求近似分布”。直接最小化KL散度很难算于是转化成最大化ELBOELBO 证据 - KL(q‖p)最大化ELBO等价于同时最小化近似分布和真实后验的KL散度。笔试里如果考这块大概率不是让你手推公式而是考概念ELBO由哪两部分组成重构误差项正则化项、为什么要最大化ELBO、VAE和GAN在优化目标上有什么本质区别。哪怕你已经忘了公式怎么推这几个概念的回答要像肌肉记忆一样顺畅因为它们是深度学习方向面试的基础题。4. 编程题实战从读题到AC的完整链路拆解编程题是整个笔试的重头戏也是拉开差距的地方。很多人觉得编程题就是“刷题”但我觉得关键是建立一套从读题到AC的标准化流程。这套流程能帮你节省大量时间还能降低“会做但没写出来”的概率。4.1 第一关把“模糊描述”翻译成“明确输入输出”编程题最容易让人崩溃的不是算法不会而是你根本没看懂题目到底要你干什么。B站的算法岗笔试题通常会用一段业务故事来包装编程题比如“现在有一批弹幕每一条弹幕有自己的发送时间和被举报次数请你选出最值得优先审核的k条”这类描述。你第一步要做的是把背景故事剥掉提取出抽象的问题模型。拿上面那个例子来说剥掉“弹幕”和“审核”这些包装它的本质就是“按某个字段排序后取前k个”再结合“被举报次数”这个关键词你还能想到“如果数据量很大用堆来做”。把业务问题映射到算法模型这个能力本身就需要大量练习不是光刷LeetCode就能练出来的。我的建议是每做一道题先不要急着写代码在草稿纸上写三句话输入是什么类型数组、链表、字符串还是树输出要什么一个数值、一个数组、还是一个布尔值约束条件里有没有隐藏提示比如“n最大是10^5”那就暗示你O(n²)的算法很可能过不了。4.2 第二关先想暴力解的复杂度再决定要不要优化绝大多数算法题的暴力解都是好想的关键看你能不能算出它的复杂度以及是否值得优化。比如“给定一个数组找出两个数的和为target的下标”暴力解是双重循环O(n²)优化解是用哈希表O(n)。笔试中如果n小于100O(n²)完全能过没必要非写O(n)的哈希表方案虽然哈希表也简单如果n到了10^5O(n²)必然超时。笔试过程中最重要的能力之一就是快速估算复杂度是否满足题目时间限制。通常的经验是1秒能跑约10^7 ~ 10^8次基本操作。所以当你的算法是O(n²)而n10^5时也就是10^10次操作必挂。这个时候就要果断想O(nlogn)或O(n)的解法。另一个实战技巧是先写出一个正确但可能超时的版本然后再逐段优化而不是一开始就追求完美解。很多人在考场上浪费大量时间憋最优解结果最简单的暴力版本都没写出来这是最大的得不偿失。如果时间不够一个能过部分用例的暴力解往往比一个不完整的“最优解”拿到的分数更高。4.3 第三关边界条件才是区分“会”和“熟”的分界线代码写完能跑通样例只是开始。笔试的判题系统里大量用例专门用来卡边界条件。最常见的边界条件包括但不限于空输入数组长度为0、字符串为空、链表头节点为null。只有一个元素很多递归或循环在这时会下标越界。所有元素都相等排序算法是否退化成O(n²)贪心策略是否会选错。极大极小值int溢出用long long或Python就没事、数组下标负数。目标值比所有值都大或都小二分查找的终止条件是否正确。我自己的习惯是写完代码后不急着提交先花一分钟在心里跑几个样例空输入、单元素输入、全是重复值的输入、数据量极大的输入。养成这个习惯之后你的AC率至少能提升20%。4.4 第四关一道经典动态规划题的手把手推演动态规划是算法岗笔试里避不开的一类B站第二套笔试题里大概率会出现至少一道。举一个比较典型的例子求一个数组的最长递增子序列LIS的长度。最简单的动态规划思路设dp[i]表示以第i个元素结尾的最长递增子序列长度。那么dp[i] max(dp[j] 1)其中j i且nums[j] nums[i]。初始值dp[i] 1。这样时间复杂度是O(n²)。但如果n到了10^5O(n²)会超时。这时候需要改用“贪心 二分”的思路维护一个数组tailstails[k]表示长度为k1的递增子序列的末尾元素的最小值。对每个nums[i]在tails里用二分查找找到第一个大于等于nums[i]的位置如果位置在末尾说明nums[i]可以扩展最长子序列的长度否则用nums[i]替换那个位置的值。最终tails的长度就是LIS的长度时间复杂度降为O(nlogn)。这两套方案大家可能都见过但笔试中真正的难点是你能不能一眼判断出该用O(n²)还是O(nlogn)的方案。判断依据就是输入规模n在1000左右用O(n²)完全可行n到10^5就必须用O(nlogn)。这种对复杂度边界的敏感需要在做题时刻意练习。5. 那些容易让人“裂开”的笔试坑一张表说清复盘这套题也结合我在网上看到大家讨论的踩坑经历把几个高频翻车点整理成一张表。每一行都是一个血泪教训。坑点错误表现正确的应对思路KMP next数组定义没看清把“失配时回退到哪个位置”和“最长公共前后缀长度”混为一谈先看题目给的公式特别是“next[i]定义为”后面那半句判断下标从0还是1开始快排最坏复杂度以为快排永远是O(nlogn)遇到有序数组还硬写O(n²)的递归版本遇到近乎有序的数据立刻考虑三数取中/随机选pivot或直接改归并排序贪心证明缺失只写出贪心策略不写证明导致下一步选错用交换论证法写两行把最优解和贪心解第一个差异元素交换证明不会更差二分查找死循环left mid 没加1或者left和right收敛条件写错牢记两种模板找左边界用 while (left right)闭区间则 while (left right)mid更新要区分向上/向下取整机器学习题只背概念不背场景知道“L2正则化”是惩罚权重平方和但问“何时用L2”就懵每一个概念预习时主动补一个应用场景比如“L2常见于线性回归岭回归防止过拟合”DP状态定义不清晰写完转移方程才发现dp[i]表示的含义无法递推写完dp定义后先口头描述一遍dp[i]表示“以第i个元素为结尾的xxx”确认自己懂再动手输入输出格式出错多输出了一个调试用的print提交前逐行检查所有print确认没有任何调试输出混在里面推荐把调试print统一加个DEBUG标记这张表你考前看一遍大概率能帮你避开一半以上的愚蠢失分。尤其是KMP的定义问题不同教材和不同题目里next数组的意义差出一个数量级审题不仔细写再多也全废。6. 备考节奏与资源选择别再盲目刷题了如果你正在备战算法岗秋招我给一个比较落地的备考路线按时间长短可以拆成三周冲刺版和八周稳扎稳打版。6.1 三周冲刺版第一周数据结构数组、链表、栈、队列、哈希表、二叉树的基础题每天刷4-6道重点在树和哈希表因为它们覆盖了笔试的大半题型。第二周专项突破排序、KMP、二分、贪心、DP每天一个主题配合“手写一遍所有经典排序算法”来打底。第三周机器学习理论快速过一遍不深挖推导只抓概念和场景每天抽时间做一套模拟题掐着时间锻炼手感。6.2 八周稳扎稳打版第1-2周系统复习数据结构把每个数据结构对应的经典题链表反转、LRU、二叉树遍历、最近公共祖先、单调栈刷透做到看到题就能在10秒内想出思路。第3-4周算法思想专项分治法、贪心、DP、回溯每天一个主题至少刷10道题来强化“识别题型”的能力。第5-6周机器学习理论系统整理从线性回归、逻辑回归、SVM到决策树、随机森林、GBDT再到深度学习基础CNN、RNN、Attention每个模块理出一个面试回答提纲。第7周混合刷题专题和模拟题交替重点培养时间分配能力和代码提速能力。第8周查漏补缺把自己做错的题重新看一遍把容易写错的边界条件汇总成自己的错题本。6.3 资料别贪多每个方向认准一套我见过太多人收藏几十个刷题网站、十几本电子书最后一套都没刷完。我的原则是每个方向认准一套就够了。基础数据结构用《剑指Offer》或者LeetCode的Hot 100算法思维看《算法导论》不用全读把排序、贪心、DP、图论这几章核心内容读透机器学习理论强推李航的《统计学习方法》再加上一份总结性的面试题集。还有一个容易被忽视的点用“输出倒逼输入”的方式复习。学完一个模块后尝试用大白话给别人讲一遍或者写一篇200字的笔记。如果你讲不清楚说明你还没真懂。这个方法比反复看视频课高效得多。说到底这套2029第二套题也好任何一家大厂的算法笔试题也罢考察的核心从来不是知识面广度而是**“在限时高压下把一个实际问题抽象成算法模型用简洁的代码解决掉”**的能力。这种能力没有捷径只能靠一遍遍刻意练习喂出来。我在备战阶段最大的体会就是不要迷信技巧和押题把每个基础算法都吃透、把每道做过的题都复盘明白比什么玄学都管用。最后再分享一个小习惯每次做完一套模拟题别急着对完答案就翻篇。把错的题按“审题不清”“算法不熟”“代码实现有Bug”“复杂度判断失误”四个维度归类每周统计一次分布。你会发现分布会随着复习逐渐变化审题不清越来越少算法不熟的占比慢慢上升——这时候你的复习重点就要跟着调整。祝看到这里的你笔试顺利秋招上岸。
算法岗笔试题型全拆解：从KMP到机器学习理论考点梳理
我当年秋招的时候算法岗的笔试基本就是一场“盲人摸象”——你永远猜不到出题人会从哪个犄角旮旯里扒出一道题来。B站这套2019秋招技术岗算法第二套笔试题我在网上翻到过不少讨论帖这次结合题目本身和热门考点词重新梳理一遍完整思路。本文不贴官方答案也没人真有完整版但我会把每类题型背后的考察意图、解题切入点、最容易踩的坑全部拆开揉碎讲清楚你要是正在备战算法岗笔试这篇可以直接当“错题本复习提纲”用。1. 这套题到底在考什么先看清楚出题人的底牌很多人拿到笔试题就开始闷头刷题这是大忌。算法岗笔试和竞赛刷题不一样它本质上是公司在短时间内完成“筛选”和“排位”两个动作的工具。筛选的是“有没有基本代码能力”排位的是“在同等能力的人里谁更接近我们团队的日常业务”。看到“哔哩哔哩2019秋招技术岗算法第二套”结合当年的招聘节奏我判断这套题的重点模块分布大致是数据结构与基础算法35%-40%、机器学习/深度学习理论基础20%-25%、数学与概率统计10%-15%、编程题25%-30%。别小看这个比例它直接决定了你的复习优先级。整套题的核心逻辑可以概括为三句话数据结构是骨架。KMP、排序、贪心、堆、二分这些是基本盘不要求你达到ACM水平但至少要做到“听名字就知道思路上手能十分钟写出来”。算法岗的“算法”二字指向的是“机器学习算法”。这也是B站这类内容平台比较特别的地方它不像Google那样考特别深的系统设计也不会像某些银行IT一样考大量SQL而是会围绕推荐、审核、内容理解这些业务场景去考察你懂不懂模型原理、会不会调参、知不知道评估指标的坑。编程题真正考的是“把模糊问题变成清晰步骤”的能力。不是考你会不会某个冷门数据结构而是考你在有限时间里能不能把思路完整落地成能跑的代码。所以你要是只会刷LeetCode而机器学习基础一塌糊涂或者理论背得滚瓜烂熟但手写代码就卡壳这套题都会让你很难受。它要求的是“两条腿走路”而且两条腿都不能太短。2. 数据结构与基础算法KMP、排序、贪心、二分到底怎么考2.1 KMP的next数组背了十遍做题照样错一看到热搜词里有“在KMP算法中对于模式串pabacaba其next数组”我就知道这类题是B站笔试的常客。KMP本身在实际业务里用得并不多但它是考察“你懂不懂前缀函数本质”的一个经典试金石。出题人不可能指望你上生产环境去写一个字符串匹配算法但你要是连next数组都算不对他会怀疑你的基本功。先把这个例子讲透。模式串 p abacaba下标从0开始长度7。next数组在B站这套题里应该指的是**“当前字符不匹配时模式串应该回退到的位置”**也就是常用的next[i]表示“p[0..i]的前缀中最长的相等前后缀长度”。要注意这里不是每个版本的KMP定义都完全一样有的地方next数组第一位是-1有的地方第一位是0所以审题一定要仔细看它给出的定义。按最主流的定义next[i] 以i结尾的子串的最长相等前后缀长度前后缀不包括子串本身来算下标 i字符子串p[0..i]最长相等前后缀长度next[i]0aa0无真前后缀01bab002aaba1前缀a后缀a13cabac004aabaca115babacab2abab26aabacaba3abaaba3第二套卷子如果考的是next数组大概率会在“前后缀不能包含整个子串”这个细节上设坑很多人会把next[6]写成7因为整个子串和自身相等这就是基本功不扎实的表现。在KMP匹配过程中当主串字符和模式串字符不匹配时模式串向右移动的位数 已匹配的字符数 - 对应的失配字符的next值。这个公式也要记住。比如在主串里匹配到某个位置失配时如果你已经匹配了5个字符而失配位置对应的next值是2那么模式串应该右移3位继续比较而不是一位一位往后挪。理解这个移动过程比背代码更重要因为笔试很可能会给你一个具体的主串和模式串让你手算匹配过程中的比较次数。2.2 排序算法与复杂度的极限拉扯数据结构排序算法这类题在B站2019秋招的笔试题里属于“送分但不完全送分”的模块。送分是因为人人都会背快排和归并的复杂度不送分是因为它考得细比如排序算法的稳定性哪些排序是稳定的哪些不稳定稳定排序意味着相等元素的相对顺序不改变。冒泡、插入、归并是稳定的选择、快排、堆排是不稳定的。这个点经常和“实际业务中按多个字段排序的需求”结合考。堆排序建堆的时间复杂度很多人以为建堆是O(nlogn)其实是O(n)。证明思路是每一层的节点数乘以该层高度最终求和的结果是O(n)。如果让你手写建堆过程注意从最后一个非叶子节点开始向下调整。快排的最坏情况当数组已经有序升序或降序时如果每次选第一个元素作为pivot快排会退化成O(n²)。这也是为什么实际工程里会用“三数取中”或者随机选pivot来避免这种极端情况。外部排序如果数据量超过内存能容纳的范围比如要对一个10GB的文件排序而内存只有1GB就需要用到外部排序。它的核心思想是“分块排序多路归并”考察归并排序在海量数据场景下的应用。我的建议是不要只看理论复杂度要把每种排序的代码手写一遍至少写三遍。第一遍照着书抄第二遍合上书自己默写第三遍边写边说出每一步在干什么。这样到笔试时就算紧张手也有肌肉记忆了。2.3 贪心算法证明比算法本身更重要贪心算法在B站这套题里出现的概率很高原因有二一是它写起来代码量少适合笔试这种限时场景二是贪心算法真正的难点不在算法而在“证明这个贪心策略是正确的”这点非常能区分应试者和真正有算法思维的人。举个例子给定一组区间求最多能选出多少个互不重叠的区间。经典解法是按照区间右端点排序然后依次选择右端点最小且与已选区间不重叠的区间。大多数人知道要按右端点排序但不知道为什么。我来解释一下按右端点排序后你选择的第一个区间是所有区间里右端点最小的这给后面剩下的区间留出了最大的空间。如果你按左端点排序可能会选到一个左端点很小但右端点很长的区间后面很多区间都放不下了。这个“选最不影响后续”的思路就是贪心策略的核心。笔试中如果考贪心不光要看你能不能选出贪心策略还可能会让你写一段简短的证明。我的经验是一般用**“交换论证法”**假设最优解和贪心解在某个位置第一次不同证明可以把最优解中那个元素换成贪心解选的元素而不改变最优性。把这个逻辑写清楚比你把代码写对更让考官印象深刻。2.4 二分图与HK算法看起来很高级其实考得浅热词里出现了“二分图HK算法”这在算法岗笔试中属于“进阶档”。B站这类公司的笔试题不太可能让你在纸上完整实现HK算法Hopcroft-Karp因为它代码量大、细节多笔试时间根本不够。但它很可能这样考给你一个图判断它是不是二分图。在二分图里求最大匹配问你能不能转化成最大流或匈牙利算法问题。判断二分图的方法很简单用BFS染色从一个点出发它的邻居染成相反颜色如果某个点和它的邻居颜色一样说明不是二分图。这个必须会写代码也就二十行。如果一个图是二分图并且有边权那么求最小顶点覆盖 最大匹配数Kőnig定理最大独立集 顶点数 - 最大匹配数。这几个结论在笔试和面试里经常一起出现。把这些结论当成工具箱里的螺丝刀到对应场景就知道该拿哪一把。真要考HK算法一般也就是让你说说它的时间复杂度O(E√V)和相比匈牙利算法的优势在稠密图上更快不会让你手写。2.5 排序算法和其他基础数据结构的联动B站这套题还有一个容易出现的考点用堆解决Top K问题。给你一个包含100万个整数的文件让你找出最大的100个数。如果你的直接反应是“全读进内存排序”那说明你对“海量数据”这个概念还缺乏敏感度。正确做法是维护一个大小为100的最小堆遍历每个数时如果它比堆顶元素大就替换堆顶并调整堆。时间复杂度是O(nlogk)空间复杂度是O(k)k100完美搞定。这里面有一个细节特别容易踩坑求最大的k个数要用最小堆求最小的k个数要用最大堆。很多人会搞反。逻辑其实很好记你只关心“前k名”的边界在哪里所以堆顶就是那条“及格线”。求最大的k个数“及格线”当然是当前这k个数里最小的那个所以用最小堆堆顶就是及格线新数只要比及格线高就顶掉及格线。3. 机器学习算法理论题B站算法岗的“分水岭”3.1 从粒子群到模拟退火传统优化算法为什么还没被淘汰如果单独把“粒子群算法原理”和“模拟退火算法”列出来很多人会疑惑这些都上了年纪的算法了深度学习时代还有人用吗问这个问题的同学大概率是没做过真正的工程。粒子群算法PSO在超参数优化、神经网络权重初始化、甚至推荐系统的召回策略参数调优里依然有应用空间。它的核心思想其实特别接地气一群人粒子在搜索空间里找食物全局最优每个粒子既会记住自己历史上找到过的最好位置个体最优也会参考整个群体找到的最好位置群体最优然后在速度和位置上不断更新。模拟退火的核心则是一个很漂亮的物理想法金属降温时如果冷却得足够慢原子就能排列成最稳定的晶格结构对应到优化问题上就是避免落入局部最优解。它用“温度”来控制接受差解的概率温度高时敢于接受坏解“到处乱跳”温度低了就收敛到局部精细搜索。这种“跳出局部最优”的思想在遇到高度非凸的损失函数时尤其有价值。B站考这些其实是在考察你对“全局搜索与局部搜索的平衡”这个优化本质的理解而不是真的要让你现场实现一个粒子群。我在准备这类题时的一个技巧是不要孤立地背每个算法的流程而是把所有优化算法按“搜索策略”和“适用场景”横向对比。比如粒子和遗传算法都属于群体智能模拟退火和禁忌搜索都属于单点搜索但加入了“跳出机制”梯度下降家族则依赖梯度信息。这样梳理过之后无论笔试考原理还是面试考场景题你都能答得比较有体系。3.2 卡尔曼滤波一个工科思维极强的考点看到热词里赫然列着“卡尔曼滤波算法”我第一反应是出题人里肯定有做过视频处理或用户行为轨迹预测的人。卡尔曼滤波的适用范围远不止军工和自动驾驶在B站这类平台里对视频帧中目标位置的追踪平滑、对用户观看进度的抖动处理、对端到端时延的预测都有可能用到它的思想。卡尔曼滤波的原理可以这样理解你有两个信息源一个是系统的状态方程比如根据上一帧的位置预测这一帧在哪一个是传感器观测比如我现在检测到目标在哪两者都有噪声。卡尔曼滤波做的事情就是根据两者的协方差大小动态决定“更相信谁”。笔试不会让你推导整个卡尔曼滤波的五个公式但可能会考这些概念预测步和更新步分别做了什么。预测步用状态转移矩阵算先验估计和先验协方差更新步用观测值和卡尔曼增益去修正先验估计得到后验估计。卡尔曼增益的作用。K 的范围是0到1之间K越接近1说明越相信观测值K越接近0说明越相信预测值。和最小二乘、维纳滤波的区别。卡尔曼滤波是递推的、适用于非平稳过程维纳滤波是批处理的后来也有递推形式适用平稳过程。我当时在准备这类考点的时候有一个特别管用的笔记法把每个公式的“物理含义”写在公式旁边不写推导过程。比如预测协方差公式 P F·P·Fᵀ Q旁边写“协方差经过线性变换后再加上过程噪声的协方差”。这样一来哪怕笔试一时忘记公式也能凭含义把式子推理出来。3.3 损失函数、正则化与泛化机器学习的“品德考核”无论是KNN的K值选择、聚类算法的距离度量还是贝叶斯分类里的先验后验说到底都在回答一个问题模型如何在训练集和测试集之间保持一致的“品德”。B站这套题里我觉得最可能出现的几个具体方向是过拟合和欠拟合的识别与对策。过拟合的典型信号是训练集准确率高而验证集准确率低对策包括增加数据量、降低模型复杂度、加正则化项、早停、Dropout等。欠拟合的信号是训练集本身准确率就不高需要增加模型容量或者做特征工程。L1正则化为什么会让权重变稀疏。因为它惩罚的是权重绝对值之和在0点不可导优化过程中权重很容易被压到0附近。L2正则化惩罚的是权重平方和它会倾向于让权重整体变小但不稀疏。这是个高频考点。K-Means聚类里K值怎么选。肘部法则看SSE的拐点、轮廓系数衡量样本与自身簇的紧密度以及与其他簇的分离度、Gap Statistic方法。B站内容推荐做用户画像聚类时经常会聊到这个。3.4 KL散度、ELBO和生成模型深度学习理论的隐藏关卡热词里有一项“KL ELBO算法原理详解”我一看就知道这套题里大概率混了变分推断的内容。KL散度Kullback-Leibler divergence衡量的是两个概率分布之间的差异它在机器学习里无处不在VAE的损失函数、变分推断、甚至Softmax和交叉熵的关联里都有它的影子。ELBOEvidence Lower Bound证据下界是变分推断的核心工具。做贝叶斯推断时我们想求后验分布p(z|x)但通常求不出来因为分母上的积分没有解析解。变分推断的思路是找一个容易处理的分布q(z)让它尽量接近p(z|x)把“求后验”转化成“求近似分布”。直接最小化KL散度很难算于是转化成最大化ELBOELBO 证据 - KL(q‖p)最大化ELBO等价于同时最小化近似分布和真实后验的KL散度。笔试里如果考这块大概率不是让你手推公式而是考概念ELBO由哪两部分组成重构误差项正则化项、为什么要最大化ELBO、VAE和GAN在优化目标上有什么本质区别。哪怕你已经忘了公式怎么推这几个概念的回答要像肌肉记忆一样顺畅因为它们是深度学习方向面试的基础题。4. 编程题实战从读题到AC的完整链路拆解编程题是整个笔试的重头戏也是拉开差距的地方。很多人觉得编程题就是“刷题”但我觉得关键是建立一套从读题到AC的标准化流程。这套流程能帮你节省大量时间还能降低“会做但没写出来”的概率。4.1 第一关把“模糊描述”翻译成“明确输入输出”编程题最容易让人崩溃的不是算法不会而是你根本没看懂题目到底要你干什么。B站的算法岗笔试题通常会用一段业务故事来包装编程题比如“现在有一批弹幕每一条弹幕有自己的发送时间和被举报次数请你选出最值得优先审核的k条”这类描述。你第一步要做的是把背景故事剥掉提取出抽象的问题模型。拿上面那个例子来说剥掉“弹幕”和“审核”这些包装它的本质就是“按某个字段排序后取前k个”再结合“被举报次数”这个关键词你还能想到“如果数据量很大用堆来做”。把业务问题映射到算法模型这个能力本身就需要大量练习不是光刷LeetCode就能练出来的。我的建议是每做一道题先不要急着写代码在草稿纸上写三句话输入是什么类型数组、链表、字符串还是树输出要什么一个数值、一个数组、还是一个布尔值约束条件里有没有隐藏提示比如“n最大是10^5”那就暗示你O(n²)的算法很可能过不了。4.2 第二关先想暴力解的复杂度再决定要不要优化绝大多数算法题的暴力解都是好想的关键看你能不能算出它的复杂度以及是否值得优化。比如“给定一个数组找出两个数的和为target的下标”暴力解是双重循环O(n²)优化解是用哈希表O(n)。笔试中如果n小于100O(n²)完全能过没必要非写O(n)的哈希表方案虽然哈希表也简单如果n到了10^5O(n²)必然超时。笔试过程中最重要的能力之一就是快速估算复杂度是否满足题目时间限制。通常的经验是1秒能跑约10^7 ~ 10^8次基本操作。所以当你的算法是O(n²)而n10^5时也就是10^10次操作必挂。这个时候就要果断想O(nlogn)或O(n)的解法。另一个实战技巧是先写出一个正确但可能超时的版本然后再逐段优化而不是一开始就追求完美解。很多人在考场上浪费大量时间憋最优解结果最简单的暴力版本都没写出来这是最大的得不偿失。如果时间不够一个能过部分用例的暴力解往往比一个不完整的“最优解”拿到的分数更高。4.3 第三关边界条件才是区分“会”和“熟”的分界线代码写完能跑通样例只是开始。笔试的判题系统里大量用例专门用来卡边界条件。最常见的边界条件包括但不限于空输入数组长度为0、字符串为空、链表头节点为null。只有一个元素很多递归或循环在这时会下标越界。所有元素都相等排序算法是否退化成O(n²)贪心策略是否会选错。极大极小值int溢出用long long或Python就没事、数组下标负数。目标值比所有值都大或都小二分查找的终止条件是否正确。我自己的习惯是写完代码后不急着提交先花一分钟在心里跑几个样例空输入、单元素输入、全是重复值的输入、数据量极大的输入。养成这个习惯之后你的AC率至少能提升20%。4.4 第四关一道经典动态规划题的手把手推演动态规划是算法岗笔试里避不开的一类B站第二套笔试题里大概率会出现至少一道。举一个比较典型的例子求一个数组的最长递增子序列LIS的长度。最简单的动态规划思路设dp[i]表示以第i个元素结尾的最长递增子序列长度。那么dp[i] max(dp[j] 1)其中j i且nums[j] nums[i]。初始值dp[i] 1。这样时间复杂度是O(n²)。但如果n到了10^5O(n²)会超时。这时候需要改用“贪心 二分”的思路维护一个数组tailstails[k]表示长度为k1的递增子序列的末尾元素的最小值。对每个nums[i]在tails里用二分查找找到第一个大于等于nums[i]的位置如果位置在末尾说明nums[i]可以扩展最长子序列的长度否则用nums[i]替换那个位置的值。最终tails的长度就是LIS的长度时间复杂度降为O(nlogn)。这两套方案大家可能都见过但笔试中真正的难点是你能不能一眼判断出该用O(n²)还是O(nlogn)的方案。判断依据就是输入规模n在1000左右用O(n²)完全可行n到10^5就必须用O(nlogn)。这种对复杂度边界的敏感需要在做题时刻意练习。5. 那些容易让人“裂开”的笔试坑一张表说清复盘这套题也结合我在网上看到大家讨论的踩坑经历把几个高频翻车点整理成一张表。每一行都是一个血泪教训。坑点错误表现正确的应对思路KMP next数组定义没看清把“失配时回退到哪个位置”和“最长公共前后缀长度”混为一谈先看题目给的公式特别是“next[i]定义为”后面那半句判断下标从0还是1开始快排最坏复杂度以为快排永远是O(nlogn)遇到有序数组还硬写O(n²)的递归版本遇到近乎有序的数据立刻考虑三数取中/随机选pivot或直接改归并排序贪心证明缺失只写出贪心策略不写证明导致下一步选错用交换论证法写两行把最优解和贪心解第一个差异元素交换证明不会更差二分查找死循环left mid 没加1或者left和right收敛条件写错牢记两种模板找左边界用 while (left right)闭区间则 while (left right)mid更新要区分向上/向下取整机器学习题只背概念不背场景知道“L2正则化”是惩罚权重平方和但问“何时用L2”就懵每一个概念预习时主动补一个应用场景比如“L2常见于线性回归岭回归防止过拟合”DP状态定义不清晰写完转移方程才发现dp[i]表示的含义无法递推写完dp定义后先口头描述一遍dp[i]表示“以第i个元素为结尾的xxx”确认自己懂再动手输入输出格式出错多输出了一个调试用的print提交前逐行检查所有print确认没有任何调试输出混在里面推荐把调试print统一加个DEBUG标记这张表你考前看一遍大概率能帮你避开一半以上的愚蠢失分。尤其是KMP的定义问题不同教材和不同题目里next数组的意义差出一个数量级审题不仔细写再多也全废。6. 备考节奏与资源选择别再盲目刷题了如果你正在备战算法岗秋招我给一个比较落地的备考路线按时间长短可以拆成三周冲刺版和八周稳扎稳打版。6.1 三周冲刺版第一周数据结构数组、链表、栈、队列、哈希表、二叉树的基础题每天刷4-6道重点在树和哈希表因为它们覆盖了笔试的大半题型。第二周专项突破排序、KMP、二分、贪心、DP每天一个主题配合“手写一遍所有经典排序算法”来打底。第三周机器学习理论快速过一遍不深挖推导只抓概念和场景每天抽时间做一套模拟题掐着时间锻炼手感。6.2 八周稳扎稳打版第1-2周系统复习数据结构把每个数据结构对应的经典题链表反转、LRU、二叉树遍历、最近公共祖先、单调栈刷透做到看到题就能在10秒内想出思路。第3-4周算法思想专项分治法、贪心、DP、回溯每天一个主题至少刷10道题来强化“识别题型”的能力。第5-6周机器学习理论系统整理从线性回归、逻辑回归、SVM到决策树、随机森林、GBDT再到深度学习基础CNN、RNN、Attention每个模块理出一个面试回答提纲。第7周混合刷题专题和模拟题交替重点培养时间分配能力和代码提速能力。第8周查漏补缺把自己做错的题重新看一遍把容易写错的边界条件汇总成自己的错题本。6.3 资料别贪多每个方向认准一套我见过太多人收藏几十个刷题网站、十几本电子书最后一套都没刷完。我的原则是每个方向认准一套就够了。基础数据结构用《剑指Offer》或者LeetCode的Hot 100算法思维看《算法导论》不用全读把排序、贪心、DP、图论这几章核心内容读透机器学习理论强推李航的《统计学习方法》再加上一份总结性的面试题集。还有一个容易被忽视的点用“输出倒逼输入”的方式复习。学完一个模块后尝试用大白话给别人讲一遍或者写一篇200字的笔记。如果你讲不清楚说明你还没真懂。这个方法比反复看视频课高效得多。说到底这套2029第二套题也好任何一家大厂的算法笔试题也罢考察的核心从来不是知识面广度而是**“在限时高压下把一个实际问题抽象成算法模型用简洁的代码解决掉”**的能力。这种能力没有捷径只能靠一遍遍刻意练习喂出来。我在备战阶段最大的体会就是不要迷信技巧和押题把每个基础算法都吃透、把每道做过的题都复盘明白比什么玄学都管用。最后再分享一个小习惯每次做完一套模拟题别急着对完答案就翻篇。把错的题按“审题不清”“算法不熟”“代码实现有Bug”“复杂度判断失误”四个维度归类每周统计一次分布。你会发现分布会随着复习逐渐变化审题不清越来越少算法不熟的占比慢慢上升——这时候你的复习重点就要跟着调整。祝看到这里的你笔试顺利秋招上岸。
