复盘携程2019届秋招研发岗笔试题型拆解、考点复盘与踩坑记录如果你正在准备OTA行业的研发岗位或者手里正好有一份携程往年的笔试题那么这篇内容应该能帮你省下不少走弯路的时间。我当年参加的是携程2019届秋招研发方向的线上笔试整套题做下来最大的感受是基础题不刁钻但覆盖面很广编程题不算难却非常考验读题和边界处理能力。这篇文章不搞什么标准答案流水账重点是把每一类题型背后的考察逻辑、容易忽略的细节、以及我当时是怎么一步步推导的写清楚希望能给准备同类岗位笔试的同学一些可复用的方法。1. 笔试整体情况回顾1.1 考试形式与时间分配携程当年的研发岗笔试是在牛客网平台上完成的采用在线编程模式摄像头全程监控整个考试时间大概在90分钟左右。题型分为两大部分第一部分是客观选择题大概20道左右覆盖数据结构、算法、计算机基础、数据库、Java或C语言特性第二部分是编程题我记得是3道难度呈梯度上升前面是字符串处理中间是动态规划/贪心类最后一道偏场景建模比较贴近实际业务。这里先说一个很关键的经验90分钟看起来不算短但当你真正进入做题状态会发现时间非常紧。选择题平均每题只能给2分钟遇到需要手算复杂度的题目绝对不能恋战。我当时给自己定的策略是选择题每10题控制在20分钟最多不超过25分钟剩下的时间全部留给编程题。编程题三个题目先花3到5分钟通读所有题面然后从自己最有把握的那道开始做而不是按题目顺序做。这个策略让我在最后一道看起来最难、实际上反而是分最多的题目上从容了不少。1.2 整体难度与淘汰逻辑从难度上说携程这套题在当年的大厂笔试里属于中等偏上谈不上劝退级但也绝对不是随便刷刷LeetCode就能过的。它的淘汰逻辑非常清晰选择题用来筛选基础扎实度编程题用来筛选代码实现能力和业务建模能力。我后来和几个进面试的同学交流得出一个规律编程题AC两道半以上的人基本都能进面试如果只AC一道选择题正确率再高也比较危险。原因是选择题往往是单选、多选混合多选少选错选都不得分容错率很低。加上编程题有部分隐藏测试用例很多人本地跑通了却提交不过说明判卷逻辑不仅看结果对不对还看你代码能否覆盖边界情况。所以备考的时候千万别抱着大概会做的心态输出必须严谨到每一个角落。2. 基础题型拆解选择题考点分析2.1 数据结构与算法考点选择题里数据结构部分占的比重最大我印象最深的是这几类考点二叉树的遍历序列反推、哈希表冲突处理、图的最短路径算法适用场景、排序算法的稳定性与时间复杂对比。先聊二叉树遍历反推。题目一般会给前序和中序让你推出后序或者给中序和后序推层次遍历。这类题看着简单但有两个坑一是递归建树时必须明确根节点在中序序列中的位置这样才能正确切分左右子树二是题目有时候会故意不给NULL标记如果树不是完全二叉树推出来的形态可能不唯一这时候要看选项是否默认了某种形态。我当时用的是手动模拟栈的思路先找根再递归切分左右子树比画图快得多。再比如哈希表携程非常喜欢考线性探测和链地址法的对比以及负载因子对查找性能的影响。这里有一个典型的选择题模型哈希表长度为13哈希函数为H(key)key%13依次插入一堆数问使用线性探测法解决冲突后某个关键字的查找长度是多少。很多同学会漏算“查找失败时比较次数”的区别考试时它往往和查找成功混在一起出。所以我建议做题时先判断题问的是成功还是失败再动手数次数否则答案必错。关于排序算法稳定性和复杂度是送分题但携程会在选项里埋一个不常见但真实存在的坑比如堆排序的空间复杂度。堆排序原地实现时可以做到O(1)额外空间但它不是稳定排序归并排序稳定但需要O(n)空间。这个如果平时只背结论很可能在“以下哪种排序在大多数情况下最优”这种题上选错。我当时直接排除了快速排序最坏O(n²)的干扰项选了改进后的归并变体但后来交流时发现命题人其实更希望从稳定性、空间、最坏情况多个维度综合判断单靠一个维度必然丢分。2.2 计算机网络与操作系统考点网络部分携程考过的点很集中TCP三次握手与四次挥手的状态迁移、HTTP状态码语义、DNS解析过程、Cookie与Session区别。最容易被扣分的是TCP状态迁移里的TIME_WAIT。选择题经常给出一副状态图问你主动关闭方在发送最后一个ACK后进入什么状态很多人选CLOSED但标准答案是TIME_WAIT并且需要等待2MSL。这里牵出一个常考延伸为什么TIME_WAIT要等待2MSL因为要确保最后一个ACK能被对端收到如果丢失对端会重发FIN主动关闭方需要能重新响应同时让旧连接的数据包在网络中过期消失避免污染新连接。理解了这个原因状态迁移题就永远错不了。操作系统这边高频题集中在进程与线程区别、死锁产生的四个必要条件、虚拟内存与页面置换算法。有一道题让我印象很深问的是“系统中只有一个CPU以下哪个调度算法可能导致饥饿”。选项有先来先服务、时间片轮转、短作业优先、多级反馈队列。先说结论短作业优先和多级反馈队列都有可能饥饿因为短作业持续到达长作业永远得不到CPU但如果题目是多选并且只允许选一个就得看它是否加了“可抢占”或“动态优先级”这些限定词。我当时咬定短作业优先因为它在非抢占式下有明显的饥饿风险而多级反馈队列现代的Linux实现已经考虑了老化机制严格来说不算典型饥饿。这种题没有绝对标准关键是在考场上读清楚限定条件。2.3 数据库与Java语言特性数据库题一般考三块索引失效场景、事务ACID与隔离级别、SQL语句执行顺序。携程2019届那道索引题我印象很深给了一张用户表索引是(name, age, city)联合索引然后给了四条SQL问哪一条不会用到这个联合索引。核心规则就是最左前缀原则只要查询条件里没有name索引就基本失效如果name用了like %xx这种前导通配也会失效如果对age做了函数运算同样失效。这种题只要把联合索引的底层B树结构想明白就能推导出来。至于Java携程偏爱考HashMap、并发包、JVM内存区域、类加载机制。有一道多选问的是HashMap在JDK 1.8中做了哪些优化选项包括“引入红黑树优化链表过长”“头插法改尾插法”“扩容时重新计算hash”“增加threshold阈值判断”。答案是引入红黑树和头插法改尾插法JDK 1.8确实把链表长度超过8并且数组长度大于等于64时转红黑树扩容迁移时不再全部rehash而是通过原位置或原位置旧容量的方式拆分。很多人会把这个“扩容时重新计算hash”选上但它只属于JDK 1.7的做法1.8已经优化掉了。这种题就靠平时对版本差异的敏感度。3. 编程题实战复盘3.1 第一题字符串加工与去重编程题第一道通常是热身级别但热身不等于送分。我拿到的那题大概是给定一个字符串要求删除所有相邻且相同字符中的后一个重复操作直到不存在相邻相同字符为止输出最终字符串。举个例子输入aabbcc先删除aa中的后一个a得到abbcc再删除bb中的后一个b得到accc再删除cc中的后一个c得到ac所以输出ac。当时第一反应是用栈模拟从左到右遍历字符如果栈顶元素和当前字符相同则当前字符不入栈并且把栈顶弹掉相当于消除一对相邻相同字符。需要注意这里的操作语义是“删除后一个”而不仅仅是“去重”所以用栈正好符合消除对子的逻辑和括号匹配本质一样。这道题真正容易错的地方是循环次数。如果写成嵌套while循环每次从头扫描字符串遇到相同就删虽然结果也可能正确但在字符串长度到10^5级别时会超时。正确做法是线性扫描加栈复杂度O(n)。我当时还额外考虑了一个隐藏用例输入abccba如果按“删除后一个”操作整个过程是abbba到aaa再到空串最终输出空。如果只是简单判断相邻相同很容易在第一次消除后漏掉跨位置的新相邻相同字符。用栈实现天然规避了这个问题因为每次入栈前都和栈顶比较新暴露出来的栈顶会自动参与下一轮比较。public String removeDuplicates(String s) { DequeCharacter stack new ArrayDeque(); for (char c : s.toCharArray()) { if (!stack.isEmpty() stack.peek() c) { stack.pop(); } else { stack.push(c); } } StringBuilder sb new StringBuilder(); while (!stack.isEmpty()) { sb.append(stack.pollLast()); } return sb.toString(); }这里有一个细节需要注意栈是先进后出最后输出时需要反转或者像我这样用pollLast从队尾取相当于让结果恢复原始顺序。笔试环境的判题只认输出字符串顺序错了哪怕字符集合对也会全错。3.2 第二题最少钞票数动态规划第二题开始上强度了。我遇到的题目大概是有若干种面额的硬币每种数量不限给定一个金额M问凑齐M需要的最少硬币数量如果凑不齐输出-1。这是典型的完全背包/动态规划题。状态定义很简单dp[i]表示凑出金额i所需的最少硬币数初始化dp[0]0其余为无穷大。对每个金额i遍历所有硬币面额coin如果icoin则dp[i]min(dp[i], dp[i-coin]1)。复杂度是O(M*N)其中N是硬币种类数M是目标金额。但携程这道题刻意加了条件部分面额可能无法被组合需要输出-1。很多同学只做了dp忘记了最终判断dp[M]是否为无穷大直接在输出时取了个超大数字导致隐藏用例失败。还有一个坑是金额M可能为0这时候最少硬币数是0程序要能直接输出0。我当时为了保险用了两层循环的顺序优化把硬币面额放外层、金额放内层这样每次更新都会基于前面已经计算出来的最优值天然支持每种硬币无限使用。有些同学会写成金额外层、硬币内层这种写法在“每种硬币只能用一次”的0/1背包里是正确的但在这个场景下会漏算重复使用的情况。public int minCoins(int[] coins, int m) { int[] dp new int[m 1]; Arrays.fill(dp, Integer.MAX_VALUE / 2); dp[0] 0; for (int coin : coins) { for (int i coin; i m; i) { dp[i] Math.min(dp[i], dp[i - coin] 1); } } return dp[m] Integer.MAX_VALUE / 2 ? -1 : dp[m]; }其实这题还能再优化如果硬币面额有公因数且M不是公因数的倍数可以直接判-1但笔试时没必要做这个数学优化dp已经足够。真正的问题是Integer.MAX_VALUE直接加1之后会溢出变成负数导致min函数选出负数所以初始化时必须除以2或者用一个足够大的常量这个细节没有踩过坑的人很难意识到。3.3 第三题订单行程拼接与拓扑排序第三题是最有意思的一道也很能体现携程的业务基因。题目大概是给出一组高铁订单记录每张订单包含起点站和终点站现在要求把所有订单拼接成一条完整行程使得前一站的终点是后一站的起点。每个站点可能出现在多个订单中且订单可能存在环要求判断是否能形成一条覆盖所有订单的完整路径并输出站点顺序。这道题的本质是有向图的欧拉路径或拓扑排序问题。先说判断逻辑如果整个行程能串成一条线那么除起点和终点外每个站点的入度等于出度起点入度比出度少1终点出度比入度少1。如果所有站点入度等于出度则可能是环题目如果要求“单条不重复路径”环也可以构成答案但如果有多个连通分量则无法拼接。实现的时候要先建图用MapString, List 保存每个站点可以到达的下一个站点列表同时统计入度出度。找起点的方法是遍历所有节点找到入度比出度小1的那个点如果不存在这样的点说明是环可以从任意站点出发。路径构造用深度优先搜索加栈实现。这里有个细节一定要先深入访问邻接节点再回头把当前节点压栈也就是Hierholzer算法的逆序输出。由于邻接表里可能有多条相同边需要维护一个全局的边访问计数器或者直接删掉用过的边否则会重边导致输出错误。我当时就吃过这个亏忽略了一个站点到另一个站点可能存在多张订单的情况结果输出路径长度不对。这道题给我的感受是它对工程建模能力的要求比前两道高很多。题目没有直接告诉你“这是图论题”你需要自己从订单拼接的业务描述里抽象出节点和边的概念。如果平时只是刷纯算法题、不习惯读业务题面很容易卡在第一步建模上。4. 工具选择、边界处理与考场实战经验4.1 在线笔试环境与语言选型在线编程题我建议优先选自己最熟练的语言不要想着用“看起来更高级”的语言。携程当时支持C、Java、Python我选Java因为List、Map、Deque这些容器都是现成的写起来比C少很多内存管理的烦恼。但Java也有短板如果题目给的数据范围特别大比如10^6级Java的Scanner读取速度会明显偏慢建议直接用BufferedReader按行读再用split处理。在线IDE通常没有代码提示所有import都要自己手写。我那次就遇到一个尴尬忘了import java.util.Deque本地编译是通过的因为我在本地IDE里自动补全了但面试笔试的编辑器是白板环境直接报编译错误。所以备考时一定要在无提示的环境下多练几次把常用类库的import背下来。4.2 边界条件与隐藏用例的常见坑在线判题最气人的就是“本地全对提交0分”。我复盘时总结了几类高频边界条件第一空字符串和空数组。很多人的代码逻辑是正确的但一上来就对数组下标做访问输入为空时直接数组越界。做任何题之前先想一想“如果输入长度是0我应该输出什么”。第二数字溢出。尤其是动态规划里用Integer.MAX_VALUE做初始值在下一次加1时溢出。我前面提到的除以2就是经验之谈。第三题目给的是多组输入。牛客网的笔试题目经常要求循环读入直到EOF很多人只处理了一组数据就结束程序系统会判定超时或者只过部分用例。写循环读取框架必须成为肌肉记忆。第四输出格式。题目要求输出结果占一行多个结果用空格分隔你看着无所谓但判题脚本会精确比对。多余的换行、行尾空格、小写字母和大写字母都会导致格式错误。建议在输出前用trim处理一下但注意如果题目要求保留前导空格就不能盲目trim。4.3 时间分配与做题顺序的实战建议90分钟的考试我的时间分配大概是前20分钟做完全部选择题中间60分钟投入编程题最后10分钟检查选择题和程序输出格式。这里要特别强调检查不是把代码重新读一遍而是要针对每个题目的边界条件构造自己的测试用例在头脑里跑一遍。比如说字符串消除那道题我会在本地试一下输入aaa输出空串试一下输入ab输出ab试一下输入aab输出b。如果几个用例都通过代码基本稳了。对动态规划题我会试一下m0、m1且没有面额为1的硬币、硬币种类为空这三种情况。对图论题我会试一下只有一个订单、订单成环、有两个独立的行程片段这三种情况。做题顺序上我的经验是先做第三题第二题这种分值高的最后做第一题。但每个人的强项不同更合理的方式是先花3分钟通读全部编程题把三道题的难度和数据范围标记出来然后从自己脑子里“解题路径最清晰”的那道开始。不要因为题目顺序靠前就先做因为笔试时间是不可再生资源第一道题如果卡住了后两道可能连看题的时间都不够。5. 笔试复盘外的延伸思考与心得5.1 携程出题风格背后的业务逻辑复盘完整套题我发现携程笔试很看重“把业务场景抽象成算法模型”的能力。第三题的订单行程拼接核心就是图论的欧拉路径但它不会直接告诉你“给你一个有向图求欧拉路径”而是把它包装成高铁订单、航班中转、酒店连住这些实际场景。这就是OTA行业研发和纯互联网业务研发的差异。携程后面面试时也会追问分布式缓存、订单状态机、高并发下库存扣减这类问题笔试题其实是在提前筛选是否具备这种业务思维。所以备考时不要只刷题还要多想想这些算法在真实业务中到底是怎么落地的。比如动态规划最少硬币表面上是凑金额实际上可以映射为酒店优惠券叠加的最优策略问题字符串消除也可以看作订单号去重、优惠券码清洗的底层逻辑。带着这个思路去做题你会发现题目不再是冰冷的算法而是一套可迁移的建模方法。5.2 踩过的坑和后来总结出的备考方法我自己备考时最大的坑就是前期刷题只刷LeetCode的Medium难度忽略了在线笔试环境的特殊性。LeetCode的判题逻辑是函数输入输出函数签名都给你定好了你只需要写核心逻辑但校招笔试是ACM模式你要自己处理输入输出自己考虑多组数据自己输出结果。这个差异让很多人在LeetCode上能轻松解题一到牛客网笔试就懵。后来我的备考方法调整为每周至少三次在牛客网或类似平台做完整套模拟题严格按照考试时间不管做没做完都准时交卷。做完之后不是看一眼解析就结束而是把每道题的错误原因整理成错题集比如“这次是因为Scanner读取超时”“这次是因为没用栈模拟导致超时”“这次是因为忘了处理空输入”。到考前一周我只看错题集不再刷新题。5.3 笔试之后如何衔接面试如果你笔试顺利通过那么接下来迎接你的是技术面试。笔试里的题目尤其是编程题面试官很可能会问“当时你是怎么想的”。这时候千万别只说“我用了栈”或“我用了动态规划”而是要把建模过程讲出来为什么状态转移方程这么定义为什么这个方案最优边界条件怎么处理有没有考虑过更高效的做法。如果你能把自己笔试时的思考过程完整复述出来并补充一两个踩坑后总结的细节面试官对你的好感度会明显提升。这比面试前临时抱佛脚刷几道八股文有效得多。最后再说一个小技巧笔试结束后不管你自我感觉如何尽量把题目和自己的代码留在本地等整个流程结束后再做一次复盘。我当时把三道题按原题数据范围重写了一遍并且尝试了不同解法比如把第二题从动态规划改成BFS把第三题用并查集辅助判断连通性。这些延伸训练在我后续面试的算法环节帮了大忙因为面试官一旦追问优化方案你不至于只能背出标准答案。