滴滴秋招工程岗笔试复盘：算法、操作系统与数据库考点全解析

秋招季又到了每年的这个时候总有学弟学妹来问我当年笔试都考了什么、该怎么准备。翻出自己整理的滴滴出行2017秋招工程岗笔试记录感慨还挺多。这份笔试题型覆盖很典型算法、数据结构、计算机网络、操作系统、数据库全都有涉及难度在互联网大厂里算中上尤其是编程题特别看重边界条件的处理和复杂度分析。这篇文章就把我当时整理的考点、答题思路和踩过的坑分享出来给正在准备校招的同学一个参考。1. 笔试整体结构与考察模块拆解1.1 笔试模块划分与分值特点滴滴的工程岗笔试在线评测系统做得很规范整场考试大概两个小时左右题型主要分三块选择题、简答题和编程题。选择题大概20到25道每道题分值不大但覆盖面极广从C内存管理到TCP三次握手再到数据库索引原理什么都可能考。简答题一般是1到2道考察系统设计或者某个技术方案的思路这种题没有标准答案但很能拉开差距。编程题通常是2道分值占比最高一道偏重基础算法另一道偏重综合应用这两道题基本决定了你能不能进面试。我当年拿到试卷的第一反应是这笔试不是随便刷刷题就能过的。它考的不仅仅是“会不会”而是“熟不熟”和“能不能在压力下快速写出健壮的代码”。选择题里有些陷阱出得相当刁钻比如C里sizeof和strlen的区别、指针和引用的底层实现差异、虚拟内存和物理内存的映射关系这些知识点如果只是背概念而没有真正写过代码很容易被绕进去。1.2 时间分配与答题顺序策略两小时做三块内容时间其实挺紧张的。我的建议是先做编程题再做选择题最后做简答题。原因很简单编程题需要大脑保持清醒和高度的专注如果先做一堆选择题把精力消耗掉再去看编程题思路容易卡壳。而简答题考察的是知识面和表达就算时间紧也能写个大概框架不至于完全丢分。编程题我给自己定的时间是每题20到25分钟加起来控制在50分钟以内。选择题平均每题1分钟左右遇到卡壳的先标记跳过去不要在一道题上死磕。简答题留15到20分钟把思路写清楚就行不需要像写博客一样长篇大论。整体节奏把控好心态就比较稳。2. 算法与数据结构核心考点剖析2.1 高频算法知识点总结把滴滴这几年的笔试题放在一起看算法题的出题范围其实是有迹可循的。最高频的几类包括数组和字符串的处理、链表操作、二叉树遍历、动态规划、贪心算法、图的最短路径。其中动态规划和贪心几乎是必考的而且不会出特别裸的模板题都会包装一个实际场景。举个例子有一道题是“给定一组区间求合并后的区间列表”其实就是合并区间问题。看起来简单但考察了好几个点排序的自定义比较器怎么写、边界条件怎么处理比如区间为空的场景、合并时怎么更新当前区间的右端点。如果平时没有留意这些细节写出来的代码要么报错要么在极端测试用例上超时。我当时的经验是刷题不能只刷数量要刷类型。LeetCode上的题目按tag分类来刷数组、链表、树、DP、图各刷二三十道基本就能覆盖笔试范围。尤其要注意那些标注为“Medium”的题目这个难度和滴滴笔试的编程题最接近。2.2 编程题实战思路拆解编程题里有一道特别典型的我印象很深题目大概是这样的设计一个数据结构支持插入、删除和随机获取一个元素要求这三个操作的平均时间复杂度都是O(1)。第一次看到这个题很多人会想到用哈希表哈希表的插入和删除确实是O(1)但“随机获取一个元素”如果只用哈希表就很难做到O(1)因为哈希表的key不是连续索引。正确的解法是哈希表加动态数组的组合动态数组存元素哈希表存元素值到数组下标的映射。删除的时候把要删的元素和数组最后一个元素交换然后弹出末尾这样删除操作的均摊复杂度就是O(1)而且数组下标连续随机获取直接用随机数模数组长度就行。这道题考的不是单一的数据结构而是组合数据结构和权衡取舍的思维。面试官想看到的是你能否根据需求分析出每个操作的时间复杂度要求然后选择合适的底层结构去组合实现。这种思路在系统设计题里同样重要后面会细说。另一个常考的套路是双指针。比如“判断一个字符串是不是回文串的变体”“在有序数组里找两个数使得它们的和等于目标值”都是典型的双指针场景。笔试的时候双指针的优势在于空间复杂度是O(1)不需要额外的哈希表所以代码更简洁也不容易出内存错误。2.3 边界情况与复杂度控制笔试编程题和平时自己写代码最大的不同在于评测系统会用各种刁钻的测试用例踩你的代码。空数组、只有一个元素的数组、全部元素相同、目标值不存在、整数溢出……这些边界情况都是常见的卡分点。我自己的习惯是写完核心逻辑之后一定要在脑子里面跑一遍边界测试输入为空或者长度为0时程序能不能正常返回而不是抛异常目标值在数组的第一个位置和最后一个位置时代码表现如何如果涉及加法或者乘法中间结果会不会超出int的范围递归的深度会不会导致栈溢出这些检查花不了两分钟但往往能多救回不少测试用例的分数。还有一个很容易忽略的点复杂度分析。有时候题目会有时间限制比如要求O(n log n)如果你写了个O(n²)的解法小数据量可能能过但遇到大数据量就直接超时。所以拿到题目先分析复杂度再动手写代码这个习惯一定要养成。3. 计算机基础与工程能力考察3.1 计算机网络高频考点解析计算机网络在选择题里占比不低重点集中在TCP/UDP协议、HTTP协议、DNS解析过程和TCP三次握手四次挥手这些考点上。选择题不会直接问你“三次握手的过程是什么”而是给一个场景让你判断。比如“客户端发送SYN后处于什么状态”“服务器收到FIN后还能不能发数据”这类问题需要你对协议状态机有清晰的理解不是背个流程图就能答对的。TCP的可靠传输是另一个重点滑动窗口和拥塞控制这块几乎每年都考。我复习的时候是抓着一个点往深里挖为什么TCP要设计慢启动为什么要区分拥塞避免和快速重传这些问题的答案都在于网络环境不可控TCP需要动态感知网络状况。理解了这个背景那些状态值和参数的升降规律就很好记了。HTTP的考点主要集中在状态码和缓存机制上。304 Not Modified是干嘛的、ETag和Last-Modified的区别是什么、HTTP/1.1的keep-alive解决了什么问题这些都是基础中的基础。我还遇到过一题是关于HTTPS握手过程的问的是对称加密和非对称加密分别用在哪个阶段这种题只要理解“非对称加密用来协商对称密钥”这个核心就不会答错。3.2 操作系统与并发基础操作系统考得最多的是进程和线程的区别、死锁产生的条件、虚拟内存和页面置换算法。这些知识点在大学课程里都学过但笔试的题目往往会结合具体的代码场景来出。比如给你一段多线程程序问它会不会死锁、如果会的话是哪个条件的体现。死锁这块我记得有个经典问题两个线程分别持有锁A和锁B然后都在等待对方释放锁。这就是“循环等待”条件。这样的题考察的就是你能不能在实际代码中识别出死锁的四个必要条件而不是单纯背概念。还有一类关于进程通信的题问“哪种方式最快、哪种方式最安全”。共享内存是速度最快的因为它不需要内核态和用户态之间的拷贝但共享内存需要同步机制来避免数据竞争而管道和消息队列则是通过内核来传递数据安全性好但性能稍差。这种比较型的题目要多从“为什么”的角度去理解而不是死记结论。3.3 数据库与设计类问题应对数据库的考点集中在索引原理和SQL优化上。用索引为什么能加快查询因为底层是B树查询的时间复杂度是O(log n)。那为什么不全部字段都建索引呢因为索引本身需要存储空间而且每次插入和更新都需要维护索引是有代价的。这个权衡思想几乎贯穿所有数据库考题。有时候选择题会问你某个SQL语句执行得很慢可能的原因有哪些选项里可能包括“没有走索引”“查询条件里有函数操作导致索引失效”“返回的字段太多触发了全表扫描”。这类题考的是实际调优的经验建议在复习时多看看执行计划explain命令的输出怎么看、type字段的访问类型从好到坏是怎么排序的这些实践知识笔试真会用到。设计类问题在简答题里比较常见比如“如果要设计一个短链接系统你会怎么设计”。这种题没有标准答案但阅卷人会看你的思路是否完整。我采用的框架是先明确需求再估算数据量然后设计接口最后考虑存储和缓存。明确需求短链接的跳转有没有时效性需不需要统计点击量估算数据量假设每天生成100万条短链接一年就是3.6亿条需要多大的存储设计接口生成短链接的接口和还原长链接的接口分别是什么参数、什么返回值存储方案用自增ID还是用哈希冲突怎么解决需不需要加缓存层把这些问题想清楚就算方案不是最优的至少能显示你有工程思维这部分得分通常不会太低。4. 实操过程中的典型问题与避坑指南4.1 读题不仔细导致的无谓失分我踩过最大的坑就是读题不仔细。有一道编程题我理解成了“统计数组中有多少对元素的和等于目标值”结果标准解法其实是“判断是否存在这样一对元素”把复杂度要求从O(n²)降低到O(n)。而我直接写了个暴力双层循环正确性虽然没问题但完全没达到出题人想考察的优化点测试用例一大就超时。后来我养成了一个习惯读题至少读两遍第一遍抓输入输出格式和复杂度要求第二遍抓边界条件和特殊场景。特别是“如果输入为空”“如果值不存在”这样的描述多琢磨一下往往这些地方就是区分度所在。不要觉得读题浪费时间方向错了代码写得再漂亮也是白搭。4.2 本地调试与在线评测的差异很多同学在本地IDE里运行得好好的代码一提交到评测系统就报错通常是这几个原因输入输出格式不对。有的题目要求一行输出多个数字并用空格隔开有的要求每个数字占一行搞混了就会导致格式错误系统判你错虽然你的逻辑对。本地编译器是C14评测系统只支持C11。某些语法特性比如结构化绑定、std::make_unique在老的编译器下编译不过。数组开小了。题目给的数据范围是10^5的量级你开了一个1000个元素的数组提交后就会出现运行错误。针对这些问题我推荐的做法是在本地用和评测系统版本一致的编译器环境并且写代码时严格控制数组大小和输入输出格式。提交之前用题目样例和自己构造的几个边界数据再跑一遍。这一套流程下来因为环境导致的失误会减少一多半。4.3 语言选择与代码风格的建议滴滴的笔试支持好几种语言C、Java、Python都可以。我个人的建议是哪门语言熟练就选哪门不要为了“显得厉害”去选一门不熟悉的语言。笔试现场的每一分钟都很宝贵你不需要在这一刻去证明自己会多门语言你需要的是在有限时间内写出正确、高效的代码。不过有一点要注意不同语言在性能上的差异是真实存在的。比如用Python写一个需要高频循环的动态规划题大概率会超时但如果用C写同样的逻辑可能轻松通过。所以如果你主攻Python建议在备考时把常用的算法模板都用Python实现一遍并且了解一下哪些操作特别耗时学会用内置的高效数据结构比如collections.deque代替list做队列操作。这样能在不换语言的前提下把性能压榨到最优。代码风格方面规范一点没有坏处。变量名用有意义的英文单词而不是a、b、c逻辑复杂的部分写一行注释解释思路核心函数的入口检查下输入是否合法。这些习惯不只是为了让阅卷人看得舒服更是为了让你自己在调试的时候能快速定位问题。4.4 针对薄弱环节的查缺补漏笔试结束后不管结果如何我都建议把做错的题和卡住的题整理成错题本。不是抄一遍题目和答案而是记录三件事当时的错误思路是什么、正确解法用到了什么技巧、这个技巧还能用在哪些类似题目上。这个整理的过程比刷十道新题更有价值。我大四那年备考秋招建了一个在线文档按“数组”“字符串”“树”“图”“动态规划”“系统设计”分类把遇到的每道有代表性的题目都做了标签。后来面试其他公司的时候这个文档直接变成了我的复习宝典。笔试的题型虽然每年都会变但核心考点和解题思路是高度稳定的把一类题吃透比追求“刷题量破500”的成就感要实在得多。还有一个容易被忽视的点多练习在纸上写代码。笔试虽然是机考但编程题的难度在于思路思路清晰之后打字只是时间问题。平时如果习惯了在IDE里靠自动补全写代码建议每周抽两三次在记事本或者白纸上写完整代码不靠任何提示。这样能真正锻炼你在面试手写代码时的底气。5. 从笔试到面试的平滑过渡笔试考完后很多人就彻底放松了其实笔试和面试之间往往只有几天到两周的间隔这段时间是复习面试的黄金窗口。笔试里暴露出来的薄弱点面试官大概率也会继续考察尤其是算法题很多面试官会顺着笔试的题目往下追问比如“如果给你的数据量再扩大十倍你的方案还扛得住吗”“能不能用递归的方式再写一遍”。所以我的建议是笔试结束后尽快复盘哪道题没有AC为什么没AC是思路不对还是代码实现有bug哪个知识点记得模糊赶紧去翻书或者查资料补上。我当时就是这样笔试结束后当晚就把所有题目在LeetCode上找到相似题重新做了一遍第二天再看一遍错题然后去面试完全不慌因为刚整理过的知识点都还是热乎的。另外可以准备一两道自己最有把握的算法题复杂度、边界条件、优化思路全部吃透。面试的时候如果被问到“讲一道你觉得最有意思的算法题”你就可以从容地展开展示自己的深度思考能力。这种展示比临时想一道题来讲要效果好得多。我的一个真实体会是面试官真正想看到的不是你会多少题而是你面对一个没见过的问题时能不能冷静分析、拆解、找到思路并且在交流中把自己的思考过程清晰地表达出来。笔试是一次无声的交流面试则是有声的两者的底层逻辑是一致的扎实的基础加上清晰的思维。最后再分享一个小技巧准备笔试的时候给自己模拟真实的考场环境。找一个安静的时间段关掉手机定好两小时计时打开评测网站随机抽一套题完全按照考试的标准来模拟。这样做的目的不是为了刷题量而是为了让身体和大脑习惯这种高压状态。我当时做了三轮模拟到了真实笔试的时候节奏感和心态都稳多了。希望这篇整理对正在备战秋招的同学有帮助。笔试只是第一关保持自己的节奏一步一个脚印往前走。