前几天整理旧电脑里的面试题集翻出一套搜狐2016研发工程师的编程题。这两年我带团队做校招笔试出题和面试评审再看当年的题目还是觉得挺唏嘘没有花里胡哨的脑筋急转弯题目把“研发工程师”四个字摆在明面上考的就是代码基本功、边界意识和状态设计。搜狐2016研发工程师编程题算得上校招题库里比较有代表性的一批字符串、动态规划、贪心、模拟题型都占了难度不算高但区分度很好。这篇文章不打算把整张卷子背一遍我只会把几道真正值得反复做的题拿出来拆解附上Python实现和踩坑记录给正在备战校招的读者一点参考。1. 题目整体观感这套题到底在筛选什么1.1 校招笔试不是竞赛题目设计背后有分工我看到很多同学刷题时只看题目本身不看题目的筛选目标。搜狐2016研发工程师编程题是典型的校招题它不是要筛出算法竞赛金牌选手而是要筛掉三类人第一类连状态定义都理不清就动手写第二类边界条件全凭运气第三类只能背模板、换一个场景就不会用的人。因此它选择了几个很朴素的场景项链、袋鼠、数字统计让考生把注意力放在问题建模而不是套路上。搜狐这套题最值得说的不是难而是它精准地覆盖了研发工程师日常写代码的三个基本能力字符串处理、状态建模、边界控制。我当时参加笔试后和同学复盘发现大部分人不是不会算法而是栽在“想当然”上。比如环状项链直接在原串上做滑动窗口比如袋鼠过河把对岸当成最后一个石头这些都是输在理解题意而不是代码能力。笔试也好面试也好很多时候拼的就是谁先把题目里的约束条件看清楚。1.2 考点分布与难度画像从题型分布看字符串处理和动态规划占了大头这两块正好是笔试出现频率最高的两个能力模型。字符串题考察代码细节动态规划题考察状态设计。整套题没有特别高的计算复杂度最难的地方在于把每个细节想全。我做下来感觉题型友好度4分出题陷阱3.5分如果基础不牢很容易在样例全过、提交0分之间反复横跳。题型代表题核心考点推荐完成时间字符串处理彩色宝石项链滑动窗口、哈希计数、环形数组15-25分钟动态规划/贪心袋鼠过河状态转移、区间覆盖、边界设计20-30分钟统计排序数组计数/字典序排序哈希表、排序、贪心取最大最小10-15分钟模拟日期/规则计算数据结构选择、逻辑完整性15-25分钟这里我特别提醒一点不要因为“真题”两个字就默认题目很偏。恰恰相反校招研发岗的编程题会刻意回避偏题怪题因为公司要招的是一个能写业务代码、能排查线上问题的人而不是只会解竞赛题的人。搜狐2016这套题基本就是按照这个思路出的所以拿它来练手收益比刷一堆冷门OJ题要高得多。1.3 为什么我建议按这个顺序刷题如果你准备刷这套题我的建议是先做统计排序类热手再啃字符串处理最后碰动态规划和贪心。原因很简单统计排序类题目的代码量少主要用于恢复手感和熟悉输入输出字符串处理需要双指针和计数器配合代码细节多动态规划/贪心则对建模能力要求更高适合在头脑清醒的时候做。按这个顺序刷还有一个好处你可以把前一题用到的数据结构带到后一题里。比如彩色宝石项链用了哈希计数器袋鼠过河虽然不需要计数但如果你先把计数器的游标思维练熟了后面理解“当前覆盖区间边界”也会更顺。知识迁移是校招笔试里很占便宜的能力。2. 彩色宝石项链环转链和双指针的经典组合2.1 题目到底说了什么题目大概是这样一条由若干宝石串成的环形项链每颗宝石有颜色颜色一共就B、G、R、Y四种。现在想从项链上截取连续的一段保证这段里四种颜色都出现并且段尽量短输出最短长度。这是一个典型的“最短覆盖子串”问题。示例字符串s BGYRBRGY你可以从第三个字符 G 开始取GYRB长度4也可以从第六个字符 R 开始取RGYB长度4。当然因为要覆盖四种颜色答案不可能小于4。这道题最迷惑人的地方是“环形”。很多人在纸上画的时候知道可以绕一圈但一写代码就只会在原字符串上找连续区间。字符串是线性的项链是环形的这两个模型之间的转换恰恰是这道题的第一个考点。2.2 为什么要复制一遍处理环形数组最直接的思路是“环转链”也就是把原字符串复制一遍拼在后面。项链从任意位置切开对应线性串上以该位置为起点的连续n个字符。复制一遍后任意起点向右走n个字符都能覆盖环上所有起点的情况。这里有一个关键约束窗口长度最多为n。因为环上的连续段绕一整圈就回到原点不能把两圈以上的内容也算进去。如果只复制不限制长度很容易写出一个看似能跑、实际上会绕出错误答案的代码。打个比方你站在环形跑道的某个点向前看一圈能看到跑道上所有位置。如果你允许自己看一圈半那么第二圈看到的其实是重复信息对找最短区段没有任何帮助只会让代码在某些数据上意外出错。2.3 滑动窗口的完整实现滑动窗口的核心是维护当前窗口中各类字符的出现次数并记录当前已有多少个目标颜色种类。右指针不断扩展窗口当四种颜色都齐了就尝试移动左指针收缩窗口并更新最短长度。很多人会想既然是四种颜色那用一个集合存当前窗口里的颜色判断集合大小是否为4不就行了吗问题在于窗口收缩的时候如果某个颜色在窗口里出现了两次左边界往右移动后这个颜色依然还在窗口里集合无法表达“次数归零”这个状态。所以必须用计数器记录每个颜色出现了几次只有当某个颜色从1变成0时有效种类数才减一。这是滑动窗口类题目的通用写法。def shortest_necklace(s: str, need: set) - int: n len(s) if n 0 or len(need) 0 or len(need) n: return -1 t s s # 环转链 cnt {} # 记录窗口内目标颜色的出现次数 kind 0 # 当前窗口已覆盖的目标颜色种类数 ans n 1 left 0 for right, ch in enumerate(t): if ch in need: cnt[ch] cnt.get(ch, 0) 1 if cnt[ch] 1: kind 1 while kind len(need): cur_len right - left 1 if cur_len ans: ans cur_len # 窗口已经覆盖整个环不可能更短直接返回 if cur_len n: return ans left_ch t[left] left 1 if left_ch in need: cnt[left_ch] - 1 if cnt[left_ch] 0: kind - 1 return ans if ans n else -1 s BGYRBRGY print(shortest_necklace(s, {B, G, R, Y}))输出是4。代码里我额外加了一个判断当窗口长度已经达到n时说明已经看遍了整条项链的所有位置再往右扩展只会绕第二圈不会产生更优解直接返回当前答案。2.4 这道题容易踩的坑第一个坑是忘记环转链只在原串上做双指针。这样只能找到“从某个位置切开后线性子串”的最短覆盖丢掉了绕一圈才能覆盖的情况。第二个坑是窗口长度没有限制让窗口在复制后的字符串上无限扩大最后可能得到一个长度大于n的“假答案”。第三个坑是只统计目标颜色却把非目标颜色的字符也放进了计数器。比如用例里如果混入A、C这类字符它们不应该影响种类判断但如果你无脑计数会导致left移动时计数错乱。第四个坑是初始判断。如果need里的颜色种类数大于n或者字符串里根本没有某些颜色应该直接返回-1而不是进去跑一遍循环否则会浪费很长时间才发现答案不对。3. 袋鼠过河动态规划与贪心边界条件决定成败3.1 题目描述与状态定义袋鼠过河是另一道让我印象深刻的题。题目描述大致是河上一字排开n个石头袋鼠从第0个石头出发第i个石头上写着数字a[i]表示从该石头起跳最多能跳过a[i]个石头。也就是说站在石头i上可以跳到i1到ia[i]之间的任意一个石头。问袋鼠最少跳几次能到达对岸也就是到达或超过下标n的位置。如果不能到达输出-1。举例n5a [1, 3, 1, 1, 1]。从0跳到1再从1跳到4最后从4跳到对岸共跳3次所以输出3。这里最容易搞混的地方是“对岸”不是最后一个石头而是最后一个石头之后的位置。下标n才是对岸。3.2 动态规划解法先想清楚再优化拿到这种“最少步数”问题第一反应是动态规划。定义dp[i]为从起点跳到第i块石头需要的最少次数dp[0] 0其他初始化为无穷大。转移时从每个位置i尝试跳到它能到达的所有位置j更新dp[j] min(dp[j], dp[i] 1)。为了不让对岸边界变得绕我建议直接把对岸也当成数组的一个位置下标n。dp数组长度开n1这样当j n时表示已经到对岸计算和判断都很自然。def solve_dp(n, a): INF float(inf) dp [INF] * (n 1) dp[0] 0 for i in range(n): if dp[i] INF: continue for j in range(i 1, min(n, i a[i]) 1): dp[j] min(dp[j], dp[i] 1) return dp[n] if dp[n] ! INF else -1这个写法特别适合用来和贪心解法对拍。它虽然时间复杂度高但语义非常清晰不容易错。当n只有几百或者a[i]值很小时直接交这个版本完全没问题。但如果n到10^5量级这种两层循环就会超时必须换思路。3.3 贪心解法跳得远不如覆盖得远袋鼠过河的贪心解法和经典跳跃游戏II完全一致。核心不是模拟“具体站在哪块石头上”而是维护“当前这一段跳跃次数能覆盖到的区间”以及这个区间里所有石头能延伸出的最远位置。变量cur_end表示当前必须完成下一次跳跃的边界farthest表示当前区间内所有点能到达的最远位置。遍历每个石头i先用i a[i]更新farthest。如果farthest已经达到或超过n说明再跳一次就能到对岸返回steps 1。当遍历到cur_end时说明当前覆盖区间已经走到头必须增加一次跳跃并把cur_end更新为farthest。def solve_greedy(n, a): if n 0: return 0 cur_end 0 farthest 0 steps 0 for i in range(n): farthest max(farthest, i a[i]) if farthest n: return steps 1 if i cur_end: steps 1 cur_end farthest if cur_end i: return -1 return -1为什么farthest n时返回steps 1而不是steps因为当前记录到steps时说明已经完成了从上一个边界到当前边界的跳跃但还没有实施“从当前区间到对岸”的这一步。只要最远位置能覆盖对岸就需要再跳一次因此答案要加1。3.4 在这道题上翻车的常见现场我见过太多人在袋鼠过河上栽跟头。第一种是把对岸理解成最后一个石头也就是下标n-1导致所有答案都少1。第二种是用DFS回溯去模拟每一种跳法n稍微大一点就递归爆栈。第三种是贪心代码里没有处理farthest i的情况当当前位置的a[i]为0且前面也没有更远位置可以接力时袋鼠会卡死在河中间代码却没有返回-1。建议提交前跑一遍这几个用例n1,a[0]返回-1。n1,a[1]返回1。n3,a[1,0,1]返回-1。n5,a[1,3,1,1,1]返回3。边界条件决定这套题能不能满分。动态规划解法跑通之后再用贪心对拍几组随机数据能有效避免思路正确但细节漏风的尴尬。4. 从搜狐2016研发岗真题里提炼的通用算法套路4.1 环形问题的通用三步法彩色宝石项链带出了一个很重要的模型环形数组处理。以后遇到环形队伍、环形公路、环形队列都可以用三步法第一步把数组复制一份拼在原数组后面第二步通过题目条件限制窗口长度不超过n第三步用滑动窗口、前缀和或者单调队列求解。这个套路之所以好用是因为它把“环”转换成了“线性”而我们对线性数组的处理经验非常丰富。但要记住复制之后不是随便做线性算法就行必须确保结果不会绕出一整圈以上。判断标准一句话任何连续区间的长度如果超过n说明它包含了重复点一定不是最优解。4.2 跳跃/覆盖类问题的双指针贪心模型袋鼠过河抽象出来之后其实是一个区间覆盖问题每个位置i能覆盖[i, ia[i]]这个区间问最少选几个点让区间覆盖到n。贪心模型可以推广到很多场景比如跳跃游戏II、最少加油次数、最小区间覆盖长度等。掌握这个模型的关键不是背代码而是理解三个变量的含义当前覆盖到的右边界、当前区间内能扩展的最远位置、已经使用的跳跃次数。cur_end是“被迫做选择”的边界farthest是“已经拥有的筹码”。每次到达边界时更新跳动次数本质上是在说“当前这一段已经走到极限了我必须再迈一步才能把覆盖范围扩大到之前攒下的最远位置。”4.3 字符串统计题最容易被忽视的细节彩色宝石项链是一道字符串统计题这种题有几个细节特别容易在笔试中翻车。第一字符集要看清。题目说颜色只有B、G、R、Y就不要把其他字符纳入计数否则左指针移动时计数会乱。第二大小写有没有区分。有些题目大小写敏感有些则不敏感最好提前问或者看样例。第三是否需要处理计数器的“从0到1”和“从1到0”两个状态变化。很多人在右指针扩展时记得加一但左指针收缩时忘了减一导致有效种类数永远只增不减。5. 笔试环境里的实战检查清单5.1 拿到题先看数据范围再定算法我习惯拿到题目后的第一件事不是写代码而是看数据范围。数据范围直接决定算法复杂度可以做到什么程度。如果n不超过1000哪怕是O(n^2)的DP也能过如果n是10^5就必须思考O(n)或O(n log n)的解法。拿袋鼠过河来说如果只知道“最少步数”就立刻写DP两层循环容易在数据量大的时候超时。但如果你注意到n可能到10^5就会主动去往贪心方向靠。这是一个很现实的取舍笔试不是追求理论最优而是追求“当前数据范围下能跑过”。为了稳妥我建议先写一个逻辑清晰的朴素解法再用它和优化后的解法对拍两边结果一致再交。5.2 自测边界用例清单每次写完代码我建议脑子里过一遍下面这组边界用例集不是每个问题都要跑完但至少覆盖其中与题面相关的几条空输入或者长度不满足题目最低要求。单个元素或只有两个元素的输入。环形问题中目标颜色只在某一处出现。跳跃问题中起点已经能到达终点。跳跃问题中某个位置的跳跃距离为0。字符串统计类问题中全部字符都相同时的结果。输入数据包含换行、空格、制表符等空白字符时的解析情况。自测样例的价值在于逼你手动模拟一遍过程而不是依赖评测系统去测。很多错误在脑子跑一遍的时候就能看出来。5.3 Python输入输出提速的姿势在线笔试环境里Python的input()在数据量大时会成为瓶颈尤其是需要逐行读取几百个测试用例时慢得让人想砸键盘。我的习惯是直接用sys.stdin.buffer.read().split()一次性读入所有数据。import sys data sys.stdin.buffer.read().split() it iter(data) n int(next(it)) a [int(next(it)) for _ in range(n)]split()之后得到的是字节串int()可以直接转换所以不需要变成字符串再处理。这种写法在网络编程题里能省下不少时间。不过要注意如果测试数据本身只有一行这种读法也没有问题只是多了一次split而已代价很小。6. 十年后再做这些题从搜狐2016到Python 2025.3一级编程题6.1 为什么旧题仍然值得刷看到热搜词“python2025.3一级编程题题目及答案”被讨论得很热我特意去看了眼Python一级编程题的样题发现核心还是循环、分支、字符串、列表、函数这些和搜狐2016研发工程师编程题的基础要求完全同源。编程题没有新旧之分技术框架可以迭代但算法基本功永远是那几块输入输出处理、状态建模、边界控制、复杂度估算。刷旧题不是为了怀旧而是因为基础题的价值在于稳定。一个研发工程师可以不会最新的框架但必须能快速把“连续子串覆盖”“最少步数跳跃”这类问题抽象出来。这种能力十年前和十年后都是同一套逻辑。6.2 如果从零开始这道题怎么练我给团队新人的建议是分四周练习。第一周看懂彩色宝石项链和袋鼠过河两题的答案把每一行代码注释明白。第二周不看文档手写滑动窗口并且把彩色宝石项链的复制、左指针收缩、计数器更新三个环节分别写成一个函数。第三周给袋鼠过河写DP和贪心两个版本用随机数据对拍保证结果一致。第四周尝试把两道题改成其他场景比如“环形食堂取餐最少覆盖”“青蛙过河最少踩石”看看模型迁移是不是真的理解了。这个过程看起来慢但对打基础非常有效。不要急着追求一天刷十题先把一道题做透比浅尝辄止地做十道题更有价值。6.3 一道Python一级编程题如何复习今天的知识这里用一道Python一级编程题串一下今天的内容输入一行由字母和数字组成的字符串统计数字字符的个数并输出所有数字字符之和。看起来很简单但它同样考察字符判断、字符串遍历、累加器维护这些基本功。def solve(s): digit_cnt 0 digit_sum 0 for ch in s: if 0 ch 9: digit_cnt 1 digit_sum ord(ch) - ord(0) return digit_cnt, digit_sum s input().strip() cnt, total solve(s) print(cnt, total)这种题的代码量不大
