京东算法工程师笔试真题复盘：从动态规划到机器学习考点全解析

2018年秋天，我在北京某高校的宣讲会上投了京东的算法工程师岗位，一周后收到了笔试通知。那时候算法岗的竞争已经非常激烈，京东这套题给我的整体印象是：基础扎实、覆盖面广、编程题不偏不怪但需要熟练度。

作为经历过那场笔试的人，我想把这份真题拆解复盘一遍。不是简单罗列题目，而是结合我当时的答题思路、考后查阅的资料、以及后来辅导学弟学妹时反复强调的考点，把每类题背后的考察逻辑讲清楚。无论你是准备互联网大厂算法岗，还是单纯想检验自己的算法功底，这篇文章都应该能给你一些实打实的参考。

1. 笔试全貌：题型分布与考察方向的底层逻辑

1.1 三个模块的构成

京东2018秋招算法工程师笔试总共120分钟，系统是牛客网，题目分三块：单选题、多选题、编程题。整体来看，单多选大概在30道左右，编程题两道。时间分配上，我身边不少人是栽在选择题耗时过多，导致编程题来不及调通。

选择题的知识面覆盖很典型，大概是这个分布：

• 数据结构与算法：栈、队列、树、图、排序、KMP、堆，大概占三分之一
• 机器学习基础：过拟合、正则化、LR、SVM、决策树、聚类
• 深度学习：反向传播、激活函数、CNN基础
• 概率统计与组合数学：条件概率、期望、随机抽样
• 少量操作系统和计算机网络：这个看年份和岗位，2018年还真出了两道

编程题考的核心，说白了一是动态规划，二是字符串处理。这两类题目在当年的笔试里出现频率极高，京东、腾讯、头条的算法岗笔试几乎都有。

1.2 算法工程师笔试与其他技术岗位的差异

很多同学会拿后端开发的笔试题来复习算法岗，这其实不太对。后端岗笔试更看重代码基本功、并发、网络协议这些，算法岗则更侧重数学基础和模型推导能力。

京东这套题里有一个很明显的特点：选择题中关于机器学习的内容不是简单的概念记忆，而是需要你真正算。比如给一个简单的数据分布，让你算信息增益；给一个线性可分的数据集，让你判断SVM的支持向量有几个。这种题目没有计算器，全靠手推，平时不动笔推导公式的同学当场就懵了。

所以复习算法岗笔试，跟复习开发岗完全是两条线。你需要把李航的《统计学习方法》里的公式亲自推一遍，而不是只看结论。

1.3 时间分配策略

我当时的策略是：选择题控制在50分钟以内，剩下的70分钟全给编程题。第一道编程题如果20分钟内没有清晰思路，先跳过做第二道，回头再补。

这里有个血泪教训：牛客网的在线IDE没有代码补全，平时用惯了IDE的人会非常难受。建议提前一两周就在牛客网或者LeetCode的在线编辑器里练习，提前适应裸写代码的感觉。否则真上了考场，光是想vector的头文件怎么写都要浪费一两分钟。

2. 编程题复盘：从读题到AC的完整思路

2.1 动规经典题目：股票买卖的最佳时机

京东2018年笔试编程题里有一道股票买卖类的问题，题目大概是给定一个数组表示每天的股价，只允许完成一笔交易（买入一次卖出一次），求最大利润。

这道题在LeetCode上对应的是121题，属于最经典的动态规划入门题。但笔试里的数据范围会稍微大一点，需要保证O(n)时间复杂度和O(1)空间复杂度。

我当时的解法是这样的：

#include <vector> #include <algorithm> int maxProfit(std::vector<int>& prices) { if (prices.empty()) return 0; int minPrice = prices[0]; int maxProfit = 0; for (int i = 1; i < prices.size(); ++i) { minPrice = std::min(minPrice, prices[i]); maxProfit = std::max(maxProfit, prices[i] - minPrice); } return maxProfit; }

核心思想很简单：遍历到第i天时，记录前i天的最低价格，用当天价格减去最低价格，就是“如果今天卖出能赚多少”，然后取历史最大值。

这道题别看简单，当年有不少人栽在一个细节上：股价一直在跌，最大利润应该是0，因为你至少可以不买不卖。很多人初始化maxProfit为负数，导致输出错误的结果。这就是边界条件没想清楚。

2.2 字符串处理：编辑距离问题的变形

第二道编程题是一道字符串编辑距离的变种。原题是LeetCode 72题，求把一个字符串变成另一个字符串的最少操作数，操作包括插入、删除、替换。

京东的题目我记得在一处做了变化：替换操作的代价和插入删除不同，替换的cost更高。这样就不能直接套标准的编辑距离模板，需要在状态转移时处理代价差异。

标准解法是二维动态规划：

#include <vector> #include <string> #include <algorithm> int minDistance(std::string word1, std::string word2, int insertCost, int deleteCost, int replaceCost) { int m = word1.size(), n = word2.size(); std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0)); for (int i = 0; i <= m; ++i) dp[i][0] = i * deleteCost; for (int j = 0; j <= n; ++j) dp[0][j] = j * insertCost; for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) { if (word1[i-1] == word2[j-1]) { dp[i][j] = dp[i-1][j-1]; } else { dp[i][j] = std::min({ dp[i-1][j] + deleteCost, // 删除 dp[i][j-1] + insertCost, // 插入 dp[i-1][j-1] + replaceCost // 替换 }); } } } return dp[m][n]; }

注意这里初始化dp[i][0]和dp[0][j]时，乘的是对应的删除代价和插入代价，而不是1。这是改动后的关键，很多人按照标准模板写初始化，结果把代价算错了。

2.3 刷题之外的配套复习清单

从这两道题往回看，2018年京东的编程题难度属于中等偏下，没有那种需要极强思维能力才能解出的压轴题。但这恰恰反映了一个规律：算法岗笔试的编程题，重点考察的是熟练度而不是天赋。

我当时刷题的覆盖面比较广，整理了一个跟京东出题风格比较匹配的清单，供大家参考：

• 线性表：数组、链表、栈、队列的基础操作，特别是用栈模拟队列或反之
• 字符串：KMP、回文串、编辑距离、最长公共子序列
• 树：前中后序遍历（尤其是非递归写法）、层次遍历、最近公共祖先
• 动态规划：股票系列、背包九讲、最长递增子序列、编辑距离
• 排序：手写快排、归并排序，理解各种排序的稳定性和复杂度
• 贪心：区间调度、跳跃游戏

如果时间有限，动态规划和字符串处理必须优先保证，这两个板块在各大厂的算法岗笔试里出现频率最高。

3. 选择题里的机器学习基础：为什么“会背概念”远远不够

3.1 数据分布与信息增益的计算

京东这套选择题里有一道让我印象深刻的题目：给一个二分类数据集，正负样本各占一半，某个特征把数据划分成两个子集，一个子集全是正样本，另一个子集正负各半，要求计算这个特征的信息增益。

这类题考的是决策树的核心概念。公式很简单：

信息熵：H(D) = -∑ p_i * log2(p_i)

条件熵：H(D|A) = ∑ (|D_v| / |D|) * H(D_v)

信息增益：g(D, A) = H(D) - H(D|A)

代入题目数据：

• 原始熵：H(D) = -0.5 * log2(0.5) - 0.5 * log2(0.5) = 1
• 第一个子集，全是正样本：H(D1) = 0
• 第二个子集，正负各半：H(D2) = 1
• 条件熵：H(D|A) = 0.5 * 0 + 0.5 * 1 = 0.5
• 信息增益：1 - 0.5 = 0.5

考察的重点不是公式本身，而是你能不能在没有计算器的情况下，把log2的值快速估算出来。平时背过常见对数值的话，这道题大约30秒就能解完。

3.2 过拟合现象与正则化手段

多选题里有一道是问哪些手段可以缓解过拟合。选项大概包括L1正则化、L2正则化、Dropout、增加训练数据、增加模型复杂度、早停法。

正确答案是除了“增加模型复杂度”以外的那几项。这道题本身不难，但属于典型的“知道就是送分，不知道就全错”的题目。

这里有一个我后来在面试中反复被问到、笔试也常考的细节：L1正则化和L2正则化的区别。L1会倾向于产生稀疏的权重，把不重要的特征权重压到0，可以起到特征选择的作用；L2只是把权重整体缩小，不会让权重变成0。

从优化角度看，L1在0点处不可导，所以通常用近端梯度法或者坐标下降法求解；L2可导，可以直接用梯度下降。这个区别在2018年的技术讨论中还没有现在这么普及，但放到今天的笔试里已经是高频考点了。

3.3 LR与SVM的比较：一个高频出题点

单选里有一道题：关于逻辑回归和支持向量机的说法，哪个是正确的？选项里有几个容易混淆的点，比如：

• LR是生成模型，SVM是判别模型（错，两者都是判别模型）
• LR对异常值敏感，SVM对异常值不敏感（对，SVM只关注支持向量）
• LR的损失函数是hinge loss（错，LR是对数损失）
• SVM不需要做特征缩放（错，SVM对特征缩放敏感）

这一类对比题在各大厂的笔试里几乎每年都会出现。核心要理解的是，LR建模的是条件概率P(Y|X)，它利用所有样本进行训练，决策边界由所有样本共同影响；SVM则是找一个最大间隔的超平面，决策边界只由少数支持向量决定，所以对异常值相对鲁棒。

同时，SVM的损失函数是hinge loss，即max(0, 1 - yi * (w·xi + b))，LR用的是交叉熵损失。如果把这两者的损失函数搞混了，那基本上所有跟分类器相关的题都容易出错。

4. 深度学习考点：从反向传播到网络结构细节

4.1 手推一个简单的反向传播

2018年的笔试里深度学习还主要停留在基础层面，不像现在这样会考Transformer、注意力机制等。当年京东的题目里有一道需要手推反向传播的计算题。

题目大致是：一个两层的全连接网络，输入是x，中间隐藏层用sigmoid激活，输出层不加激活（或者用softmax），损失函数是均方误差，给定一组具体数值，求参数更新后的值。

这类题核心是链式法则。我建议大家在复习时养成一个习惯：不要只看反向传播公式，而是自己拿一张纸，画一个只有两三个节点的简单网络，手动计算一遍梯度。这个过程虽然慢，但能帮你真正理解梯度是如何逐层传回去的。

常见的误区是，很多同学把sigmoid的梯度只记成σ'(z) = σ(z)(1-σ(z))，但不知道这个梯度是怎么来的。从定义推导一遍就会发现，这是sigmoid函数求导后可以化简的结论。类似的，softmax的求导要分i等于j和i不等于j两种情况，很多笔试题目就是在这个地方设坑。

4.2 激活函数的对比与应用场景

选择题里还考了激活函数。选项里有sigmoid、tanh、ReLU、Leaky ReLU，问的是哪些说法正确。

比较典型的正确说法是：

• ReLU可以缓解梯度消失问题，但可能出现神经元死亡
• Leaky ReLU给负半轴一个很小的斜率，缓解神经元死亡
• sigmoid输出范围在(0,1)，适合二分类的输出层
• tanh输出范围在(-1,1)，均值接近0，比sigmoid收敛更快

当年这道题还有一个选项是“ReLU的输出期望不为0，会导致后层的输入发生偏移”，这个说法也是对的。所以多选题想拿满分，不能只记住激活函数的优点，也要知道它们的缺点和适用边界。

4.3 过拟合在深度学习中的体现与应对

深度学习的多选题里有一道关于Dropout的正确理解。当时我对Dropout的理解还停留在“随机丢弃一部分神经元”这个层面，但后来复习时看了原始论文，才发现有几个关键点值得注意：

• Dropout只在训练时启用，测试时要关闭
• 训练时神经元的输出要除以keep_prob（或者用inverted dropout）
• 本质上是一种模型集成的手段，训练了多个共享参数的子网络

如果笔试中考到Dropout的Rescale问题，必须选上“训练时需要缩放”。当时很多同学把dropout理解成简单的“置零”，忽略了缩放这一步，导致在推断和训练时输出分布不一致。

5. 概率统计与组合数学：不能正面硬算的题目

5.1 条件概率与贝叶斯公式

京东这套题里有一道贝叶斯公式的应用题，背景设定是一种疾病的检测，患病率是0.1%，检测准确率是99%，问如果一个人检测结果为阳性，他真正患病的概率是多少。

这道题考的是经典的贝叶斯公式：

P(患病|阳性) = P(阳性|患病) * P(患病) / P(阳性)

P(阳性) = P(阳性|患病) * P(患病) + P(阳性|未患病) * P(未患病)

代入数据：

P(阳性) = 0.99 * 0.001 + 0.01 * 0.999 ≈ 0.00099 + 0.00999 ≈ 0.01098

P(患病|阳性) ≈ 0.00099 / 0.01098 ≈ 9%

这就是典型的基础比率谬误：即使检测准确率高达99%，因为患病率本身极低，检测阳性后的患病概率也只有9%左右。

这类题目在算法岗笔试里几乎必考，因为机器学习分类问题里经常涉及精确率、召回率和类别不平衡。贝叶斯公式是理解这些概念的基础，建议深刻理解而不是死记。

5.2 期望计算中的线性技巧

有一道组合数学题问的是：从1到100中随机取一个数，取到的数的平方的期望是多少。

很多人的第一反应是用平方的公式硬算，但在考场那种环境下很容易出错。实际上有个更巧妙的解法：随机取一个数X，E[X²] = (1² + 2² + ... + 100²) / 100，用平方和公式：

n(n+1)(2n+1) / 6 = 100 * 101 * 201 / 6 = 338350

然后除以100，得到3383.5。这样算，又快又准确。

还有一个常见的考点是几何分布的期望。比如投硬币直到出现正面，投掷次数的期望是2。推导方式是E = p * 1 + (1-p) * (1 + E)，解得E = 1/p。这个推导过程如果理解了，比死记结论更可靠，万一题目改成“直到连续出现两次正面才停止”，你也能用类似方法算。

5.3 蓄水池抽样：算法题里的概率思想

选择题里有一道关于蓄水池抽样的描述题。这个算法在2018年还只在面试中偶尔出现，但现在已经成了算法岗笔试和面试的高频考点。

蓄水池抽样解决的核心问题是：一个数据流长度未知，如何保证在遍历一遍后，每个元素被选中的概率相等？

做法是：维护一个大小为1的“蓄水池”，遍历第i个元素时，以1/i的概率替换掉之前选中的元素。最终每个元素被留在蓄水池中的概率是1/n。

这个结论看起来反直觉，但用条件概率可以证明。类似的还有洗牌算法，即Fisher-Yates洗牌，保证每种排列出现的概率是1/n!。这类题目的特点是代码量小、思维量大，很适合笔试考选择题时考察概率直觉。

6. 数据结构算法选择题：不刷题真的会吃亏

6.1 KMP算法与next数组

热门搜索词里有一条是“在kmp算法中，对于模式串p='abacaba'，其next数组”，这跟当年笔试的考法高度一致。

KMP算法中next数组的定义因教材而异。按王道数据结构（408统考）的定义，next[j]表示在模式串失配时，下一次匹配应该跳转的位置，它等于模式串从开头到j-1位置的最长公共前后缀长度加1。

对模式串p = "abacaba"，逐个推导：

这个推导过程在考场上要能手算出来。不过不同教材对next数组的定义有差异，有的教材下标从0开始，有的从1开始。答题前先确认题目用的是哪种定义，否则很容易算出不同的结果。

6.2 排序算法的稳定性与复杂度

排序相关的选择题几乎年年都有。2018年京东考的是给一排排序算法，问哪些是不稳定的。正确答案是：快排、堆排、选择排序、希尔排序。稳定的是：冒泡排序、插入排序、归并排序、基数排序。

记忆口诀很多，我自己的办法是从原理去推：

• 冒泡排序只有相邻元素交换，所以稳定
• 插入排序是往已排序序列里插，元素相对顺序不会变，所以稳定
• 归并排序在合并时如果相等取左子序列的元素，也能保持稳定
• 选择排序因为要从后面选最小的元素跟当前位置交换，可能破坏相同元素的相对顺序
• 快排的partition过程是跳着交换的，不稳定
• 堆排序的调整过程中因为堆本身会让元素大幅移动，不稳定

如果把稳定性的底层原因想明白了，就算不背口诀，考试时也能推断出来。

另外，快排在平均情况下的时间复杂度是O(n log n)，最坏情况是O(n²)；堆排序的时间复杂度稳定在O(n log n)，但实际常数较大；归并排序需要O(n)的额外空间。这些细节同样是选择题的高频考点。

6.3 大根堆的插入与调整过程

有一道题给了一个初始数组，要求建大根堆后的结果，或者要求插入一个元素后堆的变化。这种题没有技巧，纯考察堆调整的熟练度。

建堆有自顶向下和自底向上两种方式。笔试中最常考的是自底向上调整，即从最后一个非叶子节点开始，依次下沉。插入操作则是把新元素放到末尾，然后自底向上调整。

我当时复习时把堆的插入、删除、建堆都手写了一遍：

#include <vector> void shiftDown(std::vector<int>& heap, int i, int size) { while (2 * i + 1 < size) { int left = 2 * i + 1; int right = 2 * i + 2; int largest = i; if (left < size && heap[left] > heap[largest]) largest = left; if (right < size && heap[right] > heap[largest]) largest = right; if (largest == i) break; std::swap(heap[i], heap[largest]); i = largest; } }

笔试选择题里画图推演能解决大部分堆问题，但如果运气不好遇到编程题直接考堆排序，会手写shiftDown和shiftUp就非常关键了。

7. 复盘总结与备战建议：从一场笔试反推整个复习策略

7.1 按考点优先级分配复习时间

回过头看京东2018年这套题，把时间维度拉长，题目风格其实代表了算法工程师笔试的一个普遍趋势：机器学习基础和经典数据结构占大头，深度学习考察点相对基础但逐年加重。我建议按下面的优先级来分配复习时间：

• 高优先级：动态规划、树与图、排序与堆、字符串匹配（KMP/编辑距离）、概率统计、线性回归/SVM/决策树的手动推导
• 中优先级：CNN/RNN的结构与计算、集成学习方法、特征工程基础
• 低优先级：冷门算法、过深的网络结构细节、偏工程的开发知识

高优先级部分如果能保证80%的正确率，笔试通过通常没有问题。

7.2 笔试中的几个实战技巧

第一，选择题遇到不会的，尽量用排除法。京东的多选题有一个规则：多选、少选、错选都不得分，所以拿不准的选项宁可不选。当然，前提是确认题目明确说明了“少选不得分”，如果说明“少选得部分分”，那就要权衡一下。

第二，编程题提交前一定要在脑子里走一遍边界情况。空数组、只有一个元素、数组里有重复值，这些情况在笔试里最容易翻车。我在考场上提交前习惯性地把边界情况带入代码里过一遍，这个习惯帮我避免了好几次因为空数组导致的报错。

第三，如果时间实在不够，优先提交暴力解法。很多编程题都按测试点给分，暴力解法虽然不能AC，但往往能拿到一部分分数。你要是为了追求最优解导致最后连暴力版本都没提交，那才是真的亏。

7.3 从笔试到面试的能力迁移

最后说点题外话。京东这套笔试虽然只是入场券，但准备过程中锻炼出的能力，在面试阶段会直接复用。

笔试试卷里的机器学习选择题，面试时很可能就变成“你讲讲L1和L2的区别”“为什么SVM对异常值不敏感”；编程题里的动态规划，在面试时会变成“你给我讲讲你做过的项目里，哪些地方用了DP的思想”。

诚心建议所有准备算法岗笔试的人，不要只满足于“会做题”，还要明白题目背后的原理。一道KMP的next数组题，背后是字符串匹配的思想；一道贝叶斯公式题，背后是分类问题里不确定性建模的思维方式。这些原理层面的东西，才是算法工程师这个岗位真正的核心竞争力。

我后来帮人改简历、模拟面试时经常说一句话：笔试考的是你过去几个月刷题的结果，而把一道题背后的原理想透，影响的是你未来几年解决问题的方式。这句话送给大家，也算是我从京东那场笔试里得到的最大收获。