京东算法岗笔试真题解析：从KMP到PID，基础扎实才是王道

1. 京东2019春招算法类试卷到底在筛选什么样的人每年春招的算法类试卷一出来总能引起一波讨论。2019年京东这场春招算法岗笔试我印象比较深——它不是单纯堆难题而是把计算机基础、机器学习理论和业务直觉揉在一张卷子里。很多同学刷了一堆LeetCode去考试结果挂在了一些看起来基本功的题上挺可惜的。先说说京东算法岗的JD。我当时帮团队筛过简历也参与过笔试出题方向的讨论。京东的算法岗位大致分两类一类偏推荐搜索、供应链优化、风控建模这类业务算法另一类偏机器学习平台、基础算法研究。虽然方向不同但笔试考的东西高度重叠——数据结构与算法、机器学习基础、概率统计、编程能力。试卷的目的不是选出刷题最多的人而是筛出基础扎实、能写代码、懂模型原理、有业务sense的候选人。我当时拿到这套2019春招题的时候第一反应是题目整体难度中等偏上但没有特别偏难怪的题。它的核心逻辑是——你不需要会所有冷门算法但常见的数据结构、排序、字符串匹配、动态规划得能写对机器学习部分逻辑回归、决策树、SVM这些经典模型的基本原理必须讲清楚再留一两道开放题看看你拿到一个真实业务问题时的思考路径。整套卷子大概分三块选择题覆盖数据结构、操作系统、网络、概率统计、手写代码题重点考察KMP、排序、二分、DP这类高频考点、算法策略题涉及PID、卡尔曼滤波、积分类算法的应用场景理解。接下来我把每部分拆开讲结合具体的考点和解题思路帮大家还原一下这张卷子的考察逻辑。2. 数据结构与基础算法高频考点逐题拆解2.1 KMP算法与next数组——字符串匹配的经典陷阱热搜词里挂着在kmp算法中对于模式串pabacaba其next数组next[i]定义为...这道题几乎可以确定是京东笔试的原题或者至少是同源变体。字符串匹配是算法岗笔试的常客而KMP算法又是字符串匹配里考得最频繁的一个。先说下KMP到底解决什么问题。普通暴力匹配两个指针分别在文本串和模式串上走失配的时候文本串指针回退到下一个位置模式串指针回退到开头时间复杂度O(n*m)。KMP的核心思想是失配的时候模式串指针不要回退到开头而是回退到一个已经匹配过的前缀的位置文本串指针不回退。这个回退到哪的信息就存在next数组里。next数组的定义在这道题里写得很清楚next[i]表示模式串前i个字符组成的子串中最长相同前后缀的长度。注意这里有一个常见的坑——不同教材对next数组的下标定义不太一样。有的版本next[0]-1有的版本next[0]0。京东这道题明确说了next[i]定义为说明它采用的是某种固定定义做题前一定要先搞清楚下标从几开始。拿abacaba这个模式串来算一遍。先写出它的前缀子串前1个字符a没有真前缀和真后缀最长相同前后缀长度为0前2个字符ab前缀a、后缀b不相等长度为0前3个字符aba前缀a、ab后缀a、ba最长相同前后缀是a长度为1前4个字符abac前缀a、ab、aba后缀c、ac、bac没有相等长度为0前5个字符abaca最长相同前后缀是a长度为1前6个字符abacab最长相同前后缀是ab长度为2前7个字符abacaba最长相同前后缀是aba长度为3所以next数组从1开始计数就是[0, 0, 1, 0, 1, 2, 3]。如果next[0]定义成-1那整体往后平移加调整结果会呈现另一种形态。考场上最稳妥的做法是先用题目给出的定义把next数组的语义理清楚再在草稿纸上把每个位置的值写出来。我见过太多人背了模板碰到next[i]定义为这种字眼直接默认成自己熟悉的那套结果一开始就算错。KMP的失配跳转是当模式串第j位失配时j回退到next[j]按某种定义可能是next[j-1]继续比较。整个算法的时间复杂度是O(nm)因为文本串指针最多移动n次模式串指针虽然有回退但回退的总次数不会超过前进的总次数。这个复杂度证明在面试里偶尔会被追问建议自己推一遍。2.2 排序算法全家桶不只会写快排还得知道什么时候用堆排序热搜词里数据结构排序算法、冒泡排序算法c、堆排序算法扎堆出现说明排序这块确实是笔试选择题和编程题的重灾区。京东的卷子里排序题一般不会让你手写一个完整的排序而是考你在不同场景下选哪种排序和某种排序的复杂度推导。先给一个我自己整理的排序算法对比表笔试前建议背熟排序算法平均时间复杂度最坏时间复杂度空间复杂度稳定性冒泡排序O(n²)O(n²)O(1)稳定选择排序O(n²)O(n²)O(1)不稳定插入排序O(n²)O(n²)O(1)稳定希尔排序O(n^1.3左右)O(n²)O(1)不稳定归并排序O(nlogn)O(nlogn)O(n)稳定快速排序O(nlogn)O(n²)O(logn)不稳定堆排序O(nlogn)O(nlogn)O(1)不稳定京东这种大厂笔试特别喜欢考堆排序。原因是堆排序在很多工程场景里是优先队列的底层实现比如TopK问题、任务调度、定时器。我记得有一道选择题大概是从一个无序数组中找出最大的K个数最优解法的时间复杂度是什么。如果你只会排序后取前K个那是O(nlogn)用堆来做维护一个大小为K的最小堆遍历一遍数组每次和堆顶比较时间复杂度是O(nlogK)。K远小于n的时候这个差距非常明显。再比如冒泡排序c这个热搜词说明还是有不少人把最基本的冒泡当作复习起点。冒泡排序的优化点在于如果某一趟没有发生任何交换说明序列已经有序可以提前终止。这个优化在笔试里经常被拿出来当作选择题问你最好的情况下冒泡排序的时间复杂度答案是O(n)而不是O(n²)。考场上我还遇到过一个排序的衍生题链表排序。数组的快排可以直接通过下标访问元素但链表不行。链表排序一般用归并排序因为归并排序只需要顺序访问不需要随机访问。LeetCode 148就是原题。链表归并排序的代码量不算大但边界条件容易写错建议考前亲手写两遍。2.3 二分、贪心、动态规划笔试编程题的三大主力编程题部分京东倾向于考三类二分查找及其变体、贪心策略题、经典动态规划。这三个方向在热搜词里都有对应比如dijkstra算法、快速幂算法c、剪枝算法、贪心算法。先说二分。二分查找本身很简单但笔试爱考的是变体查找第一个等于目标值的位置、最后一个等于目标值的位置、插入位置。这些变体本质上都是二分边界问题。我推荐一个万能的写法定义区间[l, r]为左闭右闭循环条件为l r更新时l mid 1或r mid - 1。这样写可以避免死循环而且能方便地处理边界情况。京东笔试里有一道经典题旋转数组中的最小数字就是二分的变体——数组是由一个有序数组旋转得到的你需要在O(logn)时间内找到最小值。核心思路是比较mid和r的值如果nums[mid] nums[r]说明最小值在右半部分否则在左半部分。贪心算法一般是给一个场景题比如活动安排问题、跳跃游戏。做贪心题最关键的是证明贪心策略的正确性。笔试不需要你写严格的数学证明但你要能说服自己。以跳跃游戏为例维护一个当前能到达的最远位置遍历数组不断更新这个最远位置如果某个位置i大于当前能到达的最远位置说明无法到达返回false。这个贪心的正确性在于每一步都扩展当前最远可达范围任何其他策略都不会比这个更优。动态规划是重头戏。京东2019年春招我记得有一道最大连续子数组和的变体。经典解法是Kadane算法用dp[i]表示以第i个元素结尾的最大子数组和转移方程是dp[i] max(nums[i], dp[i-1] nums[i])最终答案是所有dp[i]中的最大值。空间上可以优化成只用一个变量。这个题太经典了以至于出现在笔试里反而让人容易大意——有些人直接背了模板结果题目改成环形数组或者允许删除一个元素就懵了。我的建议是DP题一定要先明确状态定义再写转移方程最后再看边界条件。状态定义对了代码就是照着翻译。3. 机器学习与深度学习算法工程师的核心战场3.1 从特征工程到模型评估逻辑回归为什么是必考题京东算法岗笔试的选择题里机器学习的比例很高。逻辑回归是出现频率最高的一个因为它是理解分类模型的基础也是推荐系统、风控模型的常见起点。考法一般有三种推导损失函数、解释正则化的作用、问它和线性回归的区别。逻辑回归的损失函数是交叉熵损失这点大多数人能答上来但为什么不用均方误差MSE这个问题能难住不少人。原因是逻辑回归的预测值是经过sigmoid变换的输出在(0,1)区间。如果用MSE损失函数关于参数不是凸函数梯度下降容易陷入局部最优而交叉熵损失关于参数是凸函数能保证收敛到全局最优。此外sigmoid函数在两端梯度饱和如果用MSE梯度会非常小收敛极慢交叉熵损失在预测值和真实值差异大时梯度也大学习效率更高。正则化也是高频考点。L1正则化会把参数压缩到0产生稀疏解适合做特征选择L2正则化只会让参数趋近于0但不会等于0能防止过拟合但不会产生稀疏性。为什么L1有稀疏性因为L1的梯度是常数在参数接近0的时候优化过程很容易把参数直接推过0而L2的梯度大小和参数本身成正比参数越小梯度越小最后只会无限接近0。关于模型评估京东考过AUC和ROC。AUC的含义要能说清楚随机抽取一个正样本和一个负样本分类器对正样本的打分高于负样本的概率。所以AUC对样本类别不平衡不敏感适合正负样本比例悬殊的场景。相比之下准确率Accuracy在正样本占99%的数据集上没有任何意义——全都预测为正样本准确率也有99%。这种基础概念在笔试里就是送分题但如果你只背了AUC越大越好而不知道它到底在衡量什么稍微换个问法就露馅了。3.2 反向传播与激活函数深度学习笔试的高频送分题深度学习部分京东2019的卷子主要考了反向传播的推导和激活函数的比较。这两块是所有深度学习岗的必考题也是区分调包侠和真正懂原理的人的分水岭。反向传播的推导核心是链式法则。给定一个简单的网络输入x隐藏层h W1x b1经过激活函数a sigmoid(h)输出y W2a b2损失函数L (y_target - y)²。反向传播就是从损失函数出发先算dL/dy然后算dL/dW2和dL/db2再算dL/da接着通过激活函数的导数dL/dh最后算dL/dW1和dL/db1。笔试里一般不会让你算特别深的网络但至少两层全连接网络的推导必须能完整写出来。激活函数的比较也是一个经典考点。sigmoid的缺点输出不是零中心的会导致后一层神经元接收到的输入始终为正或始终为负使得梯度更新呈锯齿状而且两端饱和梯度消失严重。tanh的输出是零中心的但两端还是会饱和。ReLU解决了正区间的饱和问题计算也简单但有一个死神经元问题——如果某个神经元的输入始终为负它的梯度始终为0权重永远不会更新。Leaky ReLU、PReLU都是针对这个问题的改进。京东有一道选择题就问ReLU相比sigmoid的优势不包括以下哪项选项里有减轻梯度消失、计算简单、输出零中心、加速收敛。答案是输出零中心因为ReLU的输出都是非负的它并不具备零中心的性质。3.3 集成学习随机森林和GBDT的对比记忆集成学习在搜索和推荐场景用得非常多京东的算法岗笔试自然也会涉及。考得最多的是Bagging和Boosting的区别以及随机森林和GBDT的具体差异。我建议用一个表来对比记忆维度随机森林GBDT集成方式BaggingBoosting基学习器决策树通常CART决策树CART回归树样本采样有放回抽样Bootstrap每轮用全部样本但调整权重特征采样每次分裂随机选部分特征全部特征参与分裂树的关系并行独立训练串行每棵树拟合残差目标函数最小化每棵树的分类误差最小化整体损失函数抗过拟合较强较弱需要用shrinkage控制训练速度快可并行慢串行GBDT的核心是加法模型前向分步算法。每一步训练一棵新的决策树拟合的是损失函数对当前模型预测值的负梯度。对于平方损失负梯度就是残差对于其他损失函数负梯度是残差的近似。XGBoost在GBDT基础上做了二阶泰勒展开加入了正则项还支持列采样这些都是笔试进阶题会考的。京东2019的卷子里有一道题我印象很深随机森林中每棵树的训练数据是如何获取的选项里有独立同分布采样、有放回采样、无放回采样、全部数据。答案是有放回采样也就是Bootstrap。很多人选了独立同分布采样这不对——Bootstrap虽然是独立采样但样本不是同分布的因为每次采样后会把样本放回同一个样本可能被多次抽到。这个细节很基础但恰恰是区分真懂和背概念的点。4. 算法策略题与开放题把控制论知识拉出来遛遛4.1 PID算法与卡尔曼滤波为什么算法试卷会出现控制论内容热搜词里pid算法、pid算法在crps psu power的作用、卡尔曼滤波算法、增量式pid算法刷了一波存在感。很多人会觉得奇怪京东一个互联网公司考PID干嘛这里要理解京东的业务场景——京东有自营物流、仓储机器人、无人机配送还有大量的供应链预测和库存控制问题。PID算法虽然起源于自动控制但它的思想在库存控制、价格调整、流量分配这些场景里都有应用。试卷里PID的题一般不会让你做复杂的控制理论推导而是考你对比例、积分、微分三个词的理解。比例项P是对当前误差的反应误差越大调整力度越大。积分项I是对历史误差的累积作用是消除稳态误差——如果系统一直存在一个小的偏差比例项可能不够力积分项会不断累积把这个偏差拉回来。微分项D是对误差变化趋势的预测误差在快速增大时微分项会提前加大抑制力度减少超调。增量式PID和位置式PID的区别也是考点。位置式PID输出的是控制量的绝对值一旦计算错误影响很大增量式PID输出的是控制量的增量只和最近几次的误差有关计算量小而且不会累积误差。在嵌入式系统和机器人控制里增量式更常用因为它不需要对所有历史误差积分。卡尔曼滤波则出现在一道关于无人机定位数据融合的题里。卡尔曼滤波的核心思想是把传感器的测量值和系统模型的预测值融合起来根据两者各自的不确定性协方差加权得到最优估计。笔试里不需要你推导卡尔曼增益的公式但你要能说明白预测-更新两个步骤以及为什么它能融合多个噪声传感器。我当时复习的时候也觉得很意外后来想通了大厂算法岗考的从来不只是算法而是解决实际工程问题的能力。控制论算法出现互联网公司的笔试卷里反映的是业务趋势。备考时别只盯着机器学习花点时间了解PID、卡尔曼滤波这些经典算法的思想性价比很高。4.2 概率题和智力题考察的是数学建模能力算法岗笔试里概率题几乎是必考的。京东2019春招有一道题大概是一个盒子里有红球和白球若干每次随机取一个球记录颜色后放回问取到第一个红球时取球次数的期望。这是一个典型的几何分布问题单次取到红球的概率是p期望就是1/p。这类题的难点不是公式而是把实际场景转化为概率模型。我见过不少同学能把几何分布、二项分布的公式背得滚瓜烂熟但题目稍微换个包装就认不出来。比如在一条长度为L的线段上随机扔两个点求两点距离的期望——这其实是几何概率和顺序统计量的问题。再比如有N个房间每个房间有一个人M个人随机进入房间求空房间的期望数量——这考察的是指示变量和线性期望的性质。做概率题有一个经验法则如果题目问的是期望优先考虑用指示变量把期望拆成多个事件概率之和而不是直接算联合分布。以空房间问题为例令Xi表示第i个房间为空的事件E[Xi] P(第i个房间为空) ((N-1)/N)^M。根据期望的线性性质空房间数量的期望就是N * ((N-1)/N)^M。这个解法干净利落而且不需要考虑房间之间是否独立——期望的线性性对任意随机变量都成立哪怕它们不独立。智力题部分京东考过25匹马5个赛道最少比赛多少次找出最快的3匹马和100层楼扔鸡蛋这类经典题。25匹马问题答案是7次先分5组比5次每组第一名再比一次确定总冠军然后根据第6次的结果排除所有不可能进前三的马最后再比一次。扔鸡蛋问题的答案是14次最优解法是逆向思维第一次从14楼扔然后逐次减1。这些题本质上都是信息论和最坏情况最优的考察平时多刷刷牛客和LeetCode的智力题模块考试时遇到就能秒杀。5. 备考路线图三个月从刷题到笔试实战5.1 算法岗笔试的高频考点优先级排序结合京东2019春招的试卷和后续几年的大厂笔试题我整理了一个考点优先级列表备考时可以按这个顺序分配精力第一梯队必须熟练数组/链表、栈/队列、哈希表、二叉树遍历前中后序、层序、二分查找及变体、快速排序/归并排序/堆排序、动态规划背包、子序列、子数组、KMP/字符串匹配、贪心算法、DFS/BFS、最小生成树/最短路径Prim、Kruskal、Dijkstra。第二梯队应该掌握并查集、线段树/树状数组、Trie树、拓扑排序、LRU缓存、位运算技巧、滑动窗口、双指针、单调栈/单调队列、快速幂、回溯全排列/组合/子集、剪枝优化。第三梯队有精力再看后缀数组、DC3、网络流、Treap/Splay、蓄水池抽样、BM算法、AC自动机。京东2019的卷子主要落在第一梯队。KMP、排序、二分、DP、贪心这几块占了编程题的大头。第二梯队里并查集和滑动窗口在后续年份的笔试里出现频率变高了建议不要跳过。5.2 模拟笔试的三个关键习惯考前两周一定要进行模拟笔试。做题环境和平时刷LeetCode差别很大时间有限、不能暂停、不能看题解、每道题都要写出完整可运行的代码。我自己总结的三个关键习惯分享给大家第一先读题再写代码至少花5分钟理解题意。很多笔试挂掉不是因为不会做而是题目看了个大概就动手最后漏掉了边界条件。比如题目里说数组长度可能为0那你的代码开头就必须处理n0的情况。面试官看代码的时候首先是看边界处理其次才看算法复杂度。第二先写暴力解再优化。笔试不是面试不会有人因为你写出了暴力解而扣分——前提是你最终给出了优化解。如果你一开始就想写O(nlogn)的最优解又没想清楚很可能卡在中间写不下去。我通常的做法是先快速写一个暴力解保底再在此基础上优化。这样即使优化失败至少有一份能跑的代码。第三用草稿纸算例推演。笔试系统一般提供编译运行但不能实时调试。KMP的next数组、DP的转移方程这些在代码里出bug很难通过肉眼发现。我的习惯是写完代码后自己构造几个测试用例在草稿纸上手动跑一遍确认和代码的逻辑一致。特别是KMP这种有回退指针的算法手动推演一遍能发现大部分边界问题。5.3 资料推荐与刷题路径我当年备考用的资料可以给大家一套组合拳LeetCode按标签刷优先刷数组、链表、树、DP、字符串、二分查找这六个标签每题先自己想20分钟想不出来再看题解。重点不是过题量而是每道题都知道为什么这么做。剑指Offer这个经典到不用多介绍了。京东笔试的风格和剑指Offer的很多题目重合度很高特别是链表反转、二叉树重建、斐波那契数列这类基础题。牛客网真题有大厂历年笔试题库考前一定要刷几套京东的真题感受一下真实的题型分布和时间压力。《算法导论》不用全读看红黑树、动态规划、贪心、图算法这几个章节的经典证明即可。笔试虽然不考证明但理解了原理之后写代码的底气完全不一样。面经和博客知乎、CSDN上有很多京东算法岗的面经多看看别人回忆的真题查漏补缺。我当时还特意整理了一页纸速查表把KMP的next数组计算方法、Dijkstra的模板、DP的常见状态定义、排序算法的稳定性这些高频考点写在一页A4纸上考前10分钟快速过一遍。这个习惯帮我避开了很多低级错误。总结一下京东2019春招算法类试卷的风格是基础为主、应用为辅、业务渗透。你不需要掌握所有冷门算法但经典的数据结构、排序、字符串匹配、DP、机器学习基础必须滚瓜烂熟。备考时把精力放在高频考点上多模拟笔试环境练到手写代码不卡壳这张卷子没有想象中那么难。祝大家顺利上岸。