刚从实验室出来翻了翻手机看到有人转了一套滴滴出行2016年的研发工程师笔试题三有点感慨。那年头移动出行正是打得火热的时候滴滴的笔试题在圈内一直以“基础扎实、算法硬核”著称跟某些喜欢出脑筋急转弯的公司完全两个路子。这套题出来之后不少人在论坛上讨论我当时也拿它当过模拟练习。现在回头看虽然过了几年但里面的考点依然很经典对准备大厂研发岗笔试的人来说参考价值一点没减。这篇文章我就把这套题里几个核心考点拿出来做个完整拆解包括我当时是怎么想的、标准解法是什么、有什么容易踩的坑以及这类题在面试环节会怎么延伸。题目本身我尽量还原个别细节如果跟原始版本有出入以知识点为准。准备校招或者想补基础的朋友可以直接把这篇文章当一份复习提纲用。1. 笔试题整体结构与考察重心1.1 题量与题型分布2016年滴滴这套笔试题三整体延续了当时互联网公司研发岗笔试的常见配置单选题、多选题和编程题三大部分时限大概在90到120分钟。选择题覆盖了数据结构、算法、操作系统、计算机网络、C/C语言基础这几个固定板块编程题一般是两道一道偏算法设计一道偏实际工程场景。跟现在很多公司的笔试比起来那年的题目有一个明显特点不搞偏题怪题考的都是“科班生应该烂熟于心的东西”但会在细节上做文章。比如链表操作、二叉树遍历、动态规划、进程同步这些经典考点几乎每套题都会出现但提问方式会换着花样来专门检查你是不是真的理解而不是背了几道题就来应付。1.2 考察方向背后的逻辑滴滴那几年业务增长快服务器压力大线上问题多所以研发岗特别看重候选人的底层功底。这点从题目设置就能看出来选择题里大量出现内存管理、并发控制、TCP状态转移这类实战中天天要面对的问题编程题也倾向于出“业务里能直接落地”的算法而不是纯粹的竞赛题。说白了这套题考的不是“你刷了多少题”而是“你能不能在实际工程里用最小的成本解决问题”。所以如果你打算靠题海战术硬闯效果大概率不理想。正确姿势是把每个考点的原理吃透再配一定量的练习确保换个问法也能认出来。2. 算法题典型题目与完整解析2.1 数组中找出出现次数超过一半的数字这道题在选择题和编程题里都出现过变体。题目描述很朴素一个长度为n的数组其中有一个数字出现的次数超过n/2找出这个数字。常规思路是先排序再取中间元素时间复杂度O(nlogn)空间复杂度O(1)。但笔试考的是更优解法也就是著名的摩尔投票法。摩尔投票法的核心思想是“同归于尽”维护一个候选值和一个计数器遍历数组时如果计数器为0就把当前元素设为候选值计数器置为1如果当前元素等于候选值计数器加1否则减1。因为目标数字出现次数超过一半它跟其他所有数字“抵消”之后最后剩下的候选值一定就是答案。int majorityElement(vectorint nums) { int candidate 0, count 0; for (int num : nums) { if (count 0) { candidate num; } count (num candidate) ? 1 : -1; } return candidate; }这里有件事必须强调摩尔投票法成立的前提是题目明确说了“一定存在超过一半的数”。如果题目没给这个条件你用这个方法得到的结果不一定是正确答案。实际的笔试题里严谨的题目会把条件写清楚但有些变体题目会故意不说明考察你是否有这个意识——那就需要在投票结束后再遍历一遍数组确认候选值是否真的超过一半。我当时做题时踩过这个坑一看到“出现次数超过一半”就直接上了摩尔投票没检查候选值合法性结果在某个测试用例上翻车了。后来养成了习惯凡是这类题目先确认前提条件再选择算法。加一遍验证遍历的时间复杂度还是O(n)完全值得。2.2 单链表反转与环检测链表这块儿滴滴的题里出现过反转链表和判断链表是否有环。反转链表这道题经典到什么程度呢几乎所有公司的笔试面试都会问。迭代写法是标配递归写法是加分项。迭代写法不难核心是三个指针prev、curr、next。每次循环先把curr的下一个节点存起来然后让curr指向prev最后三个指针整体后移。需要注意的就是别把next丢了这是新手最容易犯的错误。ListNode* reverseList(ListNode* head) { ListNode* prev nullptr; ListNode* curr head; while (curr) { ListNode* next curr-next; curr-next prev; prev curr; curr next; } return prev; }判断链表是否有环标准解法是快慢指针快指针每次走两步慢指针每次走一步如果两个指针能相遇说明有环。这个解法空间复杂度O(1)比用哈希表记录访问过的节点要优雅得多。笔试题里这道题还喜欢追问“如果要求找出环的入口节点怎么办”。解法是在快慢指针第一次相遇后把一个指针移回链表头另一个留在相遇点然后两个指针都改为每次走一步再次相遇的位置就是环的入口。这个结论可以通过数学推导验证建议自己画个图推一遍理解之后就不容易忘。2.3 动态规划与字符串编辑距离编程题里有一道很典型的动态规划计算两个字符串的编辑距离Levenshtein Distance也就是把一个字符串变成另一个字符串最少需要多少次插入、删除、替换操作。这在搜索引擎和拼写纠错里是真实场景滴滴的题出这个完全不意外。解法是二维DP定义dp[i][j]表示字符串A的前i个字符转换到字符串B的前j个字符需要的最少操作数。递推公式分两种情况如果A[i-1] B[j-1]那么dp[i][j] dp[i-1][j-1]否则dp[i][j] min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) 1分别对应删除、插入、替换三种操作。int minDistance(string word1, string word2) { int m word1.size(), n word2.size(); vectorvectorint dp(m 1, vectorint(n 1)); for (int i 0; i m; i) dp[i][0] i; for (int j 0; j n; j) dp[0][j] j; 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] min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}) 1; } } } return dp[m][n]; }这类DP题目在笔试里的难点一般不是递推公式本身而是边界条件的初始化。很多人写的时候容易忘掉字符串为空的情况也就是dp[i][0]和dp[0][j]的初值。实战中建议先把这两个边界想清楚再写循环思路会顺很多。3. 操作系统与网络高频考点3.1 进程与线程的区别和联系选择题里关于进程和线程的题几乎是必考的。知识点本身不复杂进程是操作系统资源分配的基本单位线程是CPU调度的基本单位同一个进程里的线程共享地址空间和资源但进程之间相互独立。面试时如果只答到这个程度基本只能算及格。滴滴这类公司更关注的是你对“并发”本质的理解。比如它们会问多线程并发访问共享变量时哪些操作是原子的为什么i不是原子操作这就牵涉到内存模型、临界区、互斥锁、信号量这些概念。备考的时候建议把经典的生产者消费者问题、读者写者问题都手写一遍重点理解条件变量condition variable和信号量semaphore的使用场景。我在实际工作中有一个体会很多并发问题不是靠锁解决的而是靠设计。如果能把共享状态尽量设计成不可变的或者在单线程内完成状态变更就能从根上避免锁竞争带来的性能损耗。笔试虽然不考这个深度但有了这层理解你再去看题目里的死锁、竞态条件描述会轻松很多。3.2 死锁产生的四个必要条件与预防死锁这部分题目常考的是四个必要条件互斥、持有并等待、不可剥夺、循环等待。笔试会给出几个场景让你判断是否会发生死锁或者问哪种策略可以打破哪个条件。举例来说如果一个系统把所有资源按编号排序要求进程只能按顺序申请资源这就是“破坏循环等待条件”如果允许操作系统强制剥夺已经分配给某个进程的资源那就是“破坏不可剥夺条件”。这类题不难但容易丢分的地方是场景判断因为实际给出的业务场景往往把多个条件混在一起需要你逐个核对。我做技术面试官的时候发现很多候选人能背出四个条件但遇到一个具体场景就分析不清楚了。建议备考时不要只背结论试着把每个条件用日常生活中的例子去理解比如两个人过独木桥互相不让就是循环等待如果有人后退一步问题就解决了。理解到这个程度做题基本不会错。3.3 TCP三次握手与四次挥手网络部分的重头戏永远是TCP尤其是三次握手和四次挥手的完整过程。滴滴作为互联网出行平台网络通信质量直接影响用户体验所以TCP相关题目出现频率非常高。三次握手考的不只是“SYN、SYN-ACK、ACK”这三步的名称还会问为什么需要三次而不是两次。答案是三次握手能确认双方的收发能力都正常同时能同步初始序列号防止历史连接请求突然到达引起混乱。如果只有两次握手服务端无法确认客户端的接收能力也无法处理网络中的延迟重复报文。四次挥手也常考比较刁钻的问法是“为什么挥手需要四次而握手只需要三次”。因为TCP连接是全双工的每个方向的关闭都必须单独确认所以主动关闭方发出FIN后对方要先回应ACK然后等自己的数据发完了再发FIN最后主动方再回复ACK这就是四次握手的原因。TIME_WAIT状态的意义在这里也值得一提它保证最后一次ACK如果丢失可以重传同时让旧连接的报文在网络中消失不会干扰新连接。4. 答题策略与实战经验4.1 时间分配与做题顺序这套题的题量和难度决定了你不可能在原地死磕一道题。我的建议是拿到试卷先把所有题目快速扫一遍标注出“一眼就会”和“需要思考”的题按先易后难的顺序做。选择题控制在每题1到2分钟一旦超过3分钟还没思路先标记跳过编程题留足40分钟以上。编程题的做题顺序也有讲究如果你的目标是“能跑通全部测试用例”那就先选自己最熟的题型动手如果目标更高想展示算法能力可以挑一道更有区分度的题先做。但我个人更建议求稳因为笔试系统对部分通过和完全通过的判分差异很大先把能拿的分拿到手再回头挑战难题。4.2 选择题的蒙题技巧与排除法选择题里总有几道题是你拿不准的这时候排除法比蒙答案靠谱得多。操作系统的题涉及进程调度算法、内存置换算法的通常能通过比较选项之间的差异排除掉两个网络题里涉及具体端口号或者状态码的靠记忆而涉及协议行为的靠逻辑。多选题是重灾区漏选和错选都不给分。我的经验是拿不准的选项宁可少选也不要冒险多选。因为少选还能得一半分多选了直接零分。这个策略在不少公司的笔试里都适用不只是滴滴。4.3 编程题的得分点与边界条件编程题在OJ系统里是按测试用例给分的所以边界条件处理得好不好直接决定你能不能拿高分。常见的边界情况包括输入为空、输入长度为1、元素全部相同、目标值不在数组中等。这些用例不值钱但能帮你多过好几个测试点。以链表反转为例边界就是空链表和只有一个节点的链表。以编辑距离为例边界就是一个字符串为空。把这些情况在代码里显式处理掉或者保证算法天然兼容比优化主流程的时间复杂度更能提升得分。很多人刷题时只关注“最优解”忽略了“健壮性”这在笔试里是很吃亏的。我当时准备笔试时有个习惯写完代码后用几组特殊输入在脑子里模拟跑一遍比如空输入、单元素输入、全相同输入。这不花多少时间但能显著减少低级错误。5. 从笔试到面试这套题的延伸价值5.1 题目背后的面试官意图这套笔试题虽然已经过去几年但它的出题思路值得认真琢磨。出题人设计这些题本质是想筛选出具备三种能力的人一是基础扎实能快速反应出经典数据结构和算法的适用场景二是代码过硬能在限时条件下写对、写稳、写干净三是思路清晰面对一个看似陌生的问题能拆解成已知的模型去解决。这三种能力在面试的算法环节里会继续被考察。笔试里的摩尔投票法到了面试可能会变形为“两个数组各取一个数保证某个数的总出现次数超过n/2怎么找”链表反转到了面试可能会变成“按k个一组反转链表”。如果你只是在笔试前背了答案没有真正理解解法背后的思想面试时稍微变个形就露馅了。5.2 如何举一反三最大化这套题的价值我的建议是不要把这套题当刷题素材而是当“查漏补缺清单”。每道题做完之后问自己三个问题这道题考的是哪个知识点我为什么没做出来如果是蒙的这个知识点还有哪些常见变体然后针对薄弱环节去找同类题专项练习。比如摩尔投票法不会就找“多数元素”相关的变体编辑距离不会就把动态规划的几类经典模型背包、最长公共子序列、最长递增子序列、区间DP都过一遍。这样一套题下来覆盖的知识面比单纯刷10套题还广。说实话这几年我面试过不少候选人也在团队里带过新人发现一个规律能把笔试题目背后的原理讲清楚的人在工作里解决实际问题的能力普遍不差。因为技术会迭代框架会过时但数据结构、算法、操作系统、网络这些底层的思维模式不会变。滴滴这套题能成为经典正是因为它考的就是这些不变的东西。最后分享一个我自己梳理这套题目时的小习惯我会把每道错题对应的知识点写在一张A4纸上标注“掌握程度”和“易错点”考前只看这张纸。这个方法帮我高效过完了整个秋招季希望对正在准备笔试的你也有用。