复盘携程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) { Deque<Character> 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，如果i>=coin，则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。如果所有站点入度等于出度，则可能是环，题目如果要求“单条不重复路径”，环也可以构成答案，但如果有多个连通分量则无法拼接。
实现的时候要先建图，用Map<String, 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"。如果几个用例都通过，代码基本稳了。对动态规划题，我会试一下m=0、m=1且没有面额为1的硬币、硬币种类为空，这三种情况。对图论题，我会试一下只有一个订单、订单成环、有两个独立的行程片段，这三种情况。
做题顺序上，我的经验是先做第三题第二题这种分值高的，最后做第一题。但每个人的强项不同，更合理的方式是：先花3分钟通读全部编程题，把三道题的难度和数据范围标记出来，然后从自己脑子里“解题路径最清晰”的那道开始。不要因为题目顺序靠前就先做，因为笔试时间是不可再生资源，第一道题如果卡住了，后两道可能连看题的时间都不够。
5. 笔试复盘外的延伸思考与心得
5.1 携程出题风格背后的业务逻辑
复盘完整套题，我发现携程笔试很看重“把业务场景抽象成算法模型”的能力。第三题的订单行程拼接，核心就是图论的欧拉路径，但它不会直接告诉你“给你一个有向图，求欧拉路径”，而是把它包装成高铁订单、航班中转、酒店连住这些实际场景。
这就是OTA行业研发和纯互联网业务研发的差异。携程后面面试时也会追问分布式缓存、订单状态机、高并发下库存扣减这类问题，笔试题其实是在提前筛选是否具备这种业务思维。所以备考时不要只刷题，还要多想想这些算法在真实业务中到底是怎么落地的。
比如动态规划最少硬币，表面上是凑金额，实际上可以映射为酒店优惠券叠加的最优策略问题；字符串消除，也可以看作订单号去重、优惠券码清洗的底层逻辑。带着这个思路去做题，你会发现题目不再是冰冷的算法，而是一套可迁移的建模方法。
5.2 踩过的坑和后来总结出的备考方法
我自己备考时最大的坑，就是前期刷题只刷LeetCode的Medium难度，忽略了在线笔试环境的特殊性。LeetCode的判题逻辑是函数输入输出，函数签名都给你定好了，你只需要写核心逻辑；但校招笔试是ACM模式，你要自己处理输入输出，自己考虑多组数据，自己输出结果。这个差异让很多人在LeetCode上能轻松解题，一到牛客网笔试就懵。
后来我的备考方法调整为：每周至少三次在牛客网或类似平台做完整套模拟题，严格按照考试时间，不管做没做完都准时交卷。做完之后不是看一眼解析就结束，而是把每道题的错误原因整理成错题集，比如“这次是因为Scanner读取超时”“这次是因为没用栈模拟导致超时”“这次是因为忘了处理空输入”。到考前一周，我只看错题集，不再刷新题。
5.3 笔试之后如何衔接面试
如果你笔试顺利通过，那么接下来迎接你的是技术面试。笔试里的题目，尤其是编程题，面试官很可能会问“当时你是怎么想的”。这时候千万别只说“我用了栈”或“我用了动态规划”，而是要把建模过程讲出来：为什么状态转移方程这么定义，为什么这个方案最优，边界条件怎么处理，有没有考虑过更高效的做法。
如果你能把自己笔试时的思考过程完整复述出来，并补充一两个踩坑后总结的细节，面试官对你的好感度会明显提升。这比面试前临时抱佛脚刷几道八股文有效得多。
最后再说一个小技巧：笔试结束后，不管你自我感觉如何，尽量把题目和自己的代码留在本地，等整个流程结束后再做一次复盘。我当时把三道题按原题数据范围重写了一遍，并且尝试了不同解法，比如把第二题从动态规划改成BFS，把第三题用并查集辅助判断连通性。这些延伸训练在我后续面试的算法环节帮了大忙，因为面试官一旦追问优化方案，你不至于只能背出标准答案。
