B站2020校招算法笔试卷二的复盘与拆解从真题到考点从思路到代码刷到这份《哔哩哔哩2020校园招聘算法笔试卷二》时我第一反应是总算有一份能真正代表互联网公司算法岗笔试水平的卷子了。题目不算偏但覆盖面够广数据结构、字符串匹配、机器学习、优化算法都有涉及而且有些题目背后藏着的坑不是刷几道LeetCode就能发现的。这份卷子适合两类人看一类是正在准备大厂算法岗校招的应届生另一类是已经工作但想系统梳理算法知识体系的开发者。我结合自己当年笔试和后来面试候选人的经验把这份卷子涉及的考点、易错点、推导过程都拆开聊一聊。1. 这份试卷在考什么B站算法岗的考察逻辑与考点分布先别急着做题。拿到一份笔试卷子第一件事不是埋头写代码而是花五分钟搞清楚出题人想考察什么能力结构。B站2020校招算法笔试卷二整体来看考察面很典型基础数据结构与算法、字符串处理、机器学习基础、优化搜索算法再加上一些需要现场推导的题目。这不是B站独有的风格而是国内互联网公司算法岗笔试的通用范式。1.1 为什么算法岗笔试总爱考这些老题很多同学会问现在深度学习这么火为什么笔试还在考KMP、快排、Dijkstra这些老古董原因很简单笔试筛选的不是谁会调包而是谁的计算机科学基本功扎实。KMP能不能手推next数组快排能不能写对边界条件Dijkstra能不能说清楚堆优化的原理这些直接反映了一个人对算法的理解程度。而且在线上笔试的环境里没法查资料、没法跑实验能依赖的只有脑子里的知识体系。B站这份卷子也不例外从热搜词里频繁出现KMP、排序算法、贪心算法这些关键词也能看出这类基础考点是笔试的绝对主力。1.2 整卷考点分布速览我把这份试卷涉及的考点整理成一张表方便大家对照自查考点领域具体考点考察形式难度数据结构基础数组、链表、栈、队列的操作与复杂度分析选择题/编程题低排序算法快排、堆排、归并排序的原理与复杂度选择题/手写代码中字符串匹配KMP算法的next数组推导选择/填空/手写高图论算法Dijkstra、拓扑排序选择/编程题中贪心策略贪心选择性质的证明、典型应用选择题/简答中机器学习损失函数、评估指标、过拟合选择题/简答中优化算法粒子群、模拟退火的原理与流程选择/简答中高信号处理基础重采样、滤波、锐化等图像/音频算法选择题/简答低中这个分布其实很有讲究。基础数据结构和排序是送分题考察的是你大学四年有没有认真上课KMP这类字符串算法是区分题考察的是你有没有真正理解算法的本质机器学习基础和优化算法则是进阶题考察的是你有没有做算法岗的潜力。2. 排序与数据结构高频题快排、堆排和那些必背的复杂度排序算法几乎是算法笔试的常驻嘉宾。B站这份卷子也不例外但值得注意的不是会不会写快排而是能不能在各种变形题中稳定输出。2.1 快排的划分思想与应用场景快速排序的核心是分治和划分。每次选一个基准元素pivot把数组分成小于基准和大于基准的两部分然后递归处理。int partition(vectorint nums, int left, int right) { int pivot nums[right]; // 选最右元素作为基准 int i left - 1; for (int j left; j right; j) { if (nums[j] pivot) { i; swap(nums[i], nums[j]); } } swap(nums[i 1], nums[right]); return i 1; } void quickSort(vectorint nums, int left, int right) { if (left right) return; int pos partition(nums, left, right); quickSort(nums, left, pos - 1); quickSort(nums, pos 1, right); }这里最容易踩的坑有两个一是基准元素的选择如果每次选最右元素遇到近乎有序的数组会退化到O(n²)二是partition边界条件i的初始值和最终返回的位置容易搞混。我一般建议在笔试中写随机选择基准的版本避免被测试用例卡。2.2 堆排序与TopK问题堆排序在B站笔试中往往不直接考完整实现而是考TopK问题。比如从一亿个数中找出最大的100个数最优解就是用大小为100的最小堆遍历一遍数据堆满后每次比较堆顶元素比堆顶大就替换并调整堆。建堆的时间复杂度不是O(nlogn)而是O(n)。这个点很多人记错笔试选择题里很容易被坑。调整为堆的过程是从最后一个非叶子节点开始向前逐个下沉void heapify(vectorint nums, int n, int i) { int largest i; int left 2 * i 1; int right 2 * i 2; if (left n nums[left] nums[largest]) largest left; if (right n nums[right] nums[largest]) largest right; if (largest ! i) { swap(nums[i], nums[largest]); heapify(nums, n, largest); } }堆排序的稳定性、空间复杂度、适用场景这些也是一定要记牢的。堆排序不稳定空间复杂度O(1)适用于需要原地排序且对稳定性无要求的场景。2.3 几种常见排序算法的复杂度对照笔试选择题经常考排序算法的复杂度对比我列个表方便大家直接背排序算法平均时间复杂度最坏时间复杂度空间复杂度稳定性冒泡排序O(n²)O(n²)O(1)稳定快速排序O(nlogn)O(n²)O(logn)不稳定归并排序O(nlogn)O(nlogn)O(n)稳定堆排序O(nlogn)O(nlogn)O(1)不稳定插入排序O(n²)O(n²)O(1)稳定希尔排序O(n^1.3)O(n²)O(1)不稳定我实操中的一个经验笔试手写排序时除非明确要求稳定排序否则优先写快排因为代码量最少、思维负担最小。如果遇到需要稳定排序的题用归并排序但要注意额外空间的开销。3. KMP的next数组推导从abacaba真题手算到边界条件KMP算法几乎可以算是算法笔试的必考题。B站这份卷子里涉及一个很经典的例子模式串pabacaba要求推导next数组。这个知识点在热搜词里也出现了可见有多高频。很多同学背得了KMP的整体流程但一落实到next数组的手算就会出错原因在于没有真正理解next数组的定义。3.1 next数组到底在求什么next数组的定义在不同教材里有细微差别但核心含义一致next[i]表示模式串前i个字符组成的子串中最长相等前后缀的长度有的版本定义为前i-1个字符的最长相等前后缀长度注意看清题目约定。相等前后缀的意思是一个字符串的前缀和后缀相同且长度小于字符串本身。拿pabacaba来说整个字符串的最长相等前后缀是aba长度为3。前缀aba和后缀aba相等且这是最长的。3.2 逐步手推pabacaba的next数组我按经典的next数组定义next[i]表示前i个字符组成子串的最长相等前后缀长度来手动推一遍i1子串为a没有相等前后缀长度必须小于子串长度next[1]0i2子串为ab前缀有a后缀有b不相等next[2]0i3子串为aba前缀a等于后缀a前缀ab不等于后缀ba最长相等前后缀长度为1next[3]1i4子串为abac前缀a不等于后缀c前缀ab不等于后缀ac前缀aba不等于后缀bacnext[4]0i5子串为abaca前缀a等于后缀anext[5]1i6子串为abacab前缀ab等于后缀ab长度为2next[6]2i7子串为abacaba前缀aba等于后缀aba长度为3next[7]3所以pabacaba的next数组是0, 0, 1, 0, 1, 2, 3。这个推导过程看起来简单但笔试时很多人会在i6和i7处犯错因为ab和aba这两个相等前后缀容易看漏。我的建议是动手算的时候把每个子串的前缀集合和后缀集合都列出来再求交集的最大长度慢是慢一点但准确率远高于眼算。3.3 为什么next数组能加速匹配KMP的核心思想是当模式串与文本串在某一位失配时不是把模式串右移一位从头匹配而是利用next数组的信息直接把模式串滑动到可能匹配的位置。举个例子假设文本串是abacababc模式串是abacaba在匹配到第7个字符时失配文本串第7个字符是a模式串第7个字符是a其实能匹配实际失配假设发生在模式串第7个字符与文本串第8个字符处。此时next[7]3意味着模式串前7个字符的最长相等前后缀是aba所以可以直接把模式串向右移动4位7-34前3个字符不用重新比较。这个优化的本质是避免了文本串指针的回退让匹配过程在线性时间内完成。3.4 用代码生成next数组笔试如果让手写KMPnext数组的生成代码必须烂熟于心vectorint getNext(const string p) { int n p.size(); vectorint next(n, 0); int j 0; for (int i 1; i n; i) { while (j 0 p[i] ! p[j]) { j next[j - 1]; } if (p[i] p[j]) { j; } next[i] j; } return next; }这段代码里的while循环是精髓也是笔试时最容易被忽略的。当p[i]和p[j]不相等时j要回退到next[j-1]而不是直接归零。这个回退的思想与KMP匹配时失配的处理方式完全一致理解了这一点KMP的整体逻辑就通了。4. 机器学习与评估指标算法岗绕不开的基础题B站算法岗笔试不可能只考纯数据结构机器学习和深度学习的考察是重头戏。从热搜词里机器学习算法、深度学习算法的热度就能看出这是行业内公认的重点。虽然2020年的笔试试卷距今有些年头了但基础考点依然是现在笔试的主流。4.1 损失函数的选择逻辑机器学习部分常考的一个题是回归问题和分类问题分别常用哪些损失函数。看似简单但很多人答不全。回归问题常用均方误差MSE和平均绝对误差MAE[ MSE \frac{1}{n}\sum_{i1}^{n}(y_i - \hat{y}_i)^2 ]MSE对异常值敏感因为误差被平方放大MAE对异常值更鲁棒但在零点不可导优化时不如MSE方便。分类问题最常用的是交叉熵损失[ L -\sum_{i1}^{n} y_i \log(\hat{y}_i) ]交叉熵天然适合概率输出配合softmax使用梯度计算简洁而且能有效避免梯度饱和问题。我在面试中经常问候选人为什么分类不用MSE能答出MSE配合sigmoid会导致梯度消失的人不多建议大家都去推一遍sigmoid加MSE的梯度公式印象会深刻很多。4.2 过拟合与正则化手段过拟合是算法笔试另一类高频考点。关键在于回答时要有层次数据层面、模型层面、训练层面。数据层面可以做数据增强、扩充数据集模型层面可以降低模型复杂度、加正则化项训练层面可以用早停、Dropout、Batch Normalization。L1和L2正则化的区别也是一个常见的考点L1会得到稀疏解L2会得到接近零的非稀疏解。形象点说L1是把不重要的特征的权重直接砍到零L2是让它们变得很小但不彻底消失。4.3 分类模型的评估指标精确率、召回率、F1值、AUC这些指标的定义和适用场景必须厘清。我见过很多候选人精确率和召回率的概念背得滚瓜烂熟但一放到具体场景就选错。比如垃圾邮件过滤更看重精确率还是召回率答案是看代价。如果误判正常邮件为垃圾邮件的代价高可能错过重要邮件就应优先提高精确率如果漏掉垃圾邮件的代价高用户被骚扰就应优先提高召回率。F1是两者的调和平均适用于需要平衡的场景。AUC的含义是随机抽取一个正样本和一个负样本正样本的预测分数大于负样本的概率。AUC不依赖具体的分类阈值适合评估模型整体的排序能力。4.4 一个完整的面试答题框架笔试遇到如何评估一个二分类模型这类简答题时我建议按这个框架去答混淆矩阵TP、FP、TN、FN四个基本量衍生指标精确率、召回率、F1全局指标准确率、AUC、LogLoss适用场景分析数据是否平衡、误判代价是否不对称实际应用结合具体业务场景选择主指标这套框架的好处是逻辑完整从微观到宏观从定义到应用能体现你对评估体系的系统理解。5. 优化与搜索算法选讲粒子群、模拟退火、卡尔曼滤波的考察逻辑这部分是整份试卷中最有区分度的内容。粒子群算法、模拟退火算法、卡尔曼滤波这些从热搜词里能看到的词在B站这份卷子里出现说明出题人不仅关注经典算法更关注与工程实践相关的优化和状态估计方法。对非相关方向的同学来说这些题可能是超纲的但作为算法岗候选人多少需要了解它们的核心思想。5.1 粒子群算法PSO的核心机制粒子群算法模拟鸟群觅食行为一群候选解粒子在解空间中飞翔每个粒子有自己的位置和速度通过追踪个体最优pbest和全局最优gbest来更新自己。速度更新公式是核心考点[ v_{i}(t1) w \cdot v_{i}(t) c_1 \cdot r_1 \cdot (pbest_i - x_i(t)) c_2 \cdot r_2 \cdot (gbest - x_i(t)) ]其中w是惯性权重c1是认知学习因子c2是社会学习因子r1和r2是[0,1]之间的随机数。笔试如果只背公式不理解意义很容易在追问下露馅。做题时理解这三个部分的意义远比死记公式更重要。5.2 模拟退火算法的核心逻辑模拟退火算法模拟金属退火过程高温时分子运动剧烈随温度降低逐渐趋于稳定。算法以一定概率接受比当前解更差的解这个概率由Metropolis准则决定[ P \exp(-\frac{\Delta E}{T}) ]其中ΔE是新解与当前解的适应度差T是当前温度。当ΔE0新解更差时概率P小于1且随温度降低越来越小。这个允许跳出具部最优的机制是模拟退火区别于贪心算法的核心。5.3 卡尔曼滤波的状态估计思路卡尔曼滤波是信号处理和控制论的重要内容。它的核心思想是融合系统预测和传感器测量两个信息来源给出最优状态估计。过程分为两步预测根据上一时刻状态和运动模型预测当前时刻状态和更新综合预测值和测量值按卡尔曼增益加权平均。笔试考卡尔曼滤波通常是考概念理解比如卡尔曼增益的作用决定预测和测量哪个更可信或者考一维情况的公式推导。5.4 贪心算法的考察套路贪心算法在笔试卷里出现的形式往往是选择题以下哪个问题能用贪心算法求解 正确答案通常是活动安排问题、霍夫曼编码、最小生成树Prim/Kruskal等。而背包问题要看具体类型分数背包可用贪心01背包必须用动态规划。这个考点的核心是贪心选择性质和最优子结构。做题时判断用的是哪种算法主要看每一步的局部最优选择是否一定能导致全局最优。如果不能确定大概率要用动态规划或搜索。6. 从B站笔试题反推备考策略时间分配、题目取舍与心态管理聊完具体的考点最后说点求职实际有用的东西。刷笔试题不只是为了做对题更是为了摸清出题人的思路形成自己的应试策略。6.1 笔试时间分配的通用法则以B站这份卷子的题量来看我建议采用三轮答题法第一轮用5-10分钟快速扫描所有题目把题分为立即能做想一想能做完全不会三类。第二轮从立即能做的题开始保证送分题全拿。第三轮处理想一想能做的题最后有时间再攻克完全不会的题。这样分配的核心逻辑是算法笔试的及格线往往在50%-60%左右先把确定性高的分值拿到手比死磕一道难题重要得多。6.2 代码风格也是隐形评分点即使是线上笔试面试官也会看你的代码风格。变量命名是否清晰、边界条件是否处理、是否有冗余代码这些都在印象分里。我见过不少候选人算法思路完全正确但代码写得一塌糊涂不处理数组越界、不初始化变量、缩进混乱。这在笔试中可能还好但到了面试手写代码环节就是致命伤。我一直建议在校招准备阶段就养成良好的编码习惯先想清楚边界条件再动手写写完自己走一遍测试用例。这个习惯在笔试中能帮你避开很多低级错误。6.3 如何从一道题延展出一套知识体系B站这份卷子给我最大的启发是单个考点背后站的是一整个知识体系。比如KMP考点背后不止是next数组还有自动机思想、字符串哈希、后缀数组等一串相关算法粒子群考点背后是群体智能优化算法的家族蚁群算法、人工蜂群算法等。我建议复习时用知识点拓扑图的方式组织内容每个考点画一张图中心是核心算法向外辐射的是变体、优化、应用场景和易错点。这个方法前期投入的时间多一些但后面的复习效率会大幅提升。最后说说实操中的个人体会。我当年做这类笔试时最容易出问题的地方恰恰是那些看似简单的送分题——越简单的题越容易粗心越熟悉的考点越容易掉以轻心。所以无论准备得多么充分考试时都建议留出最后10分钟回看一遍代码和选择题答案重点检查边界条件和思路是否被题目陷阱带偏。这也算是我踩过几次坑之后总结出来的硬经验分享给正在准备校招的读者希望对你们有些许帮助。