商汤算法研究岗笔试复盘：KMP、动态规划与XGBoost备考指南

2023年秋招那阵子我投了商汤科技的算法研究岗。笔试是在一个在线平台上完成的时间两小时题目不算偏但覆盖面确实比想象中广。很多同学以为算法岗笔试就是刷LeetCode实际上并没有这么简单——至少商汤这场卷子让我明显感觉到它考察的不仅仅是“能不能写代码”更包括你对经典算法原理、机器学习理论和数学推导的熟练程度。如果你正在准备AI算法岗的秋招这篇文章可以帮你快速搞清楚这类笔试到底考什么、怎么准备以及哪些地方容易踩坑。我会把知识点的拆解和实际做题的思路结合起来写不搞那种网上搜得到的大而全的八股。内容比较多但每一步我都尽量给到可以直接落地的方法。1. 笔试整体观察题量与时间分配1.1 这次笔试的题型构成从整场考试来看算法研究岗的笔试更接近“综合能力测试”而不是纯粹的编程竞赛。题目大概分成四个模块数据结构与编码题、机器学习理论题、深度学习相关题、数学基础与推导题。题量不算特别大但每道题都需要动笔算或者写比较完整的代码所以时间其实偏紧。我印象比较深的是编码题只有三道但覆盖了字符串处理、动态规划和数值计算理论题则是在“KNN、聚类、决策树、XGBoost、KL散度、BM25”这些方向里挑了若干个来问有概念解释也有公式推导。这种结构的设计逻辑很清晰研究岗需要的人不只是会调用现成模型而是要能理解模型内部的数学机制并且有能力把算法改造成适合业务场景的工具。1.2 和普通开发岗笔试的区别如果拿商汤这场笔试和普通后端开发岗的笔试对比区别还挺明显的。开发岗经常会大量考察并发、网络协议、数据库这些工程知识而算法研究岗的笔试几乎全是“数学 算法 模型原理”的组合工程性内容很少。这一点其实很值得注意。很多同学前期准备时把重心放在刷LeetCode的高频题上结果一上考场发现大量理论题心里就慌了。所以备战研究岗需要额外花时间去整理机器学习和深度学习里最核心的概念尤其是那些推导过程比较长的内容比如变分推断里的ELBO、集成学习里的Boosting推导、经典的信息检索排序公式BM25等等。1.3 考前复习路线建议我当时准备的资料以这三类为主今天回看依然觉得很有效基础算法类LeetCode Hot 100 剑指Offer高频题重点复习KMP、快速幂、堆排序、Dijkstra、贪心和动态规划这些考察频率极高的题型机器学习理论类李航的《统计学习方法》加周志华的《机器学习》对照着看把SVM、决策树、KNN、聚类、GBDT、XGBoost这些模型的推导吃透深度学习类重点看CNN的基本结构、感受野计算、目标检测主流框架以及训练阶段常用的学习率调整和正则化方法。复习过程中我习惯把每一个知识点都整理成“是什么、为什么用、怎么推、有什么缺点”四段式笔记。这个习惯帮了很大忙笔试里很多问答题其实就是在变相考察这四个维度。2. 编程题复盘经典算法才是主角2.1 字符串专项KMP算法的next数组细节商汤这场笔试里出现了一道和字符串匹配相关的题。题目本身并不是直接让你写出KMP的完整代码而是要求你求解模式串的next数组并说明如何利用它来优化匹配过程。我记得当时卷子里给了一个很典型的模式串就是p abacaba要求写出next数组并分析它的作用。这里先补充一个基础知识点。在使用前缀函数prefix function的KMP实现中π[i]表示模式串前i1个字符组成的子串中最长的相等前后缀长度。以abacaba为例计算过程可以写成这样子串最长相等前后缀π[i]a无0ab无0abaa1abac无0abacaa1abacabab2abacabaaba3如果按照KMP常见的next数组定义next[i]表示匹配失败后跳到哪个位置通常next[0] -1那么对应的数组就是[-1, 0, 0, 1, 0, 1, 2]。别小看这个数组它本质上解决了一个核心问题当主串某个字符与模式串不匹配时模式串的指针不需要从头开始而是跳到一个已经比较过的、前缀和后缀重合的位置从而避免重复比较已经成功匹配的部分。这类题目真正的难点不在于背出代码而在于现场手算时容易搞错前后缀的定义。我一度把“最长相等真前后缀”和“最长公共子串”弄混结果在边界字符上算错。后来学到的技巧是算每一位的时候先写出当前子串的所有前缀和后缀集合再取交集的最大长度这样虽然慢一点但不容易出错。2.2 动态规划与贪心经典题的变形套路笔试的第二道编码题有贪心和动态规划的影子。题目大意是一个任务调度问题给定若干任务的开始时间、结束时间和收益选择若干不重叠的任务使得总收益最大。这道题如果直接看感觉很像“加权区间调度”标准解法是先按结束时间排序然后动态规划处理。状态定义是dp[i]表示前i个任务能获得的最大收益。转移时有两种选择不选第i个任务收益为dp[i-1]选第i个任务则收益为收益[任务i] dp[p(i)]其中p(i)是结束时间不大于任务i开始时间的最后一个任务的下标。最后取两者中的最大值。代码结构大致是这样def max_profit(jobs): # jobs: [(start, end, profit)] jobs.sort(keylambda x: x[1]) # 按结束时间排序 n len(jobs) p [0] * n for i in range(n): # 二分查找前一个不与任务i冲突的任务 lo, hi 0, i - 1 while lo hi: mid (lo hi) // 2 if jobs[mid][1] jobs[i][0]: lo mid 1 else: hi mid - 1 p[i] hi 1 # 个数方便后面dp使用 dp [0] * (n 1) for i in range(1, n 1): dp[i] max(dp[i - 1], jobs[i - 1][2] dp[p[i - 1]]) return dp[n]为什么不用贪心这道题如果直接按结束时间贪心去选往往只能选到“数量最多”或者“总时长最短”的排列无法保证收益最大因为每个任务的权重不同。而动态规划能够在每个决策点同时记录“选”和“不选”两种情况从而覆盖到全局最优解。笔试时遇到这种题先不要急着写代码动手在草稿纸上列一个小的测试用例跑一遍状态转移会大大降低出错概率。2.3 数值计算快速幂与对模运算的考察还有一道数值计算类的编码题要求计算a的b次幂对一个给定模数m取余但b特别大直接循环乘一定超时。这就涉及到快速幂算法。快速幂的核心思路是把指数写成二进制形式。比如计算3^1010的二进制是1010也就是3^10 3^8 * 3^2。代码实现有一个降低复杂度的技巧把幂运算看成是二进制位上的累乘每次迭代将底数平方同时右移指数def fast_pow(a, b, m): res 1 a % m while b 0: if b 1: res res * a % m a a * a % m b 1 return res这题真正需要注意的细节是模运算的时机a在进入循环前先取一次模res每次乘完也立即取模这样每一步的结果都能控制在m的范围内避免溢出。做题时如果忘记对中间结果取模大数场景下很容易导致运行错误。2.4 编程题的做题顺序与考场心态这三道编程题整体难度不算高但组合在一起对时间管理提出了要求。我的做法是先把所有题目扫一遍优先做最长想到思路的题如果某道题想了十分钟还是没有可靠解法就先标记出来回头再做。这样做的好处是确保分数先拿到手不会因为死磕一道题把后面比较轻松的分丢掉。还有一个容易被忽略的细节笔试环境一般只支持Python、C、Java等少数几种语言而且自动评测对输入输出的格式要求极其严格。平时刷LeetCode时习惯了自己补全模板代码但到了在线笔试平台很多题目需要自己处理输入输出和边界条件比如while True循环直到读不到数据。建议提前熟悉目标平台的输入输出方式多练习几套模拟题。3. 机器学习理论题从经典算法到现代模型3.1 KNN、聚类等经典算法的考察要点理论题的第一部分比较基础考察了KNNK近邻和K-means聚类这两个经典算法。这类题看似基础实际上很容易被问倒。比如KNN会问“k值过小或过大会导致什么现象”答案背后对应的是偏差和方差的权衡k值太小模型对噪声非常敏感容易过拟合k值太大决策边界过于平滑可能把远处的样本也纳入考虑导致欠拟合。K-means则会问初始聚类中心的选取。哪怕初始中心选得差一点也有可能导致最终收敛到局部最优簇的划分不理想。更好的做法是使用k-means初始化先随机选第一个中心点然后根据距离平方权重选下一个中心点这样能让中心尽可能分散开。我需要提醒大家一个很容易被忽视的细节K-means算法的本质是期望最大化EM算法的一个特例交替执行“分配样本到最近中心”和“更新中心点位置”两步。如果理解了这个迭代逻辑很多关于收敛性、局部最优的问题都能迎刃而解。3.2 决策树与集成学习XGBoost凭什么强商汤的算法研究岗对集成学习问得比较细尤其是XGBoost。这也不意外XGBoost在工业界和比赛里都是常青树作为AI公司的研究岗自然会关注你是否能理解Boosting模型的本质。决策树部分的基础考题是“信息增益”和“Gini指数”的区别。ID3用信息增益选特征缺点是容易偏向取值多的特征C4.5改成信息增益比来缓解CART则用基尼指数计算更简单还支持回归任务。集成学习部分则重点围绕“Bagging和Boosting的区别”展开。Bagging随机森林通过有放回采样训练多个弱模型再把它们的结果平均或投票目的是降低方差BoostingAdaBoost、GBDT、XGBoost则是逐个训练模型每个新模型重点纠正前面模型犯的错误目的是降低偏差。如果想在笔试里拿到高分最好能把XGBoost的目标函数写出来。它的核心思路是在每一步加入一棵新树f_t(x)优化目标包含两部分真实损失函数L(y, y_hat)和正则项Ω(f_t)。为了优化方便XGBoost对损失函数做二阶泰勒展开同时利用一阶导数和二阶导数来加速求解。这一点经常被用来和普通的GBDT做对比GBDT只用一阶梯度信息而XGBoost引入了二阶梯度收敛更快精度也更高。3.3 检索与排序基础BM25公式解析商汤的业务场景里检索相关的内容并不少。笔试中有一道题直接围绕BM25算法展开问你它和传统TF-IDF模型相比的优势是什么。表面上看BM25是信息检索里的经典排序公式但这类题目考察的本质是“如何从文本中提取有效信号并做加权”。BM25的公式可以写成score(D, Q) Σ IDF(q_i) * (f(q_i, D) * (k1 1)) / (f(q_i, D) k1 * (1 - b b * |D| / avgdl))其中f(q_i, D)表示词q_i在文档D中的词频k1和b是两个调节参数|D|是文档长度avgdl是平均文档长度。它和TF-IDF最大的不同在于对词频的饱和处理词频越高得分增加越慢不会让一个高频词无限拉高得分同时加入文档长度归一化避免长文档天然更容易得分。笔试时如果对这类公式不熟悉很容易卡住。我的建议是备考时不要只盯着视觉和自然语言处理模型信息检索、推荐系统里的一些基础排序公式也要花点时间看。毕竟不少算法研究岗的实际业务都和检索、排序、匹配有关。3.4 概率模型与变分推断KL散度与ELBO这部分的压轴题是关于KL散度和ELBO的推导。我看到题目的时候其实是有点兴奋的因为之前刚好认真推导过一遍变分自编码器的原理没想到笔试里真的考了。KL散度的定义是D_KL(P || Q) Σ P(x) * log(P(x) / Q(x))它的含义是用Q去近似P时损失的信息量。它有一个非常重要的性质不对称性也就是D_KL(P||Q) ! D_KL(Q||P)所以在变分推断里我们优化的是D_KL(q(z) || p(z|x))而不是反过来。ELBO证据下界的推导是变分自编码器的核心。给定观测数据x我们希望最大化对数边际似然log p(x)。引入隐变量z以及近似后验分布q(z)之后可以写成log p(x) ELBO D_KL(q(z) || p(z|x))其中ELBO E_{q(z)}[log p(x|z)] - D_KL(q(z) || p(z))。由于KL散度大于等于0所以ELBO天然是log p(x)的下界。优化ELBO等价于同时最大化重构似然E[log p(x|z)]并最小化近似后验与先验的KL散度。这个结果后来在VAE里被直接用作损失函数前半是重构误差后半是正则项。面试官如果继续追问“为什么要用近似后验而不是直接求真实后验”原因也很简单p(z|x)的分母p(x)通常需要在高维隐变量空间做积分几乎无法解析计算所以只能用变分推断去做近似。能把这层因果讲清楚笔试答案基本就能拿高分了。4. 深度学习与计算机视觉商汤的重点方向4.1 CNN基础卷积、池化与感受野商汤作为一家以计算机视觉起家的AI公司算法研究岗的笔试基本绕不开CNN的相关知识。这部分我需要提醒大家题面有可能问得很基础比如“卷积层输出尺寸怎么计算”也有可能让你直接推导感受野的递推公式如果平时只是用深度学习框架搭模型不关注底层实现大概率会卡住。卷积层输出尺寸的公式很固定out floor((in 2 * padding - kernel_size) / stride) 1如果in32, padding0, kernel_size3, stride1输出就是30。笔试里最常见的一个坑是带padding并且stride大于1时有的同学会忘记向下取整导致尺寸多算或者少算。建议做题时先不看公式自己画一个6x6的输入、3x3的卷积核、stride2的示意图手算一遍输出是2x2还是3x3印象会深刻很多。感受野的递推公式则可以写成RF_{l1} RF_l (k_l - 1) * stride_product其中stride_product是当前层之前所有层的stride乘机。比如一个卷积核3x3、stride2的层叠加在感受野为1的输入上第二层感受野就是1 (3-1) * 2 5。换句话说随着网络加深高层的特征虽然语义更强但空间分辨率在逐渐下降这也是后来很多诸如FPN特征金字塔网络结构的出发点。4.2 目标检测与图像分类主流方案笔试里有一道简答题让你写出几种主流目标检测算法的区别并说明它们的优缺点。我当时的思路是围绕两代模型展开。两阶段检测的代表是Faster R-CNN它先通过区域提议网络RPN选出可能包含目标的候选框再做分类和回归。它的精度比较高但速度相对较慢因为多了区域提议这一步。单阶段检测的代表是YOLO系列和SSD它们直接在特征图上回归目标类别和位置速度更快但早期版本在处理小目标时表现不如两阶段模型。另外一个容易遗忘的点是NMS非极大值抑制。笔试可能会问“NMS为什么要去掉高分框旁边的高分框”答案是目标检测算法会生成大量高度重叠的候选框如果不做NMS同一个物体会被输出成多个检测结果。如何改进NMS比如Soft-NMS也是一些公司喜欢问的延伸方向。4.3 训练阶段的关键细节与调参深度学习部分的最后一个模块和训练经验有关比如如何防止过拟合、学习率如何调整、BatchNorm在训练和推理时的区别是什么。BatchNorm这个问题我几乎在每家AI公司的笔试或面试里都遇到过。先说结论训练时BatchNorm使用当前batch的均值和方差来归一化同时维护一个全局的滑动均值推理时它不再依赖当前batch而是直接使用训练阶段维护好的全局统计量。如果对这两条路径不够熟悉容易在“训练和推理行为差异”这个问题上丢分。学习率调整方面很多同学只知道“学习率太大会震荡太小会收敛慢”但笔试可能问得更细比如“warmup为什么有效”。通常的解释是在训练初期模型参数是随机初始化的梯度方向不准确直接用较大学习率容易把参数带偏所以先用较小的学习率进行一段预热再慢慢提升可以有效提升训练稳定性。5. 数学基础与优化算法推导能力是硬门槛5.1 概率论常考点极大似然估计与贝叶斯公式算法研究岗笔试里概率题几乎属于必考内容。常考的形式有给定一组样本和假设的分布求解参数的最大似然估计或者是给定先验和似然求后验概率。极大似然估计的解题套路很固定先写出所有样本的联合概率再取对数然后对参数求导并令导数为0。比如说假设样本服从正态分布均值参数的最大似然估计其实就是样本均值。关键在于“取对数”这一步——它把连乘变成连加求导才能轻松进行这是整个推导过程中最核心的一个技巧。贝叶斯公式的难点往往在于理清事件之间的条件关系。我给自己的提醒是先把题目文字翻译成“P(A)、P(B|A)、P(A|B)”这样的记号再代入公式不要凭直觉心算否则很容易在条件概率的方向上搞混。5.2 优化算法从梯度下降到模拟退火、粒子群传统优化算法也是笔试的高频点比如梯度下降、模拟退火、粒子群算法。这些优化算法的核心思路是“在参数空间中找到使目标函数最小化的点”只是寻找策略不同。梯度下降是利用目标函数的一阶导数信息来更新参数更新公式是θ θ - lr * ∇J(θ)。它的缺点是容易陷入局部最优尤其在非凸函数上学习率的选择也很关键太大导致发散太小收敛极慢。后来出现的Adam算法通过自适应调节每个参数的学习率在工程中被广泛使用。模拟退火算法的思想来源于物理中的退火过程。它在搜索过程中不仅接受使目标函数变好的解还以一定的概率接受更差的解。这个“以一定概率接受劣解”的机制很重要正是它让算法有可能跳出局部最优逐步收敛到全局最优。笔试里可能会给一个简单的能量函数让你模拟一步Metropolis准则的接受概率只要记住公式P exp(-ΔE / T)就能应对。粒子群算法的核心则是模拟鸟群觅食行为每个粒子有两个关键属性位置和速度。每次迭代粒子会根据自身历史最优位置pbest和群体历史最优位置gbest来更新速度v w * v c1 * r1 * (pbest - x) c2 * r2 * (gbest - x)其中w是惯性权重c1、c2是学习因子r1、r2是随机数。笔试常考的问题是“粒子群和遗传算法的区别”我会从“是否有交叉变异”“是否依赖梯度”“解的表示方式”这几个角度来答。5.3 必备公式与速查清单数学模块内容多且杂我整理了一个速查清单配合题目一起刷效率更高主题核心公式/结论极大似然估计对似然函数取对数求导为零贝叶斯公式P(A|B)P(B|A)P(A)/P(B)KL散度D(P||Q)ΣP·log(P/Q)不对称梯度下降θθ-lr·∇J(θ)模拟退火接受概率Pexp(-ΔE/T)粒子群速度更新vwvc1r1(pbest-x)c2r2(gbest-x)6. 备战算法研究岗笔试的几点心得6.1 复习优先级排序不要瞎努力如果现在让我重新准备一次我会把复习重点按投入产出比排序第一优先级是数据结构和经典算法因为这是每一轮笔试都绕不开的第二优先级是机器学习核心模型推导包括LR、SVM、决策树、XGBoost和EM算法第三优先级才是深度学习与CV基础因为这部分在公司笔试中通常只考重点概念不会考太深的推导。不少同学有一个误区把大量时间花在刷偏题怪题上反而忽略了最基础的数据结构。实际上像数组、链表、栈、队列、二叉树、堆、哈希表这些基础结构的操作才是出现频率最高的。6.2 我是怎么利用刷题平台的我的一个经验是用“专题刷题”代替“随机刷题”。比如这周专门刷动态规划下周专门刷字符串匹配再下周专门刷树和图的遍历。这样做的好处是你能在短时间内在同一个主题下看到大量变体从而总结出规律。另外我强烈建议每隔一天做一次限时模拟。很多同学平时刷题能慢慢想但一到笔试限时环境就崩本质上是缺少时间压力训练。找一套模拟题定好计时器严格按照正式考试的时间分配来做连续练几次之后考场上的节奏感会好很多。6.3 独门技巧用“讲给别人听”的方式复习这个方法我印象很深。在准备机器学习理论时我会把每个模型当成一个小课题自己对着电脑讲一遍通常是用语音会议软件录下来。只要讲到某个环节发现卡壳就说明这个知识点还没有真正掌握马上回去翻资料补上。这种“费曼式复习法”非常适合应对研究岗笔试里的大题因为很多推导题只看理解是不够的要能完整地写在卷面上。只有当你能够不参考任何资料、逻辑清晰地讲出每一步推导时才算真正掌握了。最后再分享一个小细节。笔试前一天晚上不要刷难题尽量把已经整理好的公式、代码模板和错题笔记快速翻阅一遍然后早点休息。考试当天带好草稿纸和水遇到不会的题先跳过不要影响后面模块的发挥。算法研究岗的笔试更像是一个“信息检索”的过程考察的是你在有限时间内能调用多少有效知识——所以平时的积累和组织方式往往比单纯地“读过很多内容”更关键。