滴滴2016研发笔试题复盘：算法与基础能力仍是硬通货

1. 为什么专车平台的一套老笔试题现在还有复盘价值提到“滴滴出行2016研发工程师笔试题四”很多刚准备校招的人第一反应可能是一看出行平台题目必然全是算法再看年份2016年的东西早过时了。恰恰相反我手里这份考生回忆版的零散题目最近又被我翻出来重新刷了一遍刷完之后最大的感受是老题不老基本功永远是基本功。2016年前后是移动互联网招聘最热的年份之一很多公司的研发岗笔试题都形成了固定套路线上OJ平台答题限时两小时左右题型分三块——不定项选择题考察基础理论算法编程题考察代码功底偶尔加一两道开放性的设计题。这套“笔试题四”指的就是这类题库里的第四套模拟卷网上流传的多为考生回忆版题目顺序不完整、个别描述有出入但题型分布和难度曲线非常典型。对于正在准备研发岗笔试的人这套题的价值不在“押题”而在于它完整覆盖了互联网公司校招笔试的考察逻辑算法会不会优化基础牢不牢代码能不能直接跑起来边界情况想没想到。这四项能力放到今天依然是研发岗位的核心竞争力。我会在这篇文章里以当时考生回忆得到的题目形态为参照把最值得复盘的几类题拆开讲一遍把我踩过的坑、后来总结出的答题节奏一并说出来。2. 算法题的重建复盘数组、字符串与动态规划怎么拿分2.1 数组类题目先找暴力解再谈优化回忆版里最有代表性的是一道数组重排题给定一个整数数组把奇数放到偶数前面要求保持奇数之间、偶数之间原有的相对顺序时间复杂度O(n)空间复杂度O(1)。这道题现在看依然很有嚼头。大部分人第一反应是快排的partition思想双指针从两端向中间交换。但如果直接套用快排的交换法结果会是奇数之间、偶数之间的相对顺序被打乱。题设里“保持原有相对顺序”这个条件直接封死了经典的左右交换方案。正确的做法是“插入排序思想”的变体用一个指针记录当前已排好奇数的下一个位置遍历整个数组遇到奇数就把它存到临时变量里把当前位置到指针位置之间的所有元素整体右移一位再把临时变量放到指针位置指针加一。这样每个元素最多移动一次整体时间复杂度O(n)空间上只需要一个临时变量。我后来复盘时才发现这道题真正考察的不只是“能不能写出O(n)算法”而是能不能识别题目里的隐藏约束条件。相对顺序不能变本质上就是要求算法具备“稳定性”。一个习惯在LeetCode上刷题的人如果不加分辨地提交快排交换法十有八九会栽在这上面。2.2 字符串题滑动窗口是常客另一道高频题是“找出不含重复字符的最长子串长度”。2016年的时候这道题还没有被刷题平台普及到人手一道的程度但在笔试试卷里已经出现。它最典型的解法就是滑动窗口用一个数组记录每个字符最近一次出现的位置右指针不断向右扩展每遇到一个新字符就检查它是否在当前窗口内出现过如果出现过左指针就跳到上次出现位置的下一个位置。全程只遍历一遍字符串时间复杂度O(n)。这类题容易出错的地方有三个一是字符集范围如果题目没说明只有小写字母最好直接用256大小的数组覆盖ASCII二是窗口边界的更新时机左指针的更新必须在计算长度之前完成否则会把包含重复字符的子串长度也算进去三是处理空字符串时窗口长度计算容易出错建议在循环外直接判断一次。还有一个当年很多人忽略的细节笔试平台的编译器可能不支持C11的某些容器特性。我在考场上写过一次unordered_map结果本地能过提交到OJ上报编译错误后来换成了普通数组才跑通。所以笔试前最好先确认题目页面上标注的编译语言版本而不是默认本地环境。2.3 动态规划从“跳台阶”到“最大子序列和”动态规划在那套卷子里几乎必有一道。回忆版里出现过的是一道跳台阶变种一个人上n级台阶每次可以跨1级或2级问有多少种不同的上法。这就是斐波那契数列用递推就能做并不需要真的开一个n维数组去从头到尾记录每个值。但同类型更值得练的是“最大子序列和”也就是给出一个整数数组找连续子数组的最大和。解法是状态转移dp[i]表示以第i个元素结尾的子数组的最大和要么是前一个状态加上当前元素要么是重新从当前元素开始最终答案是所有dp[i]里的最大值。进一步优化后可以只用两个变量滚动更新连数组都不用开。这类题的共同特点是状态设计决定了后续代码复杂度。如果状态定义错了后面怎么调都别扭。我当时整理过一个小套路——先想清楚“某个位置作为结尾时能产生的最优结果是什么”再想“这个结果和上一个位置的关系是什么”最后再考虑能不能滚动数组。顺着这个思路大多数基础DP题都可以在五分钟内理清。3. 非算法题一样有一堆坑Linux、网络和数据库的选择题3.1 Linux题进程、IO模型和常见的命令选项选择题里Linux所占比重不小。回忆版里有几道关于进程状态和文件描述符的题。比如一个进程在等待磁盘IO完成时它处于什么状态答案是阻塞状态。很多人会误选“就绪状态”因为听课的时候记住了就绪和运行两种状态却忽略了进程等待外部资源时会进入阻塞态只有CPU资源不足时才是就绪态。还有一道关于线程和进程切换开销的题线程切换比进程切换开销小原因是什么因为同一进程内的线程共享地址空间。题目如果考到上下文切换不是考“谁快谁慢”而是考“为什么快”答题时一定要答到共享内存地址、缓存局部性这些根因上。IO多路复用也是那几年开始高频出现的概念。select、poll、epoll三者的区别建议整理成一张表select有文件描述符数量上限poll没有数量上限但每次调用都要全量拷贝描述符集合epoll通过回调机制只返回就绪的描述符。2016年这道题在选择题里出现今天再看它已经成了后端岗面试的必问题但笔试时的考法依然是概念辨析不考源码。Linux命令里容易被忽视的是选项细节。比如查看内存用free查看磁盘IO用iostat查看网络连接用netstat查看进程树用pstree这些命令大家都会但一旦选项加上“-l”“-t”“-u”很多人的记忆就模糊了。备考时花半小时把这些命令的常用选项看一遍比刷十道所谓的“高端题”更划算。3.2 网络题TCP状态机依然是重点网络部分最典型的题目是TCP三次握手和四次挥手。回忆版里有“TIME_WAIT状态出现在哪一端、持续多长时间”这道题答案是主动关闭连接的一方持续2MSL。很多人记住结论但不知道为什么要等待2MSL。这里有一个很实在的解释既要保证最后一个ACK能够到达对方又要让本次连接产生的所有报文段在网络中消失以免干扰下一组相同端口的连接。把这些原因说清楚面试官才会确认你真的理解而不是背的。另外还有一道“TCP与UDP的区别”选择题当年很多人只看传输可靠性忽略了UDP面向报文、TCP面向字节流这个区别。UDP一次发送一个完整的报文应用层读取时按报文边界划分TCP则是一个连续的字节流应用层需要自己处理粘包和拆包问题。这个细节放在工程里特别重要比如自定义协议时候如果业务层基于UDP一条消息对应一个报文接收端开个缓冲区直接读就行基于TCP就需要自己定义消息长度字段来做帧解析。3.3 数据库题索引和事务隔离级别不能只背结论数据库题里索引是我当年最头疼的一块。题目设问方式是“有一个表记录数量约1000万查询条件是where a1 and b2现有两个单列索引(a)和(b)那么数据库会怎么执行这条查询”很多人二话不说选“优先用选择性更高那个索引”但真实答案是MySQL优化器可能会选择合并两个索引的ROWID然后做表回查也可能选择其中一个关键取决于统计信息和实际的数据分布。更常见的选择题是聚集索引和非聚集索引的区别。聚集索引决定了表数据在物理存储上的顺序一张表只能有一个非聚集索引单独存储索引结构和主键值回表通过主键查询数据行。2016年这题还是纯理论到了后面几年面试官会直接问“为什么非聚集索引回表次数多的时候优化器反而不走这个索引”这已经变成一道体验题了。数据库事务隔离级别那部分最容易混淆的是可重复读和幻读。默认的隔离级别如果设置为可重复读当前事务内多次读取同一范围的数据结果是保持一致的但在某些实现下另一个事务向这个范围插入新行后第一个事务的后续查询可能读到新行这就是幻读。要彻底避免幻读需要范围锁或间隙锁。备考时不要只背四种隔离级别的名称要能说清楚每种级别解决了什么问题、又允许什么问题存在。4. 手写代码时的隐性评价标准边界、复杂度与代码可读性4.1 边界条件答题区里的隐形考官笔试的编程题不是写完就算完阅卷人会看代码在关键输入下的表现。空数组、只含一个元素的数组、所有元素都相同、最大值和最小值交替出现这些边界用例往往是决定代码能不能过隐藏测试的关键。举个例子如果题目要求返回数组的最大值和最小值一个常见的错误是初始值设置成0然后循环里比较。当数组里全是负数时最大值结果会错误填成0。正确的做法是把初始值设为数组的第一个元素再从这个位置开始遍历。这种细节在本地测试时很难暴露因为测试数据往往有正有负刚好掩盖了问题。另一个边界问题是数组下标越界。像“最长无重复子串”滑动窗口题右指针移动到字符串末尾时如果再写一次访问当前字符的代码就可能越界。规避的方法是先把窗口长度保存下来再更新指针或者把核心逻辑提前到移动指针之前。笔试不像IDE里有断点调试最好的办法就是提交前在草稿纸上拿一个长度为1的输入手动走一遍。4.2 时间复杂度和空间复杂度的权衡部分编程题会在题目描述里直接给出数据规模比如n不超过10^5这就提示你应该用O(n log n)或更优的算法O(n^2)很可能会超时。如果没给数据规模默认按照最坏情况估算也是一种能力。有些题看着像模拟实际能优化。比如给定一个字符串统计每个字符出现的次数再找出出现次数最多的字符最直接的做法是先排序再统计时间复杂度O(n log n)更优的是开一个长度为256的数组直接计数时间复杂度O(n)空间O(1)。如果题目里的字符集只有26个英文字母甚至可以用26长度的数组写起来更清晰。我在实际刷题时养成了一个习惯每写完一种解法就在代码顶部注释里补一行时间复杂度和空间复杂度说明。笔试未必会看注释但这个过程会强迫我想清楚自己的算法在极端情况下的表现比事后查bug更有效。4.3 代码风格阅卷人不需要“神之一手”很多准备笔试的人只顾着让代码跑通完全忽略了可读性。实际上阅卷人面对大量代码第一遍看的是思路第二遍看的是边界第三遍才会去手动补充测试用例。如果你的代码全是a、b、c、d这种变量名函数逻辑全堆在main里阅卷人很难快速理解你的思路心理分数就会打折。代码风格的核心不是缩进、空行这些表面功夫而是变量命名能否表达业务含义函数能否拆成职责单一的若干段注释能不能解释“为什么”而不是“是什么”。同样是遍历数组找最大值maxNum和curMax一眼就能看出意图而temp、flag2这种命名只会增加理解成本。还有一个实用建议笔试代码尽量少依赖语言的高级特性。能用普通数组解决就不要用字典能用一个循环解决就不要写嵌套。不是说不允许用高级写法而是高级写法更容易在边界条件下出错而且阅读门槛更高。尤其在时间紧张的情况下稳定可靠的代码比炫技的代码得分更高。5. 考场上真实的答题节奏与翻车复盘5.1 我的第一次模拟考在第二题上耗了四十分钟我自己第一次做这套题时犯了一个特别典型的错误前面的选择题节奏太快只用了十分钟结果在第二道编程题上卡了四十分钟。问题是字符串括号匹配的变体要判断一个只包含()[]{}的字符串是否合法。我当时第一反应是用栈但写完之后遇到右括号时没有检查栈是否为空导致输入是)(时直接访问栈顶报错。那次翻车让我意识到笔试和平时刷题的最大区别是平时可以反复调试笔试只有一次提交机会。很多隐藏测试点并不会在示例里出现。)(这种用例平时几乎不会在意但在笔试里它就是真实存在的边界输入。之后我调整了答题策略编程题先花三分钟把题目读懂把可能的边界输入列在草稿纸上再动手写代码。宁可慢一点也不要带着模糊的理解硬写。5.2 答题顺序先捞确定性分数一套卷子里的选择题、填空题、编程题分值不一样。我后来的原则是先做选择题和填空题因为这部分答案相对确定做完就是拿分再挑一道最有把握的编程题做确保能通过基础用例最后再回头处理剩下的大题。编程题内部也可以分优先级。如果第一卷里有三题一题是快排的变体一题是字符串处理一题是动态规划我会先做字符串题——不是因为它最简单而是因为它的解题框架最直接只要边界处理清楚就不容易错。动态规划题哪怕思路清晰也要花大量时间把状态转移方程验证几遍放到最后做更合适。线上笔试平台还有另一个特点提交次数有限制有些平台两次提交之间的间隔有冷却时间。所以在提交前一定要用自己构造的测试用例在本地或草稿纸上跑一遍不要指望OJ帮你发现问题。5.3 草稿纸的重要性笔试虽然是在电脑上打字但草稿纸的作用一点不小。2016年这些笔试题的信息量很大读题、分析、设计算法、验证边界四步全在脑子里过一遍很容易出岔子。我在草稿纸上画一个简单的流程左指针右指针怎么动状态怎么转移画完基本就能把代码顺出来一半。一个实用的草稿习惯是拿到题先在草稿纸上抄一遍题目里的示例输入然后手动走一遍算法把每一步的变量值写下来。如果中途发现结果和预期不符问题要么在算法思路要么在题目的理解排查之后往往能省下大量调试时间。这个方法听起来笨但在笔试紧张状态下非常管用。6. 时间过去快十年老题给我的三点算法启发6.1 算法题的“套路”其实是进化出来的当年做这些题的时候每道题对我来说都是新的做完一道记一道效率很低。后来发现所谓套路其实是大量题目归纳出来的共性双指针往往是解决数组、链表问题的起点滑动窗口是子串、子数组问题的标准框架动态规划的状态设计往往围绕着“以某个位置结尾”做文章。如果当年有人早点告诉我这个思路我可能不会在同样的坑里摔那么多次。刷这套老题还有一个好处它的题目风格和当前LeetCode风格略有差异更偏向基础实现而不是高度技巧性的题目。做完之后反而能反过来把现在那些“包装过的难题”拆回基础模型。比如很多表面复杂的题本质还是排序加双指针很多描述很长的场景题核心还是滑动窗口。6.2 基础题才是拉开差距的地方我后来参与过几次模拟面试和帮学弟学妹看代码发现大多数人在算法题上都能写出一个能跑的版本但真正拉开差距的是选择题里的Linux命令、数据库原理、网络状态机这些“看起来不起眼”的基础知识。那些基础扎实的人在前面的客观题一遍过留给算法题的时间就更充足心态也更稳。所以在备考时不要只顾着刷算法题一定要分出时间把操作系统、计算机网络、数据库三门课的核心概念过一遍。不需要背偏题怪题但必须把最常见的概念理清楚比如进程线程区别、TCP挥手过程、索引的底层结构、事务隔离级别。6.3 回看的意义不是怀旧是把经验内化成判断力重刷这套题最实际的收获不是记住了某道题的答案而是形成了做题前的条件反射看到数组先想相对顺序和稳定性看到字符串先想字符集和窗口边界看到动态规划先想状态定义能否滚动优化。这种判断力才是刷题真正要训练的东西。如果让我给现在的求职者一个建议我会说找几套年代稍微久远一点的真题用严格的限时方式做一遍。做完之后别急着对答案先复盘自己的时间分配和失误类型。这个过程比多做十道新题更有价值因为笔试考的不只是知识储备还有在压力下快速建模、准确实现的能力。这套“2016研发工程师笔试题四”也许并不完美但作为一份训练材料它的价值已经超过了题面本身。刷过、复盘过、总结过它就不再是别人回忆里的旧题而是你自己判断力的一部分。