京东2016算法工程师笔试题这个题目直到现在提到它我还是有点后背发凉。倒不是题目本身难到做不出来而是那套题把“算法工程师”和“只会调包的程序员”区分得明明白白。我记得当年笔试完旁边好几个同学都在对一道KMP next数组的题有人直接懵了说“这不是考研408才考的东西吗”。事实上这恰恰是算法岗位笔试的常态——越是基础的数据结构和字符串匹配越能看出一个人的计算机功底是否扎实。今天我就借这个题目把当年那套笔试题中最核心的考点拆开揉碎讲一遍顺便聊聊算法工程师笔试到底在考什么以及怎么准备才不白费力气。先说清楚这篇文章不是给你背答案的而是帮你建立一套应对算法笔试题的思考框架。我会从考点分布讲起然后重点拆解一道流传很广的KMP next数组题再把排序、贪心、动态规划这些高频专题挨个过一遍最后分享一些当年踩过的坑和实战经验。无论你是准备校招、社招还是纯粹想提升算法内功这篇都值得你花十分钟看完。1. 京东2016算法工程师笔试题的考点分布与考察逻辑1.1 为什么算法工程师笔试离不开数据结构与算法很多人有误解觉得算法工程师日常就是写模型、调参数笔试也应该考机器学习深度学习。但实际上面向校招的算法工程师笔试数据结构与算法基本占了半壁江山。原因很简单笔试是海选题目需要机器自动判分而机器学习题目很难有唯一标准答案。相比之下手写一个快速排序、求一个next数组、设计一个状态转移方程答案明确对错分明作为初筛最公平。京东2016这套题就是典型。它不会让你推导复杂的损失函数反而把重心放在基础算法上。这说明一个问题在面试官眼里算法工程师首先是“工程师”得代码功底过硬然后才是“算法”。你连字符串匹配都写不利索谁敢让你去处理上亿级别的用户行为数据。从行业角度看电商行业的算法工程师面临着大量真实场景搜索排序、商品推荐、库存预测、风控反作弊。这些场景背后全是数据结构问题。比如搜索框里的前缀匹配可以用Trie树用户行为序列的相似度计算会用到动态规划实时调价系统里的优先级调度需要堆排序。笔试考KMP、考堆排序其实是在映射真实业务的技术需求。1.2 企业笔试常见题型与重难点总结根据我对近几年大厂算法笔试题的观察核心考点其实非常固定基本围绕以下几个方向展开字符串匹配类KMP、BM、Trie树。重点考察next数组的手算、匹配过程的模拟、边界条件的处理。排序与查找类快速排序、堆排序、归并排序、二分查找变形。重点考察时间复杂度、稳定性、原地排序、最坏情况。数据结构设计类LRU、最小栈、单调队列、并查集。重点考察你能否在限定复杂度内完成功能。动态规划类背包问题、最长公共子序列、最长递增子序列、股票买卖问题。重点考察状态定义和转移方程。贪心与图论类区间调度、最短路径、最小生成树。重点考察贪心策略的证明和堆优化。机器学习基础偶尔会出现但占比不高比如KNN、聚类、决策树的简单原理。京东这套题基本把上面这些点全覆盖了。我当时印象最深的是KMP那道题因为字符串匹配在业务代码里很少需要自己实现但笔试偏偏爱考。它考的不是你会不会用而是你有没有真正理解“前缀”和“后缀”这个概念能不能手动推演出next数组。这其实是在考察计算机科学最底层的抽象能力。2. KMP算法与next数组一道经典笔试题的完整拆解2.1 题目描述与next数组定义当年流传较广的一道题是这样的对于模式串 p abacaba其 next 数组next[i] 定义为前缀 p[0...i-1] 的最长相同前后缀长度是多少这不是让你写代码而是直接手算next数组。如果你对KMP的理解停留在“背代码”的层面这道题大概率会卡住。因为它考的不是代码而是你对“部分匹配表”背后逻辑的理解。先把next数组的定义说清楚。在KMP算法中当主串和模式串在某个位置失配时我们需要知道模式串应该向右滑动多少位。这个滑动量取决于当前失配位置之前的那段子串的“最长相等前后缀”长度。next[i]表示的是模式串前i个字符组成的子串中最长的相同前缀和后缀的长度。注意这里的前缀和后缀不能是子串本身长度要小于i。举个例子p abacaba我们要算next[0]到next[7]。next[0]通常约定为-1或者0不同教材定义略有差异。京东这道题里明确说了“next[i]定义为前缀 p[0...i-1] 的最长相同前后缀长度”那么next[0]就是空串通常设为-1或0这里按常见算法题习惯设为-1。不过有的解析里会改用PM表也就是从1开始计数所以看到不同答案先别慌先确认定义。2.2 手算next数组的完整过程我们把p abacaba逐个字符来算。先写个表i子串最长相等前后缀长度next[i]0-1或不参与1a02ab03aba14abac05abaca16abacab27abacaba3逐一解释i1子串a前缀和后缀都只能是空串长度为0所以next[1]0。i2子串ab前缀有a后缀有b不相等所以next[2]0。i3子串aba前缀有a,ab后缀有ba,a最长相等的是a长度1所以next[3]1。i4子串abac前缀a,ab,aba后缀bac,ac,c没有相等next[4]0。i5子串abaca前缀a,ab,aba,abac后缀baca,aca,ca,a最长相等a长度1所以next[5]1。i6子串abacab前缀a,ab,aba,abac,abaca后缀bacab,acab,cab,ab,b最长相等ab长度2所以next[6]2。i7子串abacaba前缀a,ab,aba,abac,abaca,abacab后缀bacaba,acaba,caba,aba,ba,a最长相等aba长度3所以next[7]3。所以最终next数组为[-1, 0, 0, 1, 0, 1, 2, 3]如果next[0]-1的话。有些资料里会把整个数组整体加1变成[0, 1, 1, 2, 1, 2, 3, 4]那是另一种变体本质上表达的是同一个匹配关系。做题时一定要看清题目给的next定义否则答案会对不上。这里有一个很容易错的地方在第7个字符时最长相等前后缀是aba而不是abaca或者更长的串。因为前缀必须从第一个字符开始后缀必须到最后一个字符结束二者不能重叠到覆盖整个子串。很多人算到abacab时看到ab就停了其实到abacaba时aba比ab更长需要继续检查。这个点不手动推一遍很容易漏。2.3 KMP匹配过程与复杂度分析光会算next还不够还得理解它怎么用。假设主串s ababacaba模式串p abacaba我们用KMP匹配。第1轮s[0..4] ababap[0..4] abaca在i5时失配s[5]‘c’或‘b’视具体字符串而定。此时已匹配部分的模式串前缀是abaca查next[5]1意味着该前缀的最长相等前后缀长度为1也就是a。于是模式串右移到下标1的位置继续与主串当前失配位置对齐比较。这样主串指针始终保持不回溯只移动模式串指针扫描一遍主串的时间复杂度是O(n)。模式串的每个字符顶多被比较一次、回溯一次整体是O(mn)。这是KMP最核心的优势匹配过程中主串不回头适合大数据量场景。对比暴力匹配最坏情况下每次失配都要从头开始复杂度能到O(n*m)。字符串越长差距越明显。比如在长度为1亿的文本里找一个1000位的模式串暴力法最坏情况要算1万亿次字符比较KMP只需要1亿1000次级别。这也解释了为什么KMP能在算法题里长盛不衰——它把“已经比较过并确认相同的信息”留存下来避免重复劳动这是典型的工程师思维。在京东这道题里如果你能手动推完next数组再顺手把匹配过程模拟一遍面试官对你的评价会明显高一档。因为很多求职者只会写代码模板一让解释原理就露馅。3. 笔试题高频算法专题排序、贪心与动态规划3.1 排序算法的选择与实现快排为什么这么难写对除了字符串排序是笔试里最“常青”的考点。京东这套题里就有一道让你手写快速排序并分析时间复杂度的题。它看着简单但能写得完全正确的人并不算多。快速排序的核心思想是分治选一个基准把小于基准的放左边大于基准的放右边然后递归处理左右两半。我这里给一个笔试中不容易出错的写法def quick_sort(arr, left, right): if left right: return pivot arr[left] i, j left, right while i j: while i j and arr[j] pivot: j - 1 if i j: arr[i] arr[j] i 1 while i j and arr[i] pivot: i 1 if i j: arr[j] arr[i] j - 1 arr[i] pivot quick_sort(arr, left, i - 1) quick_sort(arr, i 1, right)这个写法用挖坑法避免了很多初学者容易犯的交换越界问题。时间复杂度平均O(n log n)最坏O(n²)最坏情况发生在每次选到最大或最小元素作为基准时比如对已经有序的数组用固定基准。所以进阶一点的题目会让你分析为什么随机化基准能降低最坏概率。关于快排我当年笔试时吃过亏不记得处理等于基准的情况。如果数组里有大量重复元素上面的写法会把等于基准的元素归到某一侧造成递归深度过大。更好的做法是三分区小于、等于、大于或者直接用双指针把等于基准的元素夹在中间。笔试时如果遇到大量重复数据的用例这个优化很关键。除了快排堆排序也是高频考点。京东业务里有大量Top K问题比如“找出搜索词前100热词”堆排序的变种——小顶堆就能在O(n log k)内搞定。手写堆排要注意的是调整堆的函数要写对从最后一个非叶子节点开始下沉交换堆顶和堆尾后重新调整。3.2 贪心算法的典型应用与证明思路贪心算法在笔试中经常以“最少跳跃次数”“区间调度”这类形式出现。京东真题里有一道类似“活动安排”的题给定若干区间选择尽可能多的互不重叠区间。贪心策略是每次选结束时间最早的区间这个结论看着简单但题目会让你证明为什么贪心是最优解。证明思路常用“交换论证法”假设存在一个最优解如果它的第一个区间不是结束时间最早的区间我们可以把它替换成结束时间更早的区间这样剩余空间不会变差得到的还是最优解。不断替换下去就能说明贪心策略一定能得到最优解。这种证明能力是算法工程师区别于普通程序员的关键。笔试不一定要求你写完整证明但在面试中如果你能讲清楚会是很大的加分项。我建议准备算法题时不要只看“这题能过”要想想“为什么这个贪心策略是正确的”。哪怕只是用一个简单的反例说明“如果按开始时间贪心就不行”也比只会贴代码强得多。使用贪心算法时最怕的是遇到“看似贪心、实则需要动态规划”的题目比如“最小硬币个数”问题。如果硬币面额是1、5、11凑15元时贪心会选111111共5枚而最优解是555共3枚。这种题出现频率极高考察的就是你有没有识别出贪心失效场景的敏锐度。3.3 动态规划的状态设计技巧动态规划是算法工程师笔试的重头戏京东这套题里也有典型的背包或LCS变体。我见过很多人一看到DP就慌其实只要抓住两个核心状态定义和状态转移方程。以最长公共子序列LCS为例状态定义是dp[i][j]表示字符串A的前i个字符与字符串B的前j个字符的最长公共子序列长度。转移方程if a[i-1] b[j-1]: dp[i][j] dp[i-1][j-1] 1 else: dp[i][j] max(dp[i-1][j], dp[i][j-1])这个方程背后体现的是“决策”如果当前两个字符相等那它们一定可以接在之前的最优子序列后面如果不等那要么丢弃A的当前字符要么丢弃B的当前字符取两者较大值。DP的关键是要学会从暴力搜索递推到动态规划。先写一个递归版本看看有没有重复子问题有的话加个缓存就是记忆化搜索。如果发现状态只依赖前一行还可以压缩空间把二维数组变成一维。这个思维链路比背模板重要得多。我还想提醒一个细节状态定义千万不要过度设计。有时候两个维度就够你非要加第三个维度反而容易出错。比如股票买卖题很多版本只需要两维天数、手里是否持股。加太多状态会让代码可读性变差也不利于调试。4. 刷题与应试经验常见问题与避坑指南4.1 笔试中的边界条件与陷阱算法笔试最容易翻车的不是难题而是边界条件。我记得当年考快速排序时有一个同学传入了空数组结果递归没有终止条件直接栈溢出。看起来很小的事在判题系统里就是零分。常见的边界陷阱有数组长度为0或1比如二分查找、快排、DP数组初始化。整数溢出比如计算中间值用(left right) // 2可能溢出可以用left (right - left) // 2。字符串包含空串、大小写混合、特殊字符。链表头节点为空、只有一个节点。循环边界是小于还是小于等于差一个都会错。我建议考试时每写完一道题先手动构造几个极端用例比如空输入、最小输入、全相同输入在脑海里跑一遍。可能多花一分钟但能救回一堆分。还有一个容易忽略的点题目要求的时间复杂度要主动关注。如果数据规模是10^5你写了个O(n²)的算法即使答案正确也会超时。大部分笔试系统会同时卡时间所以最好在拿到题时先看一眼数据范围再决定用什么算法。比如数据范围在10^5级别O(n log n)很稳O(n²)基本没戏。4.2 时间复杂度与空间复杂度的权衡算法工程师笔试中复杂度分析是必考项。有的题目会有“要求空间复杂度O(1)”的限制这时候需要特殊技巧。比如数组原地去重可以用双指针判断链表是否有环可以用快慢指针。这类题还有个共同点代码量不大但思维含量高。一个经典的“空间换时间”例子是计数排序。如果待排序数字范围已知且较小可以用一个计数数组在O(nk)时间内排好比快排更快。但它的缺点是如果数字范围很大比如1到10^9开数组就不现实了。所以笔试时遇到“数组里只有0和1”的排序题就不要用快排了直接扫描一遍统计0和1的个数然后回填。这就是复杂度思维在实操中的体现。再比如LRU缓存设计要求get和put都是O(1)复杂度。单单用哈希表做不到O(1)的淘汰单单用链表做不到O(1)的查询所以必须哈希表双向链表配合。这道题考的不是某个具体算法的复杂度而是组合数据结构的复杂度。这类题在算法工程师笔试中越来越常见。4.3 笔试心态与时间分配的实战建议最后聊聊笔试现场的策略。京东这套题我记得题量不小大概有选择题、简答题和编程题。我的建议是先把所有题通读一遍标记出简单、中等、困难三档。先做会做的保证基础分拿到手。编程题不要一上来就追求完美解法。先暴力解能过一部分用例是一部分之后有时间再优化。选择题里如果遇到不会的可以用排除法但不要把时间耗在一道小题上。手写代码时要注意缩进和变量名清晰机器判卷不看你风格但面试官会看。还有一个我个人的经验考前一定把常见的数据结构实现背到肌肉记忆。不是说笔试会考原题而是当你对链表反转、快排、二分查找这些基础操作足够熟练时遇到新题就能更快上手紧张感也会少很多。从刷题策略上讲我建议按专题刷。第一遍每个专题挑5-10道简单题先把套路摸清第二遍再做中等难度尝试一题多解第三遍做困难题重点训练分析能力。不要天天在剑指offer里面打转LeetCode上按标签刷效率更高。另外强烈推荐准备一个错题本。不是让你抄题而是记录“这道题卡在哪里”。很多时候发现自己反复在边界条件、数组越界、状态初始化这些同样的地方犯错。把这些教训整理成检查清单笔试前扫一眼比刷十道新题都管用。我在实际笔试和面试中发现最打动面试官的往往不是你提交了什么完美答案而是你思考问题的过程。哪怕最后代码没调通只要你能清晰地说明思路、复杂度分析和卡住的点面试官也会给不少分。反过来如果你闷头写代码写完了也不说话即使代码跑通了面试官也很难判断你的工程能力。所以我建议你在准备算法题的时候就养成“自我讲解”的习惯像写博客一样把每道题的思路讲给自己听长此以往面试时自然流畅。