如果你在准备互联网公司的研发工程师校招笔试应该对“去哪儿”这个名字不陌生。作为在线旅游领域的头部玩家去哪儿的研发工程师笔试一直很有代表性题量不大、场景包装多、考点集中但想拿满分并不容易。2016年那套编程题放到现在来看依然是很好的算法热身题——区间合并、滑动窗口、扫描线、0-1背包几乎把校招笔试里最高频的几类模型都覆盖了。这篇文章会把我整理还原后的四道题目、解题思路、完整代码和踩坑经验一次性讲清楚适合正在备战大厂笔试的求职者也适合想系统过一遍经典算法的同学。1. 走进2016年去哪儿研发笔试现场1.1 题型设置与考试环境我印象里2016年前后这类互联网公司的在线笔试编程题一般有4到5道限时90到120分钟不同批次会有差别。考试环境是浏览器里的在线评测系统写完代码点击提交系统自动判分。判分逻辑相当严格不仅看能不能跑通给出的样例还会跑一堆隐藏边界用例所以很多同学“样例过了就是过了”的想法是笔试里最大的坑。语言方面Java、C、Python都有选手用。说实话那个年代用Python做笔试的人还不算多但现在已经完全没问题大部分在线评测系统对Python的支持都很成熟。我的建议很简单哪个语言熟练用哪个不要在考场上尝试不熟悉的语言。去哪儿的题目风格很有辨识度。它不太喜欢出“给一个数组求最大值”这种干巴巴的题而是喜欢把算法包进在线旅游的业务场景里。比如酒店价格区间、景区客流、套餐组合本质上考的还是基础算法但需要你先从业务描述里提炼出数学模型。1.2 高频考点与命题倾向我把这套题里比较有代表性的考点整理成一个表方便你对照考点类型典型业务包装核心数据结构/算法区间合并酒店价格生效区间重叠排序 线性扫描滑动窗口连续无重复关键词统计双指针 哈希表差分/扫描线景区同时在场游客数差分数组 前缀和0-1背包预算内选旅行套餐动态规划 路径回溯四个考点都是非常基础、非常经典的模型没有哪一门是偏题怪题。它们有一个共同点都能从旅游业务里找到原型。在线预订系统离不开日期区间订单系统离不开连续状态流量监控离不开时间窗口套餐推荐离不开预算约束。所以去哪儿的笔试题不是单纯考算法而是在考“把一个业务问题抽象成算法问题”的能力。1.3 这套题放到现在的参考价值有人说2016年的题太老了现在不适用。我反而觉得这套题的价值正好在于“经典”。区间合并对应今天的LeetCode 56滑动窗口对应LeetCode 3差分扫描线对应LeetCode 252/253会议室背包问题更是动态规划里的常青树。你在2025年出去面试很多公司依然在换着场景考这些模型。所以做这套题不是在“考古”而是在帮你把校招笔试的主干知识提前打牢。如果你能把下面这四道题的思路和代码彻底吃透后续再遇到类似题目基本就是换个场景重新做一遍而已。2. 四道经典编程题完整还原下面四道题是我根据当年笔试的常见版本以及网上流传的题目信息整理还原的。语言描述会做适当归纳核心数据和输入输出格式尽量保持原貌。如果你手上有更准确的版本思路完全可以直接迁移。2.1 题一酒店价格区间合并题目描述某酒店在不同时段会执行不同的价格策略运营同学提交了一批价格生效区间每条区间用[start, end]表示代表从第start天到第end天适用同一个价格。现在需要把这些区间合并去掉重叠部分输出最终的连续区间列表。输入格式第一行一个整数n表示区间数量。 接下来n行每行两个整数start和end且保证start end。输出格式输出合并后的区间每行一个按start升序排列。样例输入4 1 3 2 6 8 10 15 18样例输出1 6 8 10 15 18这道题的核心考点很直接先把区间按左端点排序然后一遍扫描维护“当前合并区间的右端点”遇到重叠就扩展遇到不重叠就开启新区间。它考察的是排序 线性扫描也是所有区间类问题的基础。2.2 题二最长无重复子串题目描述给定一个字符串找出其中不含有重复字符的最长子串的长度。你可以假设字符串只包含可见ASCII字符。输入格式一行字符串。输出格式一个整数表示最长无重复子串的长度。样例输入abcabcbb样例输出3样例输入2pwwkew样例输出23这道题的场景包装感不强更像一套通用算法题但它在笔试里出现频率极高。核心是维护一个滑动窗口让窗口里的字符始终保持不重复然后用窗口长度更新答案。它考察的是双指针和哈希表的配合。2.3 题三景区高峰客流统计题目描述景区系统里有n条门票预约记录每条记录给出游客的入园日期和离园日期。景区想知道在同一时刻最多会有多少名游客同时在园。输入格式第一行一个整数n。 接下来n行每行两个整数start和end表示游客从第start天入园第end天离园。这里第end天仍然算在园内。输出格式一个整数表示最大同时在场游客数。样例输入3 1 3 2 4 3 5样例输出2解释一下第1位游客在1、2、3天在场第2位在2、3、4天在场第3位在3、4、5天在场。第2到第3天有两位游客同时在第3到第4天也有两位所以最大值是2。这道题是典型的区间重叠最大值问题。如果你用双层循环两两比较很容易想复杂。换成差分数组或扫描线思路问题就变得非常清晰。2.4 题四旅行套餐最优组合题目描述有m个可选旅行项目每个项目有费用price和满意度value。现在你手里有预算W如何选择项目才能让总费用不超过预算、且总满意度最高。每个项目只能选一次。如果存在多个最优方案输出任意一个即可。输入格式第一行两个整数m和W分别表示项目数和预算。 第二行m个整数表示每个项目的费用。 第三行m个整数表示每个项目的满意度。输出格式第一行输出最大总满意度。 第二行输出选中的项目编号编号从1开始按升序排列。如果没有选中任何项目则第二行输出一个空行。样例输入5 600 200 300 150 400 250 3 4 2 5 3样例输出8 1 4这里选择第1个项目和第4个项目费用是200400600满意度是358。即使总满意度相同方案也不唯一判分时一般只校验最大价值和费用的合法性。这道题表面是“组合”实际是一个标准的0-1背包问题。很多同学看到“输出方案”就以为必须用DFS递归结果预算一大直接超时。正确做法是用动态规划算出最大价值再倒推回溯出方案。3. 算法思路拆解四道题背后的通用套路3.1 区间合并看到区间第一反应是排序区间合并题的关键是你要不要先排序这个决策。以题一为例如果输入区间是无序的你直接遍历根本不知道当前区间有没有跟后面的区间重叠。按下左端点排序之后你其实拥有了一个非常好的性质所有可能重叠的区间在排序后的数组中一定是连续排列的。这样遍历时你只需要维护当前已经合并到的区间。对每一个新区间如果它的左端点小于等于当前合并区间的右端点说明有重叠区域于是当前合并区间的右端点更新为两者右端点的较大值如果左端点更大那说明前面的合并工作已经结束可以开启一个新的合并区间。这里最容易错的一点是用新区间的右端点直接覆盖当前合并区间的右端点。举个例子[1, 5]和[2, 3]合并后应该还是[1, 5]但如果写成直接覆盖就变成了[1, 3]结果完全错了。所以合并时一定要用max(当前右端点, 新区间右端点)。3.2 滑动窗口右边扩展左边收缩最长无重复子串的滑动窗口思路是这样的右指针每次往前扩展一个字符如果新字符没有在窗口里出现过窗口长度就是当前候选答案如果新字符在窗口里出现过就需要把左指针移动到该字符上一次出现位置的下一个位置把重复字符“赶出窗口”。这个思路听起来简单但实现细节很重要。如果用集合set来判重你很难在移动左指针时高效地判断该删除哪个字符。用哈希表记录每个字符最近出现的位置会更自然遇到重复字符时直接查询它上一次出现的位置把left跳到那个位置加1即可。注意这里有个小的逻辑陷阱如果某个字符上一次出现的位置已经小于当前的left说明它已经被移出窗口了这次遇到的字符其实不算重复。所以判断条件是last_pos[ch] left才更新left否则不更新。3.3 差分数组把区间增减变成事件点增量题三如果用最暴力的方式做就是枚举每一天计算这一天有多少游客在场。但日期范围可能很大直接枚举会超时。差分数组的思路是把“区间内的整体增减”转换成“几个关键时间点上的增量”。具体来说对于每条预约记录[start, end]我在start位置的计数加1在end 1位置的计数减1。为什么是end 1而不是end因为题目里第end天仍然在园内所以人数要到end 1才会真正减少。这个细节几乎是题三最重要的考点少了1天结果可能直接错。处理完所有增量后按天数从小到大扫描累加当前计数这个累加值就是当天在场人数。扫描过程中记录最大值就是题目要求的答案。如果日期范围很大且很分散也可以不建数组直接用哈希表存增量最后按键排序效果完全一样。3.4 0-1背包状态转移与路径回溯题四的0-1背包模型核心是状态定义。设dp[i][w]表示在前i个项目中做选择预算最多为w时的最大总满意度。转移时对第i个项目有两种决策不选则状态等于dp[i-1][w]选则状态等于dp[i-1][w - price_i] value_i前提是w price_i。这里有很多同学会问为什么遍历预算要从0到W而不是从大到小因为在二维dp的写法里每一行都是基于上一行计算天然不会重复选择同一个项目。如果你为了省内存改成一维dp那就必须让w从W往0遍历才能保证每个项目只被选一次。这个区别非常重要笔试里不少失分就出在这里。最后要输出具体的方案就需要在算完dp表之后倒推。从最后一个项目开始如果dp[i][w]等于dp[i-1][w]说明第i个项目没被选如果不相等说明它被选中了于是把它的费用减掉继续往前倒推。这就是路径回溯的基本思路。4. 完整代码实现与测试验证4.1 环境与输入输出约定我下面给出的所有代码都用Python 3实现这样描述起来最直观。在在线评测环境里输入通过标准输入读取输出写入标准输出。为了减少行数解析带来的问题我统一用sys.stdin.read().split()一次性读取所有数据再转换成数字。这个习惯在笔试里特别实用能避免很多换行符和空行带来的麻烦。统一读取模板大概长这样import sys def main(): data sys.stdin.read().strip().split() if not data: return it iter(data) n int(next(it)) ...4.2 题一完整代码import sys def merge_intervals(intervals): if not intervals: return [] intervals.sort(keylambda x: x[0]) merged [intervals[0]] for start, end in intervals[1:]: last_start, last_end merged[-1] if start last_end: merged[-1] (last_start, max(last_end, end)) else: merged.append((start, end)) return merged def main(): data sys.stdin.read().strip().split() if not data: return it iter(data) n int(next(it)) intervals [] for _ in range(n): start int(next(it)) end int(next(it)) intervals.append((start, end)) result merge_intervals(intervals) for start, end in result: print(start, end) if __name__ __main__: main()这段代码里intervals.sort(keylambda x: x[0])是核心按左端点排序。merged[-1]始终表示当前正在合并的区间。空输入的情况也做了处理在线评测喜欢给出这种边界用例。4.3 题二完整代码import sys def length_of_longest_substring(s): last_pos {} left 0 ans 0 for right, ch in enumerate(s): if ch in last_pos and last_pos[ch] left: left last_pos[ch] 1 last_pos[ch] right ans max(ans, right - left 1) return ans def main(): s sys.stdin.readline().strip() print(length_of_longest_substring(s)) if __name__ __main__: main()这里last_pos记录每个字符最近一次出现的下标。遇到重复字符且其上次位置仍在窗口内时left跳过去。注意要先更新left再更新last_pos中的位置处理顺序反了会出问题。4.4 题三完整代码import sys def max_visitors(records): diff {} for start, end in records: diff[start] diff.get(start, 0) 1 diff[end 1] diff.get(end 1, 0) - 1 cur 0 ans 0 for day in sorted(diff): cur diff[day] ans max(ans, cur) return ans def main(): data sys.stdin.read().strip().split() if not data: return it iter(data) n int(next(it)) records [] for _ in range(n): start int(next(it)) end int(next(it)) records.append((start, end)) print(max_visitors(records)) if __name__ __main__: main()注意diff[end 1] diff.get(end 1, 0) - 1这一句正因为第end天仍然在园所以人数在end 1天才开始减少。如果你看到样例输出是2说明这个细节处理对了。4.5 题四完整代码import sys def best_plan(prices, values, budget): n len(prices) dp [[0] * (budget 1) for _ in range(n 1)] for i in range(1, n 1): p prices[i - 1] v values[i - 1] for w in range(budget 1): if w p: dp[i][w] max(dp[i - 1][w], dp[i - 1][w - p] v) else: dp[i][w] dp[i - 1][w] chosen [] w budget for i in range(n, 0, -1): if dp[i][w] ! dp[i - 1][w]: chosen.append(i) w - prices[i - 1] chosen.reverse() return dp[n][budget], chosen def main(): data sys.stdin.read().strip().split() if not data: return it iter(data) m int(next(it)) budget int(next(it)) prices [] for _ in range(m): prices.append(int(next(it))) values [] for _ in range(m): values.append(int(next(it))) max_value, chosen best_plan(prices, values, budget) print(max_value) if chosen: print( .join(map(str, chosen))) else: print() if __name__ __main__: main()输出方案时我从最后一个项目往前回溯如果dp[i][w] ! dp[i-1][w]说明项目i被选中记录后把预算减去该项目费用。最后reverse一下让编号升序输出。这比用DFS递归去找方案要高效得多。4.6 样例运行与结果我用上面的代码分别跑这四道题的样例结果如下题一输入 4 1 3 2 6 8 10 15 18 题一输出 1 6 8 10 15 18 题二输入 abcabcbb 题二输出 3 题三输入 3 1 3 2 4 3 5 题三输出 2 题四输入 5 600 200 300 150 400 250 3 4 2 5 3 题四输出 8 1 4如果实在不放心可以自己多造几组数据测。我给个自测建议区间合并加一组[1, 5]和[2, 3]看输出是不是1 5无重复子串加一组空串输出应该是0客流统计加一条记录[1, 1]输出应该是1背包题加一组预算为0的输入验证输出为空方案。5. 笔试过程中的常见坑与排查技巧5.1 输入读取的坑在线笔试输入读取这块我吃过不少亏。input()方式读一行确实方便但如果某一行末尾有空格或者数据里有空行直接split()会得到空字符串处理起来很容易崩。我后来的习惯是统一用sys.stdin.read().strip().split()一次把整个输入读进去再手动按顺序解析。这种方式不太关心行号只关心数据顺序对于“第一行n后面n行区间”这种固定格式尤其好用。唯一要注意的是如果输入可能为空记得先判断data是否为空再执行next(it)。5.2 边界条件最容易丢分编程题里“样例通过但隐藏用例不过”的情况十有八九是边界条件没考虑全。我总结了一下这四道题最容易漏的边界区间合并空数组、只有一个区间、所有区间都重叠、区间相接但不重叠比如[1,2]和[2,3]到底算不算重叠要看题目约定一般start last_end视为重叠。无重复子串空字符串、单个字符、所有字符都相同。客流统计只有一条记录、记录区间是单日、结束时间很大导致end 1超出预定义数组。背包预算为0、项目费用大于预算、多个项目费用恰好等于预算。我建议每道题动笔前先在草稿纸上写三组测试数据最常规的、空的、极端边界的。写完代码后用这三组数据自测能过滤掉绝大部分问题。5.3 时间复杂度的估算与自救笔试时正式写码前先快速估算数据规模。如果n是10^5嵌套循环基本没戏O(n log n)的排序扫描通常很稳O(nW)的背包要看W的范围如果W到了10^6二维数组可能直接内存溢出这时候要么优化成一维dp要么考虑会不会其实是DFS加剪枝。具体到这套题区间合并和客流统计的数据规模一般不会太大Python足够应付最长无重复子串是纯线性扫描数据再大也不怕只有背包题需要特别留意预算范围。如果预算特别大但项目数量很少其实更适合用DFS回溯剪枝而不是动态规划。5.4 调试技巧与提交策略我在笔试现场的习惯是先写主逻辑再写输入解析最后集中测试。主逻辑部分如果结果不对就在关键位置加print看中间变量。比如区间合并里把排序后的数组打印出来背包里把dp[i][w]的更新过程打出来。这些调试输出在最终提交前一定要注释掉不然会被判为格式错误。提交策略上记得优先保证“能过样例并处理常规边界”的版本先交一版再慢慢优化。在线评测系统一般只看最后一次提交结果所以不要等到代码完全满意再交那样风险很大。先把基本分拿到再考虑优化。我个人复盘这套题时最大的体会是编程题真正拉开分数的不是谁掌握了冷门算法而是谁能在有限时间里把普通模型写对写稳。区间合并、滑动窗口、差分、0-1背包这些模型练到“闭眼能写”的程度笔试时心里会踏实很多。最后再分享一个小技巧每次写题前花30秒想清楚输入输出的边界用例再动手敲代码这个习惯帮我避免过无数个隐藏扣分点。