京东2018秋招算法工程师笔试题我当年是怎么一步步啃下来的先交代一下背景我参加过那一年京东的秋招投的算法工程师岗。那会儿算法岗还没像现在这么卷但京东这套笔试题已经做得相当有水平了。它不光是考你会不会调包、记不记住公式而是把你对算法最底层那点理解挖得很透。当时做完题出来我最大的感受是这试卷不是用来筛人的是用来教人的——考点覆盖了数据结构、机器学习、深度学习、最优化和工程落地几乎每一道题都能延伸出一大篇文章。我后来带团队面人也总爱拿当年真题里的思路来考新人因为这些题到今天依然不过时。这篇文章就把我当时做的这套题——准确说是这套题要考察的核心知识体系——完整拆一遍。不是简单报答案而是把每类题背后的原理、常见解法、还有我踩过的坑都摆出来给准备算法岗笔试的朋友一个可复用的复习框架。无论你是刚准备投第一份算法实习的在校生还是已经面过几家公司想查漏补缺的求职者这篇文章都能帮你在算法笔试这条路上少走很多弯路。1. 京东2018秋招算法工程师笔试题到底在考什么先说结论这套题的核心不是考“你背了多少个算法”而是考“你理解算法到了什么程度”。整份试卷大概分几大块数据结构与基础算法、机器学习理论、深度学习模型、以及少量工程实践相关的题目。考试时间有限题目量不小跟现在很多大厂笔试不同京东这套题在形式上也融合了选择题、填空题和简答/编程题考察方式比较立体。1.1 从题型分布反推考官的出题逻辑我当时拿到的试卷没有公开的原题编号但根据回忆和同行交流考点分布非常有代表性我整理成下面这张表考点模块典型内容题量占比重点考察能力数据结构与基础算法字符串匹配KMP、排序、贪心、动态规划约30%代码功底与算法思维机器学习理论代价函数、梯度下降、正则化、集成学习约30%对模型原理的理解深度深度学习卷积计算、反向传播、激活函数、RNN/LSTM约25%模型机制与调参直觉数学与最优化概率统计、参数估计、SVM推导、粒子群/模拟退火约15%数学基础和全局优化思维从这个分布能看出京东算法岗不只需要你懂机器学习更要求你有扎实的“算法工程师”基本功。所谓算法工程师不只是调参数的人首先是一个能把数据结构和算法题写得飞起的程序员。不管是KMP的next数组还是排序算法的稳定性分析这些都直接决定你后续能不能真正理解模型的训练过程。这套题其实是在提醒所有求职者别只盯着“高大上”的深度模型最底层的那些算法原理才是决定你上限的东西。1.2 为什么算法岗笔试总爱考经典算法而不是新模型我见过很多同学准备笔试时疯狂看transformer、看BERT结果一打开卷子第一题问的是KMP的next数组怎么求人就懵了。京东这套题里也有这个规律越基础的经典算法越常考。为什么会这样因为经典算法是思维体操。KMP里那个next数组考察的是“当匹配失败时如何利用已知信息跳过不必要的比较”。这个思想在深度学习中也有对应——比如BN批归一化内部就是利用batch统计量让网络训练时减少不必要的参数调整。又比如快排里的分治思想跟决策树的分裂过程如出一辙。考官出这些题不是教你背代码而是想看到你在面对一个已知问题时能不能推导出内在的“状态转移逻辑”。以KMP为例模式串abacaba的next数组推导过程很多人能默写代码但真要手算就出错。原因在于next数组有两种定义一种是next[i]表示“当前字符匹配失败后应该跳转到的位置”另一种是“最长相同前后缀长度”。京东当年就考了后者的变种所以概念不清的人很容易踩坑。后面我会专门用一整节把KMP next数组的几种定义、计算方法和易错点说透——这不是随便写个博客给你抄而是真正从做题角度帮你搞定它。2. 五大必考基础算法深度解析这一部分是整份试卷里最“硬核”的部分也是很多非科班同学的噩梦。说句实在话我当年复习的时候最初能把快速幂手写出来都很费劲但刷完京东这轮笔试题之后我对这堆算法的理解上了一个大台阶。下面这几个算法不夸张地说是算法岗笔试的“必考五位一体”。2.1 KMP算法笔试里的“老熟人”next数组别再背错了KMP是字符串匹配的经典算法。暴力匹配的时间复杂度是O(m*n)KMP能把最坏情况降到O(mn)。它的核心思想是当匹配失败时利用已经匹配成功的部分让模式串尽量向右滑动得更远而不是只移动一位。京东考KMP时特别喜欢考next数组的计算。我们先把定义说清楚。在很多教材里next[i]代表“模式串前i个字符组成的子串中最长相同前后缀的长度”。这个定义下next[0]一般设为-1或0不同教材有差异。还有另一种定义next[i]表示“模式串第i个字符匹配失败后接下来用模式串的第几个字符继续比较”。这两种定义容易混淆。笔试时如果不确定考官的意图可以看题目是否给了初始值和示例。以模式串Pabacaba为例按“最长相同前后缀长度”的定义且next[0]-1的版本我们来手推一下字符串的前缀是指除了最后一个字符外从头部开始的子串后缀是指除了第一个字符外到尾部结束的子串。对于每个位置i我们看P[0:i]这个子串的“最长相等前后缀长度”。i0P[0]a只有一个字符没有前缀也没有后缀按惯例next[0]-1。i1子串ab前缀有a后缀有b没有相同的最长长度0next[1]0。i2子串aba前缀有a,ab后缀有a,ba最长公共前后缀是a长度为1next[2]1。i3子串abac前缀a,ab,aba后缀c,ac,bac没有公共的next[3]0。i4子串abaca前缀a,ab,aba,abac后缀a,ca,aca,baca公共的只有a长度1next[4]1。i5子串abacab前缀a,ab,aba,abac,abaca后缀b,ab,cab,acab,bacab公共的是ab长度为2next[5]2。i6子串abacaba前缀a,ab,aba,abac,abaca,abacab后缀a,ba,aba,caba,acaba,bacaba公共的包括a和aba最长的是aba长度3next[6]3。所以按这个定义Pabacaba的next数组是[-1,0,1,0,1,2,3]。如果题目问的是“匹配失败后跳到哪个位置”假设next数组从0开始且next[i]表示当P[i]与主串不匹配时模式串要回退到的位置下标那么需要把上面的数组做一个平移跳转位置 最长公共前后缀长度对于next[i]来说。具体来说当P[6]匹配失败时我们可以把模式串的P[3]下标3对应的位置拿过来继续比较因为P[0:3]aba已经和主串中刚才匹配的后缀aba相同了。这个平移推导很多人在考场上会算错一位一定要亲自推两遍。2.2 排序算法不只是“背复杂度”还要理解稳定性与逆序对排序几乎是所有笔试的保留节目。京东那年的题涉及排序的变种比如问“归并排序和快速排序谁更稳定为什么”或者“在什么场景下你选择堆排序而不是快排”如果你只是死背“快排平均O(nlogn)最坏O(n^2)不稳定”有些题是会答不好的。关于稳定性的通俗理解如果两个相等元素的相对顺序在排序前后保持不变那么排序算法就是稳定的。为什么重要因为当你按多个关键字排序时比如先按主键再按副键只有稳定的排序才能保证副键排序后不破坏主键的相对顺序。归并排序是稳定的因为合并时遇到相等元素会先取左半部分的元素自然保持原顺序。快速排序不稳定因为partition过程会交换相隔很远的位置导致相等元素的相对顺序可能改变。堆排序也不稳定因为堆的调整过程会跨越大量位置。另外排序和“逆序对”问题紧密相关。归并排序在合并时天然可以统计逆序对数量这是一个经典考点。京东的题目里出现过类似“求一个数组的逆序对数量”的变种题你如果用O(n^2)暴力解在小数据上能过但只要数据量一上来就会超时。用归并排序的话复杂度是O(nlogn)做法是在合并两个有序数组时如果左半边的当前元素大于右半边的当前元素那么左半边当前元素后面的所有元素也都大于右半边当前元素这些元素都可以与右半边当前元素组成逆序对累加即可。这里我给大家一个避坑提示笔试写归并排序时一定要把临时数组的开辟放在递归函数外面复用同一个临时数组否则每一层递归都new一次数组又慢又容易内存溢出。而且递归函数里临时数组的拷贝逻辑如果写错逆序对计数就会差很多务必用小的测试用例验证一下。2.3 贪心与动态规划从“活动选择”到“背包问题”的递推思路贪心和动态规划是算法笔试的“大分题”通常会作为填空题或者编程题出现。京东那年我印象最深的一道题是“会场安排”问题本质是活动选择问题给了若干个活动的开始和结束时间问最多能安排多少个互不重叠的活动。贪心解法大家都知道——按结束时间排序每次选结束最早且与已选活动不冲突的那个。但考试时往往不直接这么问而是给你一组具体数据让你写状态转移方程或者问如果按开始时间排序会得出什么反例。动态规划的重点是状态定义和转移方程。比如经典的0-1背包问题状态dp[i][j]表示考虑前i个物品、背包容量为j时能获得的最大价值转移方程为dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i])。但这里有个优化版——用一维数组滚动更新时内层循环必须从右往左遍历否则一个物品会被重复使用。这个细节非常容易被笔试考到我记得京东的卷子里还真就出了一道关于“完全背包和0-1背包代码差异”的题。如果在考场上一时想不起状态怎么定义我教大家一个笨而有效的办法先暴力递归写出“f(i, capacity)”的返回逻辑然后再看递归中重复计算的参数组合用二维数组把它们记下来就能自然得到动态规划写法。这个方法在时间紧张时特别好用。2.4 快速幂、GCD、二分图HK算法等冷门高频题不要因为冷门就觉得不考。京东的卷子里出现了快速幂的变种一般题目背景会包装成“求x的n次方再mod p”。快速幂的核心是利用二进制分解指数把乘法次数从n降到log n。很多人的误区是只背了递归写法迭代写法容易在指数为正负、模运算的处理上出错。这里建议务必掌握迭代写法def fast_pow(x, n, mod): res 1 base x % mod while n 0: if n 1: res (res * base) % mod base (base * base) % mod n 1 return res注意n如果是负数要先用逆元处理笔试里如果没要求负数幂一般可以只考虑非负整数。二分图HK算法Hopcroft-Karp属于更进阶的内容通常针对“最大匹配”问题的加速。普通匈牙利算法复杂度O(VE)HK算法通过BFS找多条增广路再用DFS同时增广能把复杂度降到O(E√V)。京东这种级别的笔试不太会硬让你默写HK算法但如果题目图形是二分图的匹配问题知道匈牙利算法基本够用。不过我也吃过亏有一道题问“二分图最大匹配时为什么要用HK而不是匈牙利”如果没有提前了解过HK算法的优势这题直接白送。所以建议把两者的适用场景搞清楚至少能说出HK算法通过层次图减少增广次数这个关键点。另外还有Kahn算法属于拓扑排序的一种实现方式。Kahn算法的核心是维护一个入度为0的节点队列每次取出队首节点输出并减少其邻居的入度再把新的入度为0的邻居入队直到队列为空。如果最后输出的节点数不等于图的总数说明图中存在环。京东的题目偶尔会给你一个有向图让你判断是否有环或者给出拓扑排序的一个可能顺序。这类题只要把队列版Kahn写熟基本不会失分。2.5 剪枝、模拟退火与粒子群笔试中的“最优化”思想近年算法岗笔试和面试越来越爱问启发式算法可能是为了考察你对“非精确解”的理解。模拟退火和粒子群算法作为经典的全局优化算法偶尔会在选择题或简答题中出现。京东2018年那一轮我记得有一道题给了一个函数优化问题问“如果要避免陷入局部最优可以怎么做”选项中就有模拟退火和粒子群。模拟退火的思想是把物理退火过程搬到优化问题上从一个初始温度出发在当前解的邻域里随机产生新解计算能量差ΔE如果ΔE0则接受新解否则以概率exp(-ΔE/T)接受较差解。随着温度T逐渐降低接受较差解的概率越来越小最终算法收敛。这里的关键在于“接受较差的解”是为了跳出局部最优这也是它和普通贪心最大的区别。粒子群算法的原理则源自鸟群觅食行为。每个粒子代表解空间中的一个候选解粒子有位置和速度速度更新公式为v[i] wv[i] c1r1*(pbest[i] - x[i]) c2r2(gbest - x[i])x[i] x[i] v[i]其中w是惯性权重c1、c2是学习因子r1、r2是[0,1]随机数pbest是个体历史最优gbest是全局最优。你可能会问为什么笔试会考这个因为粒子群不仅在传统优化里有应用还被用来训练神经网络、优化超参数。考官不是让你手推粒子群收敛性而是希望你对这个经典算法有基本的概念至少知道它和遗传算法、模拟退火有什么区别。复习时抓住每个算法的核心关键词模拟退火温度概率接受粒子群速度更新个体最优/全局最优遗传算法选择/交叉/变异。这个区分度在选择题上非常管用。3. 机器学习与深度学习必考理论避开那些常见的理解误区算法工程师肯定躲不开机器学习理论京东的卷子在这块考得不算深但覆盖范围广。我见过不少同学在“梯度下降为什么能收敛”“什么是正则化”“LSTM怎么解决梯度消失”这类基础题上翻车原因不是不会而是没有从根上理解。下面挑几个高频重点结合我自己的复习笔记来展开。3.1 梯度下降、损失函数与正则化的本质理解京东笔试出现过类似这样一道题“在训练线性回归模型时如果希望防止过拟合可以在损失函数中加入哪一项其作用原理是什么”这题答案是L1或L2正则化但要拿全分必须说清楚L1和L2的区别。L2正则化也叫权重衰减它在损失函数上加上所有参数平方和的λ倍即L L0 λ||w||²。梯度更新时对w求导会得到2λw相当于每一步都在原始梯度下降的基础上让w乘以(1-2ηλ)所以它会让权重趋向较小的值但不会严格为0从而平滑决策边界。L1正则化加的项是λ||w||₁对w求导要么是λ、要么是-λ在w等于0处不可导所以它会推动许多参数精确变为0起到特征选择的作用。还有一个常考细节为什么不能因为加了正则化就不再归一化特征因为如果特征的尺度差异很大L1/L2正则化会倾向于惩罚那些尺度较小的特征因为对应的权重更新时会相对更大导致正则化效果失真。因此预处理阶段的标准归一化不是可选项是必须项。梯度下降的收敛性也是高频考点。我自己的理解方式如果我们把所有样本的损失看成一个曲面那梯度的反方向就是该点下降最快的方向。学习率η决定每一步走多远如果η太大步子跨过谷底来回震荡不收敛如果太小训练缓慢。更形式化地在强凸函数优化问题中选择合适的学习率梯度下降能线性收敛到全局最优。但在深度学习中我们的损失函数通常非凸梯度下降只能收敛到局部极小值或鞍点所以才会引入动量、Adam等优化器来加速逃离鞍点。京东可能考你“动量项的作用”答案可以概括为利用历史的梯度累积增强在梯度方向一致的维度上的更新速度同时抑制震荡。3.2 K-Means、KNN、贝叶斯等经典模型背后的数学直觉这几个模型是机器学习考点的“老演员”。KNN在笔试里经常和“距离度量”一起考比如问“欧式距离与曼哈顿距离的区别”或者问“特征尺度差异明显的场景下KNN为什么要归一化”。KNN的核心是“物以类聚”但它本身没有显式的训练过程所有计算都发生在预测时。对一个新样本计算它与所有训练样本的距离取最近的K个邻居进行投票。K取太小容易受到噪声影响K取太大会抹平类别边界。京东常考的另一个点是“KNN适合处理高维数据吗”答案是不适合因为高维空间中所有点之间的距离越来越接近这就是“维度灾难”。距离的区分度下降KNN的有效性就大打折扣。K-Means聚类则常考“初始中心点怎么选”和“如何确定K”。经典的K-Means初始中心点可以选择随机选K个样本但在坏的情况下可能陷入局部最优。K-Means则按距离加权概率采样初始中心能够显著改善聚类效果。笔试如果让你比较“K-Means和GMM高斯混合模型”的差异可以从“硬分配vs软分配”的角度回答K-Means把每个点硬性分到最近的簇GMM计算每个点属于每个簇的后验概率是软分配。还有一点K-Means假设每个簇是凸形且大小相近如果数据分布是螺旋形或长条形K-Means效果会很差。朴素贝叶斯在京东题目中出现过概率计算类题比如“两个特征的朴素贝叶斯分类器给定先验和条件概率计算后验概率”。核心是贝叶斯公式P(C|X) P(X|C)P(C)/P(X)而朴素贝叶斯的“朴素”之处在于假设特征之间相互独立从而P(X|C) ∏P(x_i|C)。由于分母P(X)对所有类相同实际比较时只需比较分子。还要注意平滑处理如果某个特征值在训练集中从未出现概率会变成0导致整个分子为0。所以拉普拉斯平滑很重要在分子加1、分母加类别数。3.3 SVM、决策树、集成学习中的高频失分点SVM曾经是机器学习笔试的重头戏。京东可能会问“支持向量机中的支持向量指的是什么”“为什么引入核函数”甚至考你“SVM和对数几率回归的区别”。说白了SVM找的是“最大间隔超平面”支持向量就是让这个间隔起作用的那些样本点。引入核函数的目的是把低维线性不可分的数据映射到高维使其线性可分同时不需要显式计算高维特征空间的内积通过核技巧。然而核函数的选择也不是越多越好RBF核适用广泛但要注意γ参数太大会过拟合太小会欠拟合。决策树在笔试里常出现信息增益的计算。比如一个二分类数据集特征A有两个取值怎么计算信息熵和信息增益。信息熵公式大家都会背但计算时会踩坑一定是按“每个取值对应的子集的样本量占比作为权重”来加权求和别再除错样本总数。还有信息增益偏向取值多的特征因此后来的C4.5算法用了增益率信息增益除以特征自身熵来矫正而CART用的是基尼指数。这些细节在京东的简答题里可能占不少分。集成学习这边随机森林和GBDT分别代表了Bagging和Boosting两大流派。随机森林通过有放回抽样bootstrap构造多个决策树并对结果投票或平均能显著降低方差GBDT则是一步步拟合残差降低偏差。笔试里如果问“随机森林中的样本抽样和特征抽样分别解决了什么问题”答案要说到样本抽样增加了树的多样性特征抽样降低树之间相关性从而进一步提升整体泛化能力。GBDT中“为什么用负梯度近似残差”是一个进阶问题因为直接拟合残差在回归任务中比较容易理解但对于任意损失函数残差不一定容易计算而损失函数的负梯度在所有情况下都有定义所以XGBoost、LightGBM都统一用负梯度方向来指导学习。3.4 深度学习笔试核心反向传播计算、卷积过程与常用激活函数深度学习部分是京东算法岗笔试的“分水岭”纯机器学习出身但没怎么写过神经网络的同学很可能在这块丢分。一般来说笔试不会让你手写一个完整的深度神经网络但会让你手算一个简单网络的前向和反向传播。我印象很深的一道题类似这样一个简单的两层全连接网络输入x1第一层权重w10.5偏置b10激活函数用sigmoid第二层权重w20.8偏置b20输出层用线性激活。损失函数用均方误差真实标签y1。题目问经过一次梯度下降后w1更新为多少这题本质是考链式法则需要从损失函数对输出求梯度再回传到第二层再经激活函数的导数和线性乘积累积到第一层。很多人容易漏掉激活函数导数或者忘记乘上输入x。我们先手算一下。第一步第一层线性输出z1 w1 * x 0.5激活输出a1 sigmoid(0.5) ≈ 0.6225。第二步第二层线性输出z2 w2 * a1 0.8 * 0.6225 0.498输出层激活是线性的所以预测值y_pred z2 0.498。损失L 0.5*(y - y_pred)^2用0.5系数方便求导 0.5*(1-0.498)^2 ≈ 0.126。反向传播∂L/∂y_pred -(y - y_pred) -(1 - 0.498) -0.502。∂y_pred/∂z2 1。∂z2/∂w2 a1 0.6225。所以∂L/∂w2 ∂L/∂y_pred * ∂y_pred/∂z2 * ∂z2/∂w2 -0.502 * 1 * 0.6225 ≈ -0.3125。接着往第一层传∂L/∂a1 ∂L/∂y_pred * ∂y_pred/∂z2 * ∂z2/∂a1 -0.502 * 1 * 0.8 -0.4016。再经过sigmoid激活∂a1/∂z1 a1*(1-a1) ≈ 0.6225 * 0.3775 ≈ 0.235。然后∂z1/∂w1 x 1。最终∂L/∂w1 -0.4016 * 0.235 * 1 ≈ -0.0944。如果学习率η0.1则w1更新为0.5 - 0.1*(-0.0944)0.50944。w2更新为0.8 - 0.1*(-0.3125)0.83125。这个手算过程一定要多练几遍笔试时间紧很容易因为小数点保留误差导致选了错误选项。卷积过程的计算也是高频题。给一个输入矩阵和一个卷积核让你算输出特征图大小。公式是out (in - k 2*padding)/stride 1。如果除不尽有的框架会向下取整。京东考过一道带padding的卷积计算题题目不大但计算量不小做的时候务必把公式写出来再带数字别心算。激活函数这边常见考法是比较sigmoid、tanh、ReLU的优缺点。Sigmoid的问题在于饱和区导数趋近0容易导致梯度消失且输出不是零中心的tanh输出是零中心的但同样存在饱和区ReLU解决了正区间梯度消失问题计算也简单但可能出现“神经元死亡”问题负区间梯度恒0因此衍生出LeakyReLU、PReLU等变体。京东笔试中如果问“为什么深度网络不常用sigmoid”至少要从“梯度消失”和“非零中心”两个角度作答。LSTM和GRU也不时在简答题中出现。很多人背结论说“LSTM解决梯度消失”但理解并不深。LSTM引入了遗忘门、输入门和输出门通过一个细胞状态c_t来保存长期信息。反向传播时细胞状态的梯度传递路径中多了一条“直通”边由遗忘门控制相当于给梯度开了一条高速公路使得梯度能够更顺畅地回传从而缓解梯度消失。遗忘门的值接近1时这条路径的梯度衰减很小。GRU则把LSTM的三个门简化成两个门更新门和重置门参数更少在小数据集上不容易过拟合。4. 从京东真题看算法岗笔试的实战策略与刷题方法理论讲完了回到最现实的问题面对一套像京东这样的算法笔试现场怎么分配时间、怎么拿分、怎么避坑。这段内容不是泛泛而谈的“考前要刷题”而是我从亲身经历中总结出来的可行性套路。4.1 拿到卷子后的第一件事别急着从第一题开始做我当年第一次参加某家大厂在线笔试时按顺序从选择题做到最后编程题结果最后编程题时间不够只通过了一半用例吃了大亏。后来我学聪明了不管平台能不能提前翻页我都会先快速把整张试卷的题目扫一遍。这主要是为了做三件事一是标记题目类型和分值。选择题和填空题往往分值小但数量多简答题和编程题分值大但耗时大。二是在脑子里面过一道“哪些题是我一眼就会的哪些题需要多花时间”。先把会做的做掉把能拿的分拿到手这是在线笔试最重要的原则。三是看有没有“陷阱题”。什么叫陷阱题比如题面给了很长的背景故事但实际上就是问一个简单的排序稳定性这时候千万不要被冗长的题干吓住。京东的笔试题目量不算小按我的经验整体时间分配大概是选择题每题不超过1分钟计算类填空题每题3-5分钟简答题每题10分钟编程题每道至少预留20分钟。如果选择题卡住超过2分钟立刻标记一个“待定”然后跳过最后再用剩余时间回来解决。4.2 手写代码的细节决定笔试能否全过编程题是算法笔试的大头也是最容易丢细节分的地方。很多人在本地IDE里写得顺畅一到在线笔试就疯狂报错原因不外乎这几点第一没有考虑输入输出格式。在线笔试经常要求处理多行输入有的输入以逗号分隔有的以空格分隔有的行数不确定。如果main函数里读数据的方式写错整个逻辑再对也白搭。我的习惯是花半分钟把输入样例在草稿纸上模拟一遍再开始写代码框架而不是直接上来就写核心逻辑。第二边界条件不处理。数组长度为0、链表只有一个节点、目标值等于中间值、递归深度过深导致栈溢出等这些边界条件一定要在脑子里过一遍最好写出明确的if分支。第三循环里的指针/索引越界。这个错误特别隐蔽写完代码后一定要用一个小测试用例手动走一遍循环确认每个索引的最大值不超过数组长度减一。还有一点要特别注意不要在编程题中使用复杂的高级技巧来炫技。如果你的代码思路简单但正确哪怕复杂度不是最优也能拿到基础分数。尤其是暴力解法很多时候在数据量小的情况下直接能AC比你在考场上临时想一个复杂的优化算法然后写错要好得多。当然如果明确提示数据规模很大那就必须用效率更高的算法否则部分用例会超时。4.3 简答题的答题技巧按“公式解释例子”三部曲作答京东笔试题中的简答题不是单纯考你默写概念而是更看重你的逻辑表达。比如问“解释KMP的next数组”如果你只把next数组的定义写上去可能只能拿一半分。更好的答法分三步第一步写出next数组的精确定义包括下标含义、取值含义。第二步解释next数组计算的递推逻辑分情况说明当P[i] P[j]时next[i1] j1当不等时j next[j]循环回退。第三步用一个具体例子比如abacaba展示next数组是怎么一步步算出来的并注明用这种递推方式使复杂度达到O(m)。这样回答既覆盖了知识点又展示了推导能力分数自然高。我还见过一个答得不错的同学在解释粒子群算法时他从“鸟群觅食”引入然后给出速度更新公式、位置更新公式再专门解释了参数w/c1/c2的直觉含义最后说了一句“由于随机性的存在粒子群不一定能找到全局最优但通常能在较短时间得到不错的近似解”。考官一看就知道他是真的懂而不是背概念。所以简答题的核心是“用具体式子支撑你的文字”最好能写公式就写公式。4.4 复习路径怎么高效刷算法笔试真题如果你还有1-3个月准备秋招我强烈建议不要漫无目的地刷“题库”。针对京东这种级别的公司建议按下面的节奏来前期基础期花两周把所有基础数据结构过一遍数组、链表、栈、队列、树、图、堆、哈希表。每个数据结构自己实现一遍至少要实现遍历、插入、删除这些基本操作。同时把字符串匹配KMP、排序快排/归并/堆排、二分查找、并查集、拓扑排序、最短路径这些“经典算法模板”写熟练。中间穿插做经典剑指offer题和LeetCode前200题。中期专题期针对机器学习面试中常考的基础算法做专项准备梯度下降手算、反向传播手算、卷积尺寸计算、K-Means迭代过程模拟、朴素贝叶斯概率计算、SVM间隔推导可选、决策树分裂计算、以及粒子群/模拟退火的原理和公式。准备一个笔记本把每个算法的“一句话概念核心公式优缺点典型应用”记下来考前翻这个本子效率最高。后期冲刺期找3-5套历年大厂真题做模拟考试严格按照考试时间。做完后不要只对答案一定要把每道错题都按“正确思路”重新推一遍并总结错误类型“概念不清楚”、“计算粗心”、“代码没跑通”分别记录。我当年专门建了一个错题本最后效果非常好。错题本里还要记录时间分配失误比如哪道题花了太多时间导致后面来不及。5. 常见问题与排查技巧实录帮你少踩80%的坑从我自己和身边同学的实战反馈来看算法笔试中有些坑是重复出现的。以下挑了几个典型问题用“现象-原因-解决”的方式整理成速查表这也算是我这几年做算法题的经验沉淀。5.1 手算next数组总是差一位怎么排查现象KMP的next数组手算结果和标准答案总差一位。原因绝大多数情况是next[i]的定义或者下标起点不一致。有的教材定义“next[j]表示当模式串第j个字符匹配失败后从模式串下标为next[j]的字符开始继续比较”这时next[0]通常是-1next[1] 0。而有些题目定义“next[i]为前i个字符最长相同前后缀长度”下标从0开始next[1]0next[2]1。如果不仔细读题极易偏移一位。解决方式考场上先圈出题目中的定义如果是计算题直接按定义来如果是代码填空题看它给出的初始next[0]是-1还是0再决定后续递推。平时复习时把两种定义各手推一遍abacaba这样不管考哪种定义都能快速适应。我再强调一下唯一保险的办法拿到题目先写一个小的测试字符串比如abab用定义手推一遍验证自己的理解和题目给的一致后再正式计算。5.2 动态规划代码在笔试里总爆栈怎么办现象递归版动态规划在测试用例较大时栈溢出或者运行超时。原因递归深度太大每层递归消耗系统栈空间数据量大时自然会溢出。另外某些递归写法中每个状态的计算没有做“记忆化”导致重复计算复杂度爆炸。解决方式第一优先写成迭代版自底向上。如果空间不够可以用滚动数组压缩维度。第二如果必须用递归别忘了添加lru_cachePython或使用vectorvector memo手动记忆化。第三笔试前要练习几道“递归转迭代”的题例如斐波那契、爬楼梯、0-1背包确保能快速切换写法。5.3 代码本地跑能过粘贴到在线编辑器就编译错误现象本地IDE一切正常复制到牛客/赛码等平台后编译报错或者运行时异常。原因常见原因包括main函数返回类型写错有的平台要求int有的要求void但一般int更稳妥没有引入必要的头文件使用了本地编译器特有扩展或者读取输入时用了不支持的函数。还有一种特别坑的情况是代码里混入了不可见字符如中文标点、全角括号——从网页复制代码时很容易发生。解决方式无论多着急提交前都手动检查头文件、括号是否为半角、main函数签名。另外建议使用Python写在线笔试的同学不要用sys.setrecursionlimit做过大的递归限制有的平台并不支持还是优先用迭代思路。最后一个小经验在线笔试平台也有自己的“本地调试”功能有条件的话写完代码后先在平台的示例输入上跑一遍确认输出完全一致再提交。5.4 遇到没见过的算法题现场怎么“蒙”思路现象题目背景很陌生或者看起来像是某个冷门算法完全没思路。原因其实就是遇到新题慌了。实际上很多所谓的冷门算法题都是经典模型的变种。解决方式我总结了一个“四步蒙题法”。第一步看数据范围如果n很小比如n≤20可以先考虑暴力枚举或状态压缩如果n在10^5级别多半是排序、二分、贪心、动态规划如果n在10^5~10^6而且要求O(nlogn)优先考虑树状数组、线段树、堆等。第二步把问题抽象成已知模型它是不是一个“最大值最小”问题那就大概率是二分答案是不是“区间内统计某种特征”可能是前缀和或滑动窗口是不是“两个集合匹配”可能是二分图匹配。第三步写一个最简单的暴力解再想能不能优化。第四步如果暴力解也不行想想题目的限制条件有没有可以利用的性质比如数据单调性、无环性、单调栈等。说实话京东级别的笔试更侧重基础应用很少会出现真正偏门的算法所以把经典模型吃透大部分题都能解。6. 一份可复现的算法笔试冲刺计划以30天为例很多同学问我距离笔试还有一个多月现在还来得及吗我的回答是来得及但必须有节奏。下面这份计划是我当年亲身实践过的之后也推荐给学弟学妹反馈都不错。当然你可以根据自己的基础调整但我建议整体节奏不要乱。6.1 第1-10天基础算法模板速过这个阶段的重点是“会写、写对、写快”。每人每天至少手写代码5道题题目类别可以按这样分配第1-2天把数组、链表、栈、队列的基础题练熟第3-4天练排序和二分查找尤其是快排、归并排序的代码要能默写第5-6天练树和图的遍历DFS/BFS要烂熟于心第7-8天练贪心和动态规划至少能做经典背包、最长公共子序列、最长递增子序列第9-10天练字符串和数学题重点是KMP、快速幂、大数运算。每道题写完不要急着看题解先自己构造几个测试用例看能不能通过。如果错先自己想错在哪实在想不出再看。这个“先想”的过程比单纯刷题重要得多。我见过不少同学刷了很多题但进步有限就是因为一直处于“看题-看答案-抄一遍”的循环里大脑没有主动思考。6.2 第11-20天机器学习与深度学习基础夺分不要以为笔试里机器学习的题不写代码就不重要。事实上京东这类公司的算法工程师笔试中选择题和填空里机器学习占的分值甚至能接近编程题。这个阶段复习重点放在手算推导上。每天选一个模型做“手算题”比如今天手算线性回归的梯度下降一步明天手算K-Means的一次迭代后天手算朴素贝叶斯后验概率。深度学习方面每天手推一个反向传播例子并练习计算卷积核输出尺寸。同时把机器学习经典模型思维导图整理出来每个模型要求自己用三句话讲清楚“解决了什么问题、核心假设是什么、如何训练参数”。可能有些同学觉得“三句话”太简单但实际上如果你能用三句话给一个完全不懂的人讲明白你就真的懂了。6.3 第21-27天整套真题模拟与错题复盘这个阶段找一个安静的时间模拟真实考试环境。每天上午一套往年真题如果找不到京东的原题用其他大厂的也可以只要难度接近下午花时间复盘。复盘不是对答案而是把每道题对应的知识点重新产出一份笔记。比如你今天做错了一道“粒子群算法”的选择题就把粒子群的公式、迭代流程、优缺点整理成半页纸。晚上再把当天所有错题知识点再过一遍。错题本建议电子化方便后期检索。我当时就在Notion里建了一个表字段包括题目来源、知识点、错误类型概念/计算/代码、错因描述、正确思路。这样到考前最后一天直接翻这个表效率极高。6.4 第28-30天查漏补缺与状态调整最后三天不要刷新题了重点看之前整理的笔记和错题本。把那些“一看就会一写就错”的算法模板再手写一遍KMP、归并排序、快速幂、二叉树非递归遍历、Dijkstra、Kahn拓扑排序。同时把机器学习常考公式再过一遍信息增益、基尼指数、SVM间隔、LSTM门控、梯度下降更新式、粒子群更新式。考前保证充足睡眠尤其不要熬夜刷题。我的个人感受是算法笔试非常吃状态一旦脑子发懵连简单的快排边界都会写错。提前一天把身份证、电脑、充电器、网络环境准备好在线笔试的话还要提前测试摄像机位是否正常。7. 我的用券“心法”与考试时间管理最后再分享几个笔试现场特别实用的时间管理技巧。第一个技巧是“5分钟热身法”。开考前5分钟先在草稿纸上默写一遍常用的算法模板和公式——比如快排分区函数、KMP的next循环、快速幂代码、卷积尺寸公式、信息增益公式。这像运动员比赛前要热身一样让你脑子迅速进入状态。我每次笔试都这么做效果很明显。第二个技巧是“两轮答题法”。第一轮只做确定性极高且耗时短的题把能拿的分全部拿到手。第二轮再花时间做计算量大的题和编程题。这样即使某一道计算题花掉了时间也不至于出现“全卷大空白”的惨状。第三个技巧是“相信第一直觉”。选择题中如果你对某个选项很有把握不要随便改。考场上第一直觉往往是建立在平时积累上的快速模式匹配除非你发现明显的计算错误否则不要因为“怕错”就反复改答案。我亲身经历过改错比不改错的机会大得多。第四个技巧是“不会的题也要写步骤”。尤其是简答题只要写出相关公式、概念、甚至一个简单的例子都有可能得到部分分数。千万不要完全留白。比如问“模拟退火如何避免局部最优”哪怕你只写出“以一定概率接受较差解”这句话也能拿几分。在竞争激烈的算法岗招聘中一分之差可能就决定能否进入面试所以任何得分机会都要抓住。说到底京东2018秋招算法工程师笔试题本身并不是要难倒所有人它更是在用一种系统化的方式测试你是否具备算法工程师的底层素养。如果你能把上面这些知识点融会贯通再配合合理的复习计划绝对不只是应对京东其他大厂的技术笔试也能轻松上手。算法这条路没有捷径每一次推导、每一道代码、每一页错题笔记最终都会成为你拿到offer路上的垫脚石。
京东2018秋招算法工程师笔试题我当年是怎么一步步啃下来的先交代一下背景我参加过那一年京东的秋招投的算法工程师岗。那会儿算法岗还没像现在这么卷但京东这套笔试题已经做得相当有水平了。它不光是考你会不会调包、记不记住公式而是把你对算法最底层那点理解挖得很透。当时做完题出来我最大的感受是这试卷不是用来筛人的是用来教人的——考点覆盖了数据结构、机器学习、深度学习、最优化和工程落地几乎每一道题都能延伸出一大篇文章。我后来带团队面人也总爱拿当年真题里的思路来考新人因为这些题到今天依然不过时。这篇文章就把我当时做的这套题——准确说是这套题要考察的核心知识体系——完整拆一遍。不是简单报答案而是把每类题背后的原理、常见解法、还有我踩过的坑都摆出来给准备算法岗笔试的朋友一个可复用的复习框架。无论你是刚准备投第一份算法实习的在校生还是已经面过几家公司想查漏补缺的求职者这篇文章都能帮你在算法笔试这条路上少走很多弯路。1. 京东2018秋招算法工程师笔试题到底在考什么先说结论这套题的核心不是考“你背了多少个算法”而是考“你理解算法到了什么程度”。整份试卷大概分几大块数据结构与基础算法、机器学习理论、深度学习模型、以及少量工程实践相关的题目。考试时间有限题目量不小跟现在很多大厂笔试不同京东这套题在形式上也融合了选择题、填空题和简答/编程题考察方式比较立体。1.1 从题型分布反推考官的出题逻辑我当时拿到的试卷没有公开的原题编号但根据回忆和同行交流考点分布非常有代表性我整理成下面这张表考点模块典型内容题量占比重点考察能力数据结构与基础算法字符串匹配KMP、排序、贪心、动态规划约30%代码功底与算法思维机器学习理论代价函数、梯度下降、正则化、集成学习约30%对模型原理的理解深度深度学习卷积计算、反向传播、激活函数、RNN/LSTM约25%模型机制与调参直觉数学与最优化概率统计、参数估计、SVM推导、粒子群/模拟退火约15%数学基础和全局优化思维从这个分布能看出京东算法岗不只需要你懂机器学习更要求你有扎实的“算法工程师”基本功。所谓算法工程师不只是调参数的人首先是一个能把数据结构和算法题写得飞起的程序员。不管是KMP的next数组还是排序算法的稳定性分析这些都直接决定你后续能不能真正理解模型的训练过程。这套题其实是在提醒所有求职者别只盯着“高大上”的深度模型最底层的那些算法原理才是决定你上限的东西。1.2 为什么算法岗笔试总爱考经典算法而不是新模型我见过很多同学准备笔试时疯狂看transformer、看BERT结果一打开卷子第一题问的是KMP的next数组怎么求人就懵了。京东这套题里也有这个规律越基础的经典算法越常考。为什么会这样因为经典算法是思维体操。KMP里那个next数组考察的是“当匹配失败时如何利用已知信息跳过不必要的比较”。这个思想在深度学习中也有对应——比如BN批归一化内部就是利用batch统计量让网络训练时减少不必要的参数调整。又比如快排里的分治思想跟决策树的分裂过程如出一辙。考官出这些题不是教你背代码而是想看到你在面对一个已知问题时能不能推导出内在的“状态转移逻辑”。以KMP为例模式串abacaba的next数组推导过程很多人能默写代码但真要手算就出错。原因在于next数组有两种定义一种是next[i]表示“当前字符匹配失败后应该跳转到的位置”另一种是“最长相同前后缀长度”。京东当年就考了后者的变种所以概念不清的人很容易踩坑。后面我会专门用一整节把KMP next数组的几种定义、计算方法和易错点说透——这不是随便写个博客给你抄而是真正从做题角度帮你搞定它。2. 五大必考基础算法深度解析这一部分是整份试卷里最“硬核”的部分也是很多非科班同学的噩梦。说句实在话我当年复习的时候最初能把快速幂手写出来都很费劲但刷完京东这轮笔试题之后我对这堆算法的理解上了一个大台阶。下面这几个算法不夸张地说是算法岗笔试的“必考五位一体”。2.1 KMP算法笔试里的“老熟人”next数组别再背错了KMP是字符串匹配的经典算法。暴力匹配的时间复杂度是O(m*n)KMP能把最坏情况降到O(mn)。它的核心思想是当匹配失败时利用已经匹配成功的部分让模式串尽量向右滑动得更远而不是只移动一位。京东考KMP时特别喜欢考next数组的计算。我们先把定义说清楚。在很多教材里next[i]代表“模式串前i个字符组成的子串中最长相同前后缀的长度”。这个定义下next[0]一般设为-1或0不同教材有差异。还有另一种定义next[i]表示“模式串第i个字符匹配失败后接下来用模式串的第几个字符继续比较”。这两种定义容易混淆。笔试时如果不确定考官的意图可以看题目是否给了初始值和示例。以模式串Pabacaba为例按“最长相同前后缀长度”的定义且next[0]-1的版本我们来手推一下字符串的前缀是指除了最后一个字符外从头部开始的子串后缀是指除了第一个字符外到尾部结束的子串。对于每个位置i我们看P[0:i]这个子串的“最长相等前后缀长度”。i0P[0]a只有一个字符没有前缀也没有后缀按惯例next[0]-1。i1子串ab前缀有a后缀有b没有相同的最长长度0next[1]0。i2子串aba前缀有a,ab后缀有a,ba最长公共前后缀是a长度为1next[2]1。i3子串abac前缀a,ab,aba后缀c,ac,bac没有公共的next[3]0。i4子串abaca前缀a,ab,aba,abac后缀a,ca,aca,baca公共的只有a长度1next[4]1。i5子串abacab前缀a,ab,aba,abac,abaca后缀b,ab,cab,acab,bacab公共的是ab长度为2next[5]2。i6子串abacaba前缀a,ab,aba,abac,abaca,abacab后缀a,ba,aba,caba,acaba,bacaba公共的包括a和aba最长的是aba长度3next[6]3。所以按这个定义Pabacaba的next数组是[-1,0,1,0,1,2,3]。如果题目问的是“匹配失败后跳到哪个位置”假设next数组从0开始且next[i]表示当P[i]与主串不匹配时模式串要回退到的位置下标那么需要把上面的数组做一个平移跳转位置 最长公共前后缀长度对于next[i]来说。具体来说当P[6]匹配失败时我们可以把模式串的P[3]下标3对应的位置拿过来继续比较因为P[0:3]aba已经和主串中刚才匹配的后缀aba相同了。这个平移推导很多人在考场上会算错一位一定要亲自推两遍。2.2 排序算法不只是“背复杂度”还要理解稳定性与逆序对排序几乎是所有笔试的保留节目。京东那年的题涉及排序的变种比如问“归并排序和快速排序谁更稳定为什么”或者“在什么场景下你选择堆排序而不是快排”如果你只是死背“快排平均O(nlogn)最坏O(n^2)不稳定”有些题是会答不好的。关于稳定性的通俗理解如果两个相等元素的相对顺序在排序前后保持不变那么排序算法就是稳定的。为什么重要因为当你按多个关键字排序时比如先按主键再按副键只有稳定的排序才能保证副键排序后不破坏主键的相对顺序。归并排序是稳定的因为合并时遇到相等元素会先取左半部分的元素自然保持原顺序。快速排序不稳定因为partition过程会交换相隔很远的位置导致相等元素的相对顺序可能改变。堆排序也不稳定因为堆的调整过程会跨越大量位置。另外排序和“逆序对”问题紧密相关。归并排序在合并时天然可以统计逆序对数量这是一个经典考点。京东的题目里出现过类似“求一个数组的逆序对数量”的变种题你如果用O(n^2)暴力解在小数据上能过但只要数据量一上来就会超时。用归并排序的话复杂度是O(nlogn)做法是在合并两个有序数组时如果左半边的当前元素大于右半边的当前元素那么左半边当前元素后面的所有元素也都大于右半边当前元素这些元素都可以与右半边当前元素组成逆序对累加即可。这里我给大家一个避坑提示笔试写归并排序时一定要把临时数组的开辟放在递归函数外面复用同一个临时数组否则每一层递归都new一次数组又慢又容易内存溢出。而且递归函数里临时数组的拷贝逻辑如果写错逆序对计数就会差很多务必用小的测试用例验证一下。2.3 贪心与动态规划从“活动选择”到“背包问题”的递推思路贪心和动态规划是算法笔试的“大分题”通常会作为填空题或者编程题出现。京东那年我印象最深的一道题是“会场安排”问题本质是活动选择问题给了若干个活动的开始和结束时间问最多能安排多少个互不重叠的活动。贪心解法大家都知道——按结束时间排序每次选结束最早且与已选活动不冲突的那个。但考试时往往不直接这么问而是给你一组具体数据让你写状态转移方程或者问如果按开始时间排序会得出什么反例。动态规划的重点是状态定义和转移方程。比如经典的0-1背包问题状态dp[i][j]表示考虑前i个物品、背包容量为j时能获得的最大价值转移方程为dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i])。但这里有个优化版——用一维数组滚动更新时内层循环必须从右往左遍历否则一个物品会被重复使用。这个细节非常容易被笔试考到我记得京东的卷子里还真就出了一道关于“完全背包和0-1背包代码差异”的题。如果在考场上一时想不起状态怎么定义我教大家一个笨而有效的办法先暴力递归写出“f(i, capacity)”的返回逻辑然后再看递归中重复计算的参数组合用二维数组把它们记下来就能自然得到动态规划写法。这个方法在时间紧张时特别好用。2.4 快速幂、GCD、二分图HK算法等冷门高频题不要因为冷门就觉得不考。京东的卷子里出现了快速幂的变种一般题目背景会包装成“求x的n次方再mod p”。快速幂的核心是利用二进制分解指数把乘法次数从n降到log n。很多人的误区是只背了递归写法迭代写法容易在指数为正负、模运算的处理上出错。这里建议务必掌握迭代写法def fast_pow(x, n, mod): res 1 base x % mod while n 0: if n 1: res (res * base) % mod base (base * base) % mod n 1 return res注意n如果是负数要先用逆元处理笔试里如果没要求负数幂一般可以只考虑非负整数。二分图HK算法Hopcroft-Karp属于更进阶的内容通常针对“最大匹配”问题的加速。普通匈牙利算法复杂度O(VE)HK算法通过BFS找多条增广路再用DFS同时增广能把复杂度降到O(E√V)。京东这种级别的笔试不太会硬让你默写HK算法但如果题目图形是二分图的匹配问题知道匈牙利算法基本够用。不过我也吃过亏有一道题问“二分图最大匹配时为什么要用HK而不是匈牙利”如果没有提前了解过HK算法的优势这题直接白送。所以建议把两者的适用场景搞清楚至少能说出HK算法通过层次图减少增广次数这个关键点。另外还有Kahn算法属于拓扑排序的一种实现方式。Kahn算法的核心是维护一个入度为0的节点队列每次取出队首节点输出并减少其邻居的入度再把新的入度为0的邻居入队直到队列为空。如果最后输出的节点数不等于图的总数说明图中存在环。京东的题目偶尔会给你一个有向图让你判断是否有环或者给出拓扑排序的一个可能顺序。这类题只要把队列版Kahn写熟基本不会失分。2.5 剪枝、模拟退火与粒子群笔试中的“最优化”思想近年算法岗笔试和面试越来越爱问启发式算法可能是为了考察你对“非精确解”的理解。模拟退火和粒子群算法作为经典的全局优化算法偶尔会在选择题或简答题中出现。京东2018年那一轮我记得有一道题给了一个函数优化问题问“如果要避免陷入局部最优可以怎么做”选项中就有模拟退火和粒子群。模拟退火的思想是把物理退火过程搬到优化问题上从一个初始温度出发在当前解的邻域里随机产生新解计算能量差ΔE如果ΔE0则接受新解否则以概率exp(-ΔE/T)接受较差解。随着温度T逐渐降低接受较差解的概率越来越小最终算法收敛。这里的关键在于“接受较差的解”是为了跳出局部最优这也是它和普通贪心最大的区别。粒子群算法的原理则源自鸟群觅食行为。每个粒子代表解空间中的一个候选解粒子有位置和速度速度更新公式为v[i] wv[i] c1r1*(pbest[i] - x[i]) c2r2(gbest - x[i])x[i] x[i] v[i]其中w是惯性权重c1、c2是学习因子r1、r2是[0,1]随机数pbest是个体历史最优gbest是全局最优。你可能会问为什么笔试会考这个因为粒子群不仅在传统优化里有应用还被用来训练神经网络、优化超参数。考官不是让你手推粒子群收敛性而是希望你对这个经典算法有基本的概念至少知道它和遗传算法、模拟退火有什么区别。复习时抓住每个算法的核心关键词模拟退火温度概率接受粒子群速度更新个体最优/全局最优遗传算法选择/交叉/变异。这个区分度在选择题上非常管用。3. 机器学习与深度学习必考理论避开那些常见的理解误区算法工程师肯定躲不开机器学习理论京东的卷子在这块考得不算深但覆盖范围广。我见过不少同学在“梯度下降为什么能收敛”“什么是正则化”“LSTM怎么解决梯度消失”这类基础题上翻车原因不是不会而是没有从根上理解。下面挑几个高频重点结合我自己的复习笔记来展开。3.1 梯度下降、损失函数与正则化的本质理解京东笔试出现过类似这样一道题“在训练线性回归模型时如果希望防止过拟合可以在损失函数中加入哪一项其作用原理是什么”这题答案是L1或L2正则化但要拿全分必须说清楚L1和L2的区别。L2正则化也叫权重衰减它在损失函数上加上所有参数平方和的λ倍即L L0 λ||w||²。梯度更新时对w求导会得到2λw相当于每一步都在原始梯度下降的基础上让w乘以(1-2ηλ)所以它会让权重趋向较小的值但不会严格为0从而平滑决策边界。L1正则化加的项是λ||w||₁对w求导要么是λ、要么是-λ在w等于0处不可导所以它会推动许多参数精确变为0起到特征选择的作用。还有一个常考细节为什么不能因为加了正则化就不再归一化特征因为如果特征的尺度差异很大L1/L2正则化会倾向于惩罚那些尺度较小的特征因为对应的权重更新时会相对更大导致正则化效果失真。因此预处理阶段的标准归一化不是可选项是必须项。梯度下降的收敛性也是高频考点。我自己的理解方式如果我们把所有样本的损失看成一个曲面那梯度的反方向就是该点下降最快的方向。学习率η决定每一步走多远如果η太大步子跨过谷底来回震荡不收敛如果太小训练缓慢。更形式化地在强凸函数优化问题中选择合适的学习率梯度下降能线性收敛到全局最优。但在深度学习中我们的损失函数通常非凸梯度下降只能收敛到局部极小值或鞍点所以才会引入动量、Adam等优化器来加速逃离鞍点。京东可能考你“动量项的作用”答案可以概括为利用历史的梯度累积增强在梯度方向一致的维度上的更新速度同时抑制震荡。3.2 K-Means、KNN、贝叶斯等经典模型背后的数学直觉这几个模型是机器学习考点的“老演员”。KNN在笔试里经常和“距离度量”一起考比如问“欧式距离与曼哈顿距离的区别”或者问“特征尺度差异明显的场景下KNN为什么要归一化”。KNN的核心是“物以类聚”但它本身没有显式的训练过程所有计算都发生在预测时。对一个新样本计算它与所有训练样本的距离取最近的K个邻居进行投票。K取太小容易受到噪声影响K取太大会抹平类别边界。京东常考的另一个点是“KNN适合处理高维数据吗”答案是不适合因为高维空间中所有点之间的距离越来越接近这就是“维度灾难”。距离的区分度下降KNN的有效性就大打折扣。K-Means聚类则常考“初始中心点怎么选”和“如何确定K”。经典的K-Means初始中心点可以选择随机选K个样本但在坏的情况下可能陷入局部最优。K-Means则按距离加权概率采样初始中心能够显著改善聚类效果。笔试如果让你比较“K-Means和GMM高斯混合模型”的差异可以从“硬分配vs软分配”的角度回答K-Means把每个点硬性分到最近的簇GMM计算每个点属于每个簇的后验概率是软分配。还有一点K-Means假设每个簇是凸形且大小相近如果数据分布是螺旋形或长条形K-Means效果会很差。朴素贝叶斯在京东题目中出现过概率计算类题比如“两个特征的朴素贝叶斯分类器给定先验和条件概率计算后验概率”。核心是贝叶斯公式P(C|X) P(X|C)P(C)/P(X)而朴素贝叶斯的“朴素”之处在于假设特征之间相互独立从而P(X|C) ∏P(x_i|C)。由于分母P(X)对所有类相同实际比较时只需比较分子。还要注意平滑处理如果某个特征值在训练集中从未出现概率会变成0导致整个分子为0。所以拉普拉斯平滑很重要在分子加1、分母加类别数。3.3 SVM、决策树、集成学习中的高频失分点SVM曾经是机器学习笔试的重头戏。京东可能会问“支持向量机中的支持向量指的是什么”“为什么引入核函数”甚至考你“SVM和对数几率回归的区别”。说白了SVM找的是“最大间隔超平面”支持向量就是让这个间隔起作用的那些样本点。引入核函数的目的是把低维线性不可分的数据映射到高维使其线性可分同时不需要显式计算高维特征空间的内积通过核技巧。然而核函数的选择也不是越多越好RBF核适用广泛但要注意γ参数太大会过拟合太小会欠拟合。决策树在笔试里常出现信息增益的计算。比如一个二分类数据集特征A有两个取值怎么计算信息熵和信息增益。信息熵公式大家都会背但计算时会踩坑一定是按“每个取值对应的子集的样本量占比作为权重”来加权求和别再除错样本总数。还有信息增益偏向取值多的特征因此后来的C4.5算法用了增益率信息增益除以特征自身熵来矫正而CART用的是基尼指数。这些细节在京东的简答题里可能占不少分。集成学习这边随机森林和GBDT分别代表了Bagging和Boosting两大流派。随机森林通过有放回抽样bootstrap构造多个决策树并对结果投票或平均能显著降低方差GBDT则是一步步拟合残差降低偏差。笔试里如果问“随机森林中的样本抽样和特征抽样分别解决了什么问题”答案要说到样本抽样增加了树的多样性特征抽样降低树之间相关性从而进一步提升整体泛化能力。GBDT中“为什么用负梯度近似残差”是一个进阶问题因为直接拟合残差在回归任务中比较容易理解但对于任意损失函数残差不一定容易计算而损失函数的负梯度在所有情况下都有定义所以XGBoost、LightGBM都统一用负梯度方向来指导学习。3.4 深度学习笔试核心反向传播计算、卷积过程与常用激活函数深度学习部分是京东算法岗笔试的“分水岭”纯机器学习出身但没怎么写过神经网络的同学很可能在这块丢分。一般来说笔试不会让你手写一个完整的深度神经网络但会让你手算一个简单网络的前向和反向传播。我印象很深的一道题类似这样一个简单的两层全连接网络输入x1第一层权重w10.5偏置b10激活函数用sigmoid第二层权重w20.8偏置b20输出层用线性激活。损失函数用均方误差真实标签y1。题目问经过一次梯度下降后w1更新为多少这题本质是考链式法则需要从损失函数对输出求梯度再回传到第二层再经激活函数的导数和线性乘积累积到第一层。很多人容易漏掉激活函数导数或者忘记乘上输入x。我们先手算一下。第一步第一层线性输出z1 w1 * x 0.5激活输出a1 sigmoid(0.5) ≈ 0.6225。第二步第二层线性输出z2 w2 * a1 0.8 * 0.6225 0.498输出层激活是线性的所以预测值y_pred z2 0.498。损失L 0.5*(y - y_pred)^2用0.5系数方便求导 0.5*(1-0.498)^2 ≈ 0.126。反向传播∂L/∂y_pred -(y - y_pred) -(1 - 0.498) -0.502。∂y_pred/∂z2 1。∂z2/∂w2 a1 0.6225。所以∂L/∂w2 ∂L/∂y_pred * ∂y_pred/∂z2 * ∂z2/∂w2 -0.502 * 1 * 0.6225 ≈ -0.3125。接着往第一层传∂L/∂a1 ∂L/∂y_pred * ∂y_pred/∂z2 * ∂z2/∂a1 -0.502 * 1 * 0.8 -0.4016。再经过sigmoid激活∂a1/∂z1 a1*(1-a1) ≈ 0.6225 * 0.3775 ≈ 0.235。然后∂z1/∂w1 x 1。最终∂L/∂w1 -0.4016 * 0.235 * 1 ≈ -0.0944。如果学习率η0.1则w1更新为0.5 - 0.1*(-0.0944)0.50944。w2更新为0.8 - 0.1*(-0.3125)0.83125。这个手算过程一定要多练几遍笔试时间紧很容易因为小数点保留误差导致选了错误选项。卷积过程的计算也是高频题。给一个输入矩阵和一个卷积核让你算输出特征图大小。公式是out (in - k 2*padding)/stride 1。如果除不尽有的框架会向下取整。京东考过一道带padding的卷积计算题题目不大但计算量不小做的时候务必把公式写出来再带数字别心算。激活函数这边常见考法是比较sigmoid、tanh、ReLU的优缺点。Sigmoid的问题在于饱和区导数趋近0容易导致梯度消失且输出不是零中心的tanh输出是零中心的但同样存在饱和区ReLU解决了正区间梯度消失问题计算也简单但可能出现“神经元死亡”问题负区间梯度恒0因此衍生出LeakyReLU、PReLU等变体。京东笔试中如果问“为什么深度网络不常用sigmoid”至少要从“梯度消失”和“非零中心”两个角度作答。LSTM和GRU也不时在简答题中出现。很多人背结论说“LSTM解决梯度消失”但理解并不深。LSTM引入了遗忘门、输入门和输出门通过一个细胞状态c_t来保存长期信息。反向传播时细胞状态的梯度传递路径中多了一条“直通”边由遗忘门控制相当于给梯度开了一条高速公路使得梯度能够更顺畅地回传从而缓解梯度消失。遗忘门的值接近1时这条路径的梯度衰减很小。GRU则把LSTM的三个门简化成两个门更新门和重置门参数更少在小数据集上不容易过拟合。4. 从京东真题看算法岗笔试的实战策略与刷题方法理论讲完了回到最现实的问题面对一套像京东这样的算法笔试现场怎么分配时间、怎么拿分、怎么避坑。这段内容不是泛泛而谈的“考前要刷题”而是我从亲身经历中总结出来的可行性套路。4.1 拿到卷子后的第一件事别急着从第一题开始做我当年第一次参加某家大厂在线笔试时按顺序从选择题做到最后编程题结果最后编程题时间不够只通过了一半用例吃了大亏。后来我学聪明了不管平台能不能提前翻页我都会先快速把整张试卷的题目扫一遍。这主要是为了做三件事一是标记题目类型和分值。选择题和填空题往往分值小但数量多简答题和编程题分值大但耗时大。二是在脑子里面过一道“哪些题是我一眼就会的哪些题需要多花时间”。先把会做的做掉把能拿的分拿到手这是在线笔试最重要的原则。三是看有没有“陷阱题”。什么叫陷阱题比如题面给了很长的背景故事但实际上就是问一个简单的排序稳定性这时候千万不要被冗长的题干吓住。京东的笔试题目量不算小按我的经验整体时间分配大概是选择题每题不超过1分钟计算类填空题每题3-5分钟简答题每题10分钟编程题每道至少预留20分钟。如果选择题卡住超过2分钟立刻标记一个“待定”然后跳过最后再用剩余时间回来解决。4.2 手写代码的细节决定笔试能否全过编程题是算法笔试的大头也是最容易丢细节分的地方。很多人在本地IDE里写得顺畅一到在线笔试就疯狂报错原因不外乎这几点第一没有考虑输入输出格式。在线笔试经常要求处理多行输入有的输入以逗号分隔有的以空格分隔有的行数不确定。如果main函数里读数据的方式写错整个逻辑再对也白搭。我的习惯是花半分钟把输入样例在草稿纸上模拟一遍再开始写代码框架而不是直接上来就写核心逻辑。第二边界条件不处理。数组长度为0、链表只有一个节点、目标值等于中间值、递归深度过深导致栈溢出等这些边界条件一定要在脑子里过一遍最好写出明确的if分支。第三循环里的指针/索引越界。这个错误特别隐蔽写完代码后一定要用一个小测试用例手动走一遍循环确认每个索引的最大值不超过数组长度减一。还有一点要特别注意不要在编程题中使用复杂的高级技巧来炫技。如果你的代码思路简单但正确哪怕复杂度不是最优也能拿到基础分数。尤其是暴力解法很多时候在数据量小的情况下直接能AC比你在考场上临时想一个复杂的优化算法然后写错要好得多。当然如果明确提示数据规模很大那就必须用效率更高的算法否则部分用例会超时。4.3 简答题的答题技巧按“公式解释例子”三部曲作答京东笔试题中的简答题不是单纯考你默写概念而是更看重你的逻辑表达。比如问“解释KMP的next数组”如果你只把next数组的定义写上去可能只能拿一半分。更好的答法分三步第一步写出next数组的精确定义包括下标含义、取值含义。第二步解释next数组计算的递推逻辑分情况说明当P[i] P[j]时next[i1] j1当不等时j next[j]循环回退。第三步用一个具体例子比如abacaba展示next数组是怎么一步步算出来的并注明用这种递推方式使复杂度达到O(m)。这样回答既覆盖了知识点又展示了推导能力分数自然高。我还见过一个答得不错的同学在解释粒子群算法时他从“鸟群觅食”引入然后给出速度更新公式、位置更新公式再专门解释了参数w/c1/c2的直觉含义最后说了一句“由于随机性的存在粒子群不一定能找到全局最优但通常能在较短时间得到不错的近似解”。考官一看就知道他是真的懂而不是背概念。所以简答题的核心是“用具体式子支撑你的文字”最好能写公式就写公式。4.4 复习路径怎么高效刷算法笔试真题如果你还有1-3个月准备秋招我强烈建议不要漫无目的地刷“题库”。针对京东这种级别的公司建议按下面的节奏来前期基础期花两周把所有基础数据结构过一遍数组、链表、栈、队列、树、图、堆、哈希表。每个数据结构自己实现一遍至少要实现遍历、插入、删除这些基本操作。同时把字符串匹配KMP、排序快排/归并/堆排、二分查找、并查集、拓扑排序、最短路径这些“经典算法模板”写熟练。中间穿插做经典剑指offer题和LeetCode前200题。中期专题期针对机器学习面试中常考的基础算法做专项准备梯度下降手算、反向传播手算、卷积尺寸计算、K-Means迭代过程模拟、朴素贝叶斯概率计算、SVM间隔推导可选、决策树分裂计算、以及粒子群/模拟退火的原理和公式。准备一个笔记本把每个算法的“一句话概念核心公式优缺点典型应用”记下来考前翻这个本子效率最高。后期冲刺期找3-5套历年大厂真题做模拟考试严格按照考试时间。做完后不要只对答案一定要把每道错题都按“正确思路”重新推一遍并总结错误类型“概念不清楚”、“计算粗心”、“代码没跑通”分别记录。我当年专门建了一个错题本最后效果非常好。错题本里还要记录时间分配失误比如哪道题花了太多时间导致后面来不及。5. 常见问题与排查技巧实录帮你少踩80%的坑从我自己和身边同学的实战反馈来看算法笔试中有些坑是重复出现的。以下挑了几个典型问题用“现象-原因-解决”的方式整理成速查表这也算是我这几年做算法题的经验沉淀。5.1 手算next数组总是差一位怎么排查现象KMP的next数组手算结果和标准答案总差一位。原因绝大多数情况是next[i]的定义或者下标起点不一致。有的教材定义“next[j]表示当模式串第j个字符匹配失败后从模式串下标为next[j]的字符开始继续比较”这时next[0]通常是-1next[1] 0。而有些题目定义“next[i]为前i个字符最长相同前后缀长度”下标从0开始next[1]0next[2]1。如果不仔细读题极易偏移一位。解决方式考场上先圈出题目中的定义如果是计算题直接按定义来如果是代码填空题看它给出的初始next[0]是-1还是0再决定后续递推。平时复习时把两种定义各手推一遍abacaba这样不管考哪种定义都能快速适应。我再强调一下唯一保险的办法拿到题目先写一个小的测试字符串比如abab用定义手推一遍验证自己的理解和题目给的一致后再正式计算。5.2 动态规划代码在笔试里总爆栈怎么办现象递归版动态规划在测试用例较大时栈溢出或者运行超时。原因递归深度太大每层递归消耗系统栈空间数据量大时自然会溢出。另外某些递归写法中每个状态的计算没有做“记忆化”导致重复计算复杂度爆炸。解决方式第一优先写成迭代版自底向上。如果空间不够可以用滚动数组压缩维度。第二如果必须用递归别忘了添加lru_cachePython或使用vectorvector memo手动记忆化。第三笔试前要练习几道“递归转迭代”的题例如斐波那契、爬楼梯、0-1背包确保能快速切换写法。5.3 代码本地跑能过粘贴到在线编辑器就编译错误现象本地IDE一切正常复制到牛客/赛码等平台后编译报错或者运行时异常。原因常见原因包括main函数返回类型写错有的平台要求int有的要求void但一般int更稳妥没有引入必要的头文件使用了本地编译器特有扩展或者读取输入时用了不支持的函数。还有一种特别坑的情况是代码里混入了不可见字符如中文标点、全角括号——从网页复制代码时很容易发生。解决方式无论多着急提交前都手动检查头文件、括号是否为半角、main函数签名。另外建议使用Python写在线笔试的同学不要用sys.setrecursionlimit做过大的递归限制有的平台并不支持还是优先用迭代思路。最后一个小经验在线笔试平台也有自己的“本地调试”功能有条件的话写完代码后先在平台的示例输入上跑一遍确认输出完全一致再提交。5.4 遇到没见过的算法题现场怎么“蒙”思路现象题目背景很陌生或者看起来像是某个冷门算法完全没思路。原因其实就是遇到新题慌了。实际上很多所谓的冷门算法题都是经典模型的变种。解决方式我总结了一个“四步蒙题法”。第一步看数据范围如果n很小比如n≤20可以先考虑暴力枚举或状态压缩如果n在10^5级别多半是排序、二分、贪心、动态规划如果n在10^5~10^6而且要求O(nlogn)优先考虑树状数组、线段树、堆等。第二步把问题抽象成已知模型它是不是一个“最大值最小”问题那就大概率是二分答案是不是“区间内统计某种特征”可能是前缀和或滑动窗口是不是“两个集合匹配”可能是二分图匹配。第三步写一个最简单的暴力解再想能不能优化。第四步如果暴力解也不行想想题目的限制条件有没有可以利用的性质比如数据单调性、无环性、单调栈等。说实话京东级别的笔试更侧重基础应用很少会出现真正偏门的算法所以把经典模型吃透大部分题都能解。6. 一份可复现的算法笔试冲刺计划以30天为例很多同学问我距离笔试还有一个多月现在还来得及吗我的回答是来得及但必须有节奏。下面这份计划是我当年亲身实践过的之后也推荐给学弟学妹反馈都不错。当然你可以根据自己的基础调整但我建议整体节奏不要乱。6.1 第1-10天基础算法模板速过这个阶段的重点是“会写、写对、写快”。每人每天至少手写代码5道题题目类别可以按这样分配第1-2天把数组、链表、栈、队列的基础题练熟第3-4天练排序和二分查找尤其是快排、归并排序的代码要能默写第5-6天练树和图的遍历DFS/BFS要烂熟于心第7-8天练贪心和动态规划至少能做经典背包、最长公共子序列、最长递增子序列第9-10天练字符串和数学题重点是KMP、快速幂、大数运算。每道题写完不要急着看题解先自己构造几个测试用例看能不能通过。如果错先自己想错在哪实在想不出再看。这个“先想”的过程比单纯刷题重要得多。我见过不少同学刷了很多题但进步有限就是因为一直处于“看题-看答案-抄一遍”的循环里大脑没有主动思考。6.2 第11-20天机器学习与深度学习基础夺分不要以为笔试里机器学习的题不写代码就不重要。事实上京东这类公司的算法工程师笔试中选择题和填空里机器学习占的分值甚至能接近编程题。这个阶段复习重点放在手算推导上。每天选一个模型做“手算题”比如今天手算线性回归的梯度下降一步明天手算K-Means的一次迭代后天手算朴素贝叶斯后验概率。深度学习方面每天手推一个反向传播例子并练习计算卷积核输出尺寸。同时把机器学习经典模型思维导图整理出来每个模型要求自己用三句话讲清楚“解决了什么问题、核心假设是什么、如何训练参数”。可能有些同学觉得“三句话”太简单但实际上如果你能用三句话给一个完全不懂的人讲明白你就真的懂了。6.3 第21-27天整套真题模拟与错题复盘这个阶段找一个安静的时间模拟真实考试环境。每天上午一套往年真题如果找不到京东的原题用其他大厂的也可以只要难度接近下午花时间复盘。复盘不是对答案而是把每道题对应的知识点重新产出一份笔记。比如你今天做错了一道“粒子群算法”的选择题就把粒子群的公式、迭代流程、优缺点整理成半页纸。晚上再把当天所有错题知识点再过一遍。错题本建议电子化方便后期检索。我当时就在Notion里建了一个表字段包括题目来源、知识点、错误类型概念/计算/代码、错因描述、正确思路。这样到考前最后一天直接翻这个表效率极高。6.4 第28-30天查漏补缺与状态调整最后三天不要刷新题了重点看之前整理的笔记和错题本。把那些“一看就会一写就错”的算法模板再手写一遍KMP、归并排序、快速幂、二叉树非递归遍历、Dijkstra、Kahn拓扑排序。同时把机器学习常考公式再过一遍信息增益、基尼指数、SVM间隔、LSTM门控、梯度下降更新式、粒子群更新式。考前保证充足睡眠尤其不要熬夜刷题。我的个人感受是算法笔试非常吃状态一旦脑子发懵连简单的快排边界都会写错。提前一天把身份证、电脑、充电器、网络环境准备好在线笔试的话还要提前测试摄像机位是否正常。7. 我的用券“心法”与考试时间管理最后再分享几个笔试现场特别实用的时间管理技巧。第一个技巧是“5分钟热身法”。开考前5分钟先在草稿纸上默写一遍常用的算法模板和公式——比如快排分区函数、KMP的next循环、快速幂代码、卷积尺寸公式、信息增益公式。这像运动员比赛前要热身一样让你脑子迅速进入状态。我每次笔试都这么做效果很明显。第二个技巧是“两轮答题法”。第一轮只做确定性极高且耗时短的题把能拿的分全部拿到手。第二轮再花时间做计算量大的题和编程题。这样即使某一道计算题花掉了时间也不至于出现“全卷大空白”的惨状。第三个技巧是“相信第一直觉”。选择题中如果你对某个选项很有把握不要随便改。考场上第一直觉往往是建立在平时积累上的快速模式匹配除非你发现明显的计算错误否则不要因为“怕错”就反复改答案。我亲身经历过改错比不改错的机会大得多。第四个技巧是“不会的题也要写步骤”。尤其是简答题只要写出相关公式、概念、甚至一个简单的例子都有可能得到部分分数。千万不要完全留白。比如问“模拟退火如何避免局部最优”哪怕你只写出“以一定概率接受较差解”这句话也能拿几分。在竞争激烈的算法岗招聘中一分之差可能就决定能否进入面试所以任何得分机会都要抓住。说到底京东2018秋招算法工程师笔试题本身并不是要难倒所有人它更是在用一种系统化的方式测试你是否具备算法工程师的底层素养。如果你能把上面这些知识点融会贯通再配合合理的复习计划绝对不只是应对京东其他大厂的技术笔试也能轻松上手。算法这条路没有捷径每一次推导、每一道代码、每一页错题笔记最终都会成为你拿到offer路上的垫脚石。
