2017滴滴秋招算法岗笔试真题解析：高频考点与答题套路

这套2017年滴滴秋季校园招聘算法岗的笔试真题我在准备校招的时候反复翻过很多遍后来工作里带实习生、帮学弟学妹做模拟面试也经常从里面挑几道题当试金石。说实话题目难度不算变态但它非常有代表性不偏不怪考点密度高能在同一张卷子里同时考察数据结构、机器学习基础和工程思维。如果你准备投算法岗尤其是互联网公司的算法岗这套题很值得拿出来认真过一遍。下面我按当年的考察思路把高频考点、经典题型和答题套路拆开讲一遍也补上一些我复盘时才想明白的坑。1. 先搞懂滴滴算法岗笔试的“出题逻辑”1.1 笔试到底在筛什么样的人算法岗的笔试和平时的算法竞赛刷题不太一样。竞赛题只要代码跑得快、跑得对就行但滴滴这种业务场景很强的公司笔试不只是筛“谁会写代码”更是在筛“谁能把一个模糊的业务问题转化成清晰的计算问题”。地图路线规划、供需预测、订单派单、定价补贴这些滴滴的核心业务背后都依赖算法岗的人能把数据建模和基础算法玩得很熟。所以笔试里往往会出现两类题一类是纯数据结构与算法比如字符串匹配、排序、图论最短路另一类是机器学习或深度学习的基础题比如推导逻辑回归的损失函数、说清楚K-means怎么收敛。前者看你的代码硬功夫后者看你的理论底子和表达是否清楚。从我的复盘经验看这类笔试真正想筛掉的是三种人只会背题但不懂原理的、代码写得出来但边界条件一塌糊涂的、以及理论基础薄弱只能泛泛而谈的。所以你在准备时千万别只刷LeetCode笔试里的简答题往往才是拉分项。我见过很多同学代码题写得不错但让他手写一下LR的梯度更新或者解释一下SVM为什么引入核函数就说不清楚。这类题恰恰是算法岗笔试和开发岗笔试最大的区别。1.2 2017年秋招试卷的整体面貌虽然2017年的原卷现在已经不好找了但从各个渠道流传出来的回忆版来看当年的试卷结构大致是三块选择题、简答题、编程题。整体时长大概90到120分钟题量不算少时间压力很大。选择题一般覆盖概率统计、数据结构、机器学习基础概念。比如给你一个时间复杂度的式子让你选等价结果或者给一段KMP相关的描述让你判断对错又或者问某个损失函数在什么条件下是凸的。这类题看起来简单但考查范围很广你可能在牛客网或LeetCode上刷不到反而要靠平时的积累。简答题则更直接常见的有手推线性回归或逻辑回归的梯度公式、解释贝叶斯公式在垃圾邮件分类中的应用、说明K-means的优缺点等。编程题通常两到三道难度从中等到偏上基本都控制在“你认真想一想能写出来”的程度不会故意出那种需要冷门算法才能解的题。很多同学会被“秋招真题”四个字吓到觉得一定很难。实际上你仔细拆开看绝大多数考点都是各厂笔试通用的东西。滴滴的题目给我的感觉是务实它不会为了难而难更愿意考那些工作中真的会用到的知识点。1.3 这份旧真题放到今天还有参考价值吗有人会问2017年的真题到现在都过去这么多年了还有必要刷吗我的看法是太有必要了。算法考点的更新速度远没有业务和技术栈那么快。KMP、堆排序、Dijkstra、逻辑回归、反向传播这些知识点在今天依然是算法岗笔试的绝对主力。尤其是滴滴这种涉及大量地图数据和交易数据的公司图论、排序、聚类、最短路这些问题几乎年年都会出现。另一方面笔试的出题模式和筛选逻辑也没有变。现在很多公司笔试依然是“选择题简答题编程题”的组合难度和方向也大同小异。刷旧真题练的不是“押题”而是熟悉出题人怎么把业务场景和算法知识结合起来。比如给你一批乘客订单和司机位置让你设计一个派单算法本质上是在考最短路或二分图匹配。这种包装过的算法题只看LeetCode是练不到的必须靠真实笔试题来培养感觉。2. 高频考点拆解数据结构与算法题2.1 字符串匹配与KMPnext数组到底怎么算字符串匹配是笔试中的常客而KMP算法又是其中最经典、也最容易被问细节的知识点。你光会写KMP不够面试官经常会追问一句“next数组是怎么构造出来的”如果答不上来代码题即使跑通了也会扣印象分。我以热搜里那个经典模式串 pabacaba 为例手把手算一遍next数组。这里我用的是最常见的定义next[i] 表示 p[0..i] 这个子串的最长相等前后缀长度也就是当前前缀子串中真前缀和真后缀相等的最长长度。逐个位置来看i0子串是 a真前缀和真后缀都为空所以 next[0]0。i1子串是 ab前缀有 a后缀有 b不相等next[1]0。i2子串是 aba长度为1的前后缀分别是 a 和 a相等所以 next[2]1。i3子串是 abac长度为1的前后缀是 a 和 c不相等更长的前后缀也不存在next[3]0。i4子串是 abaca长度为1的前后缀 a 和 a 相等长度为2的前后缀 ab 和 ca 不相等所以 next[4]1。i5子串是 abacab长度为1的前后缀 a 和 b 不相等但长度为2的前后缀 ab 和 ab 相等所以 next[5]2。i6子串是 abacaba长度为1的前后缀 a 和 a 相等长度为2的前后缀 ab 和 ba 不相等长度为3的前后缀 aba 和 aba 相等所以 next[6]3。最终得到的 next 数组是 [0, 0, 1, 0, 1, 2, 3]。注意不同的教材对 next 数组的定义略有差异有的会整体减一有的会定义成失配后要跳转的下标但核心思想完全一样都是基于最长相等前后缀长度。笔试时如果题目给了定义按题目的来如果没给默认是这个定义即可。手写构造代码也不难我一般用这种写法def get_next(p: str): n len(p) nxt [0] * n j 0 for i in range(1, n): while j 0 and p[i] ! p[j]: j nxt[j - 1] if p[i] p[j]: j 1 nxt[i] j return nxt这里有个关键点while 里回退 j nxt[j - 1]而不是直接把 j 减一。这是KMP算法里最容易写错的地方。很多人在笔试时能背出整体框架但一写到这里就卡住本质原因是没有理解 next 数组存的是“已经匹配过的信息”——当失配时我们不需要从头开始重新匹配而是利用之前计算出的相同前后缀长度来快速回退。另外还想提醒一句笔试时如果允许字符串匹配可以直接调库但KMP依然是高频理论题不要因为能调库就完全不看。我见过太多人KMP代码能背下来但next数组计算题一改参数就不会了。2.2 排序算法从冒泡到堆排复杂度要清楚排序算法几乎是所有算法岗笔试的保留项目也是选择题和手写代码题的重灾区。常见的考察方式有给一段排序过程让你判断是哪种排序、手写快排或堆排、问你某个排序算法稳不稳定、或者比较不同排序算法在特定数据下的表现。先放一张我整理过的常用排序算法复杂度对照表笔试前建议反复看几遍排序算法平均时间复杂度最坏时间复杂度空间复杂度稳定性冒泡排序O(n²)O(n²)O(1)稳定选择排序O(n²)O(n²)O(1)不稳定插入排序O(n²)O(n²)O(1)稳定快速排序O(n log n)O(n²)O(log n)不稳定归并排序O(n log n)O(n log n)O(n)稳定堆排序O(n log n)O(n log n)O(1)不稳定为什么要强调稳定性因为笔试选择题里很容易出现“下列哪个排序算法是稳定的”这类题目。从表里就能看到稳定的通常只有冒泡、插入、归并。堆排序虽然时间复杂度很漂亮但它是不稳定的这个细节很多人会忽略。至于手写代码我最推荐练熟快排和堆排。快排的思路是选一个pivot把小于等于它的放左边、大于它的放右边然后递归处理左右两边。笔试时容易犯的错误有两个一是递归边界没写对导致栈溢出二是partition函数里下标计算错误造成死循环。堆排的话建堆和调整堆是关键建议先把down操作写熟因为后面很多TopK问题都要用到堆。这里有一个我在实际笔试中总结出的技巧如果题目没有特别要求优先写快排或归并因为代码量适中、容错率也高。冒泡排序尽量不要写除非题目明确要求。笔试评分往往看结果更看重你有没有能力在限定时间内写出一个正确的 O(n log n) 排序而不是背一个O(n²)的冒泡上去糊弄。2.3 贪心、二分和动态规划的经典考法贪心算法、二分查找、动态规划这三类题目基本是算法岗笔试编程题的三大支柱。每场笔试至少会遇到一到两题。先说说贪心。贪心题最难的并不是写代码而是“证明这个贪心策略是对的”。笔试时一般不会让你写严格证明但你至少要能从直觉上解释清楚为什么局部最优能推出全局最优。经典题如“区间调度”就是典型的贪心给你一堆会议时间区间问最多能安排多少个不冲突的会议。解法是优先选结束时间最早的区间因为这样能为后续留下更多空间。这道题在滴滴的笔试卷子里很可能会出现变形比如你在一个时间段内最多能接多少笔顺路订单思路是一样的。二分查找看起来很基础但笔试里翻车的概率很高。最容易错的是边界条件while (left right) 还是 while (left right)更新时是 left mid 1 还是 left midright 是 mid - 1 还是 mid我见过太多人在这些细节上纠结最后代码死活跑不过样例。一个相对稳妥的写法是采用“左闭右闭”区间配合 while (left right)然后根据情况调整 mid ± 1。当然不同题目场景可能需要微调但总比每次都是凭感觉写要好。动态规划则是区分度最高的一类题。滴滴笔试里比较常见的有最长上升子序列、背包问题、编辑距离等。做DP题的核心是三步定义状态、写出状态转移方程、确定初始化条件。比如最长上升子序列dp[i] 表示以第 i 个元素结尾的最长上升子序列长度转移时遍历 j i如果 nums[j] nums[i]就用 dp[j] 1 更新 dp[i]。算法不难但很多人栽在“状态定义想错了”或者“初始化忘记赋值为1”这种低级错误上。我建议平时练DP时养成一个好习惯先把状态定义和转移方程用注释写在代码上面再动笔写代码这样即使最后结果不对面试官也能看到你的思路。2.4 图论与搜索Dijkstra、并查集、二分图图论相关的内容滴滴笔试里出现频率不低毕竟地图、路线、派单这些业务和图的联系太紧密了。你至少要把最短路径、并查集、二分图匹配这几块掌握好。Dijkstra是很经典的单源最短路算法思想是每次从未确定的节点里选一个距离最小的用这个节点去松弛它的邻接节点。它的适用场景是边权非负的图如果题目里有负权边就得换Bellman-Ford或者SPFA。笔试手写Dijkstra时推荐用优先队列优化也就是堆优化的版本复杂度能从 O(V²) 降到 O(E log V)。但这里有个坑——优先队列可能会把同一个节点多次push进去所以弹出时要判断一下当前距离是否已经过期避免重复处理。并查集在笔试里经常用来判断图的连通性或者处理动态连通性问题。它的代码非常短核心就是find和union两个操作。我建议你加上路径压缩也就是在find过程中直接把节点指向根节点这样几乎能达到 O(1) 的均摊复杂度。二分图匹配的经典算法是匈牙利算法适用于“最优匹配”和“最大匹配”问题。滴滴的派单场景经常会抽象成二分图左边是乘客右边是司机边代表能匹配求最大匹配数。虽然笔试不太可能要求你默写完整的匈牙利算法但至少要能说出“把问题建模成二分图”这个思路。处理这类问题时建议先画一个简单的二分图模型再考虑用DFS或BFS增广。3. 机器学习与深度学习题目的答法3.1 经典模型原理题LR、SVM、K-means、KNN机器学习的简答题是算法岗笔试里最能体现功底的部分。和开发岗不一样算法岗必须真的懂模型原理不能只停留在“会用sklearn”的水平。逻辑回归LR几乎是必考。你需要能写出它的假设函数、损失函数和梯度更新公式。简单说LR 是对线性组合 z wx b 做 sigmoid 变换得到预测概率。它的损失函数是交叉熵而不是均方误差。为什么用交叉熵因为交叉熵是凸函数配合 sigmoid 时梯度更稳定收敛速度更快。如果你能再多说一句“如果使用MSE容易陷入局部最优”分就稳了。SVM 的必考点是“核函数到底在解决什么问题”。一句话版本是当数据在当前维度下线性不可分时通过核函数把数据映射到更高维空间让它们在高维空间中线性可分。常见核函数有线性核、多项式核、RBF高斯核。面试官很喜欢问“RBF核把数据映射到多少维”答案是无限维因为高斯核的展开式是无穷维的这个细节很多人答不上来。K-means 是聚类算法里的经典。它的步骤很简单随机选 K 个中心点、计算每个样本到中心的距离并分配类别、重新计算每个类的中心点、重复直到中心点不再变化。笔试常问的一个问题是“K-means 一定能收敛吗”答案是能收敛到局部最优但不一定是全局最优。所以实际使用中要多次随机初始化或者用 K-means 来做更好的初始点选择。KNN 则是“懒学习”的代表它训练阶段不学习只是把样本存下来预测时根据最近的 K 个邻居投票。热搜里有一个很典型的问题“KNN算法的应用能力包括哪三个方面”。从我的理解来看可以概括为分类能力、回归能力、异常检测能力。分类就是多数投票回归就是取最近 K 个样本的均值异常检测则是看样本与其邻域的距离距离太远的可以认为是异常点。另外还要注意KNN 对特征尺度非常敏感使用前一定要做归一化否则数值范围大的特征会主导距离计算。3.2 深度学习基本概念反向传播、过拟合、激活函数深度学习的基础概念在现在的算法岗笔试中几乎是必考因为很多团队的日常工作都会涉及神经网络。反向传播是理解神经网络训练的关键。它的核心思想是利用链式法则从输出层开始逐层反向计算损失函数对每个参数的梯度然后用梯度下降更新参数。笔试简答题常让你手推一个两层的反向传播过程这时候不要慌一步一步把链式法则展开即可。我建议你把常见的损失函数和激活函数的导数都记熟比如 sigmoid 的导数是 σ(x)(1-σ(x))tanh 的导数是 1-tanh²(x)ReLU 的导数在 x0 时为 1x0 时为 0。过拟合的经典表现是训练集上效果很好、测试集上效果很差。常见的解决办法包括增加训练数据、降低模型复杂度、加入正则化项L1/L2、early stopping、Dropout、数据增强等。别人只能列名字你能说清楚“为什么 Dropout 能防止过拟合”就会加分——Dropout 随机丢弃一部分神经元相当于在训练多个不同的子网络最后集成这些子网络的预测从而提升泛化能力。还有一个高频考点是激活函数。笔试中常问“为什么需要非线性激活函数”答案是如果没有非线性变换多层神经网络叠起来依然等价于一个线性模型很难拟合复杂函数。所以要选非线性的激活函数比如 ReLU、sigmoid、tanh。但 ReLU 也有问题比如神经元死亡所以现在有很多变体像 Leaky ReLU、ELU 等。能把它们的优缺点对比说清楚已经超过大多数候选人了。3.3 优化与高级算法粒子群、模拟退火、卡尔曼滤波、PID这类算法看似冷门但在滴滴这类偏智能决策的场景里笔试偶尔会出现一道开放性的简答题考察你是不是有足够宽的算法视野。不需要你默写全部公式但至少要能用大白话讲清楚原理。粒子群算法PSO是从鸟群觅食行为中得到的启发式优化算法。每个粒子代表种群中的一个候选解它有自己的位置和速度每一轮迭代会根据个体历史最优位置和群体历史最优位置来更新速度再更新位置。核心就两个更新公式速度更新和位置更新。笔试中如果问你“粒子群和遗传算法有什么区别”可以说粒子群没有交叉和变异操作而是靠粒子之间的信息共享来搜索。模拟退火算法的核心是 Metropolis 准则以一定概率接受比当前解更差的解从而跳出局部最优。这个“一定概率”会随着温度的降低而越来越小最后收敛到近似全局最优。理解它只需要记住一句话——开始的时候敢乱跳后期逐渐趋于稳定。卡尔曼滤波在滴滴这种有大量传感器数据的场景里很实用。它是一种最优状态估计方法分预测和更新两步预测阶段利用上一时刻的状态转移方程预测当前状态更新阶段利用当前观测值对预测结果做校正最终得到一个更精确的估计。它假设系统噪声和观测噪声都服从高斯分布这也是它能写出解析解的原因。PID 控制器则是工业控制领域最常见的算法P 是比例项I 是积分项D 是微分项。比例项响应当前误差积分项消除稳态误差微分项抑制超调。笔试中出现“PID在什么场景下能用到”你可以结合实际业务来答比如订单价格调整、供需平衡控制等虽然精度要求不如硬件控制但思想是一样的。4. 笔试现场实操记录我是怎么安排时间的4.1 拿到卷子后的前10分钟该做什么一定不要拿到卷子就开始埋头写第一道题。先花三到五分钟把整张卷子从头到尾扫一遍看清楚每个part有几道题、大致难度、分值分布。一般来说选择题和简答题的分数占比较高编程题虽然耗时长但分值也大不能轻易放弃。我会做一个简单的优先级排序先做有把握的题尤其是那种一眼就知道答案的选择题和简答题快速拿分然后再集中精力做编程题最后再回头啃不会的题。2017年滴滴这套卷的题量不算小如果你卡在一道难题上时间很快就没了。我在第一次模拟的时候就是栽在了一道KMP的变体题上结果后面动态规划题没时间写非常亏。时间分配方面我个人的习惯是这样的题型建议耗时策略选择题15-20分钟不纠结超过2分钟没思路先标记跳过简答题20-30分钟要求写公式的先写思路再写公式编程题第一题15-20分钟优先拿全部分数编程题第二题20-30分钟尽力而为有思路就写没思路写伪代码检查与补齐10分钟看有没有漏题有没有明显bug这个分配方式不绝对但你心里一定要有一个时间表。见过太多人第一道编程题写得非常完美但第二道题根本没时间看导致总分上不去。4.2 手写代码题的标准动作手写代码题哪怕没有实际运行环境也一定要按“能编译通过”的标准来写。我一般分四步走。第一步读题至少两遍。把输入范围、输出格式、边界条件都圈出来。很多题目里藏着“n 10^5”这样的信息它直接决定你能不能写O(n²)的解法。第二步先在心里走一个暴力解法不需要写出来但要想清楚暴力解法为什么不够好然后针对瓶颈做优化。第三步正式写代码时先写注释把关键变量的含义写清楚。这样即使代码有小问题阅卷人也能看懂思路。第四步自己造几个测试用例包括正常情况、空输入、极端数据在脑子里执行一遍。这里有一个很现实的建议如果实在没有思路可以先写一个暴力解法保证拿到部分分数。笔试评分很多时候是按case给分的暴力解法能过一小部分case比空着拿零分好得多。你可以先写一个正确的暴力版本再在注释里写“优化思路是使用XX算法”这样至少能证明你具备工程思维。4.3 提交前检查清单提交前检查这一环节很多人会忽视但恰恰是拉分的关键。我复盘了自己大大小小十几场笔试总结了一个检查清单变量名和函数签名是否符合题目要求尤其是牛客网或者赛码网那种必须使用固定类名或方法名的题目循环边界条件是否正确特别是二分查找和动态规划里的下标是否处理了空输入和单元素输入数据类型是否会造成溢出比如 int 换成 long 或 long long是否处理了读入多组测试用例的情况时间复杂度是否满足题目限制如果n是10^5O(n²)大概率会超时是否存在死循环风险比如while循环里没有改变循环条件。每次提交前按这个清单过一遍可以有效避免低级失误。我见过有同学快排把partition写错导致栈溢出也见过KMP的回退逻辑写错导致匹配结果不对这些都不是不会做而是检查不仔细。5. 常见错误与排查技巧实录5.1 边界条件与空值问题边界条件是最容易翻车的地方也是最容易通过检查修复的问题。比如KMP算法中如果模式串长度为空直接返回0如果目标串长度小于模式串长度直接返回-1。这些分支是你写主逻辑之前就应该想好的。再比如二分查找很多人在更新边界时写错left mid 还是 left mid 1。如果是查找左边界通常要在 nums[mid] target 时收缩右边界如果是查找右边界则在相等时收缩左边界。笔试时如果你不确定可以通过在纸上画一个长度为2的数组来验证。这个小技巧我用了很多次比自己死记要靠谱得多。再补充一个非常常见的错误数组越界访问。用C写算法题时如果访问了 nums[-1] 或者 nums[n]有时候程序不一定会立刻崩而是读到脏数据导致结果莫名其妙地错。这种问题排查起来最头疼所以写循环之前一定要确认下标范围。5.2 复杂度估算错误笔试时经常出现“为什么我的代码超时了”的情况。其实超时不一定是因为你的思路错而是因为复杂度太高。你需要养成一个习惯看到输入规模先算一下到底选什么算法。一个粗略的经验是1秒大概能跑 10^8 到 10^9 次简单操作。如果你的算法是 O(n²)n 等于 10^5那运算量就是 10^10几乎一定会超时。这时候就应该考虑 O(n log n) 或 O(n) 的解法比如排序后二分、滑动窗口、哈希表辅助等。另外动态规划的时间复杂度也要会估算。比如二维DP状态数是 O(n²)转移如果又是 O(n)那总复杂度就是 O(n³)在 n500 左右可能还能接受但 n2000 就直接废了。很多笔试题目其实设计得刚好卡在“O(n²)能过、O(n³)不能过”的边界上看的就是你会不会算。5.3 环境、语言和输出格式的坑不同平台的笔试环境差别很大。有些平台是LeetCode风格只让你填函数体有些平台是ACM风格需要自己处理输入输出还有一些平台要你用标准输入读取数据并且输出格式不能有多余空格。这些规则在开考之前就应该了解清楚。如果你用的是 C建议把 cin/cout 取消同步可以在 main 函数开头写 ios::sync_with_stdio(false); cin.tie(nullptr); 否则输入输出量大时可能因为性能被卡。如果用的是 Java注意 Scanner 在大数据量下性能较差可以考虑用 BufferedReader。Python 则要注意递归深度限制默认只有1000层如果题目递归深度可能比较大最好改成迭代或加 sys.setrecursionlimit。输出格式方面最常见的坑是“行尾不能有多余空格”。代码跑对了但因为多打了一个空格被判 Presentation Error非常可惜。写输出逻辑时可以用一个简单的技巧第一项前不输出空格或逗号后面的项先输出分隔符再输出数据这样能保证格式正确。6. 复盘了这么多场笔试我最想提醒你的三件事第一件事代码题一定要手写不要只在IDE里敲。笔试是没有代码补全和即时报错提示的平时手写代码越少考场上越容易写出低级语法错误。我自己的训练方法是找一张白纸定时45分钟直接手写快排、KMP、堆排和几个经典DP写完再敲到电脑里验证正确性。第二件事简答题不要只背结论一定要理解推导过程。比如LR的损失函数为什么是交叉熵、SVM的间隔最大化是什么意思这些东西看起来是理论但面试官完全可能追问。你如果只背结论现场很容易被问穿。第三件事做完每一道题后养成自己造极端用例去验证的习惯。空输入、只有一个元素、所有元素相同、数据倒序这几个case覆盖面很广可以帮你抓住很多隐藏bug。我在重新做2017年这套题的时候每写一道题都会主动跑一遍这些极端用例这个习惯让我在后面好几场真正的笔试里躲过了不少扣分点。希望你现在就开始练习别等坐在考场里再后悔。