搜狗2019秋招研究员试卷部分编程题合集第二场先说个题外话。前阵子有朋友问我都2026年了刷2019年的老题还有没有意义我的回答一直是校招笔试不像手机系统不存在“过时”这回事。尤其搜狗这种老牌互联网公司的研究员岗考察的从来不是某个框架的API记得多熟而是最底层的算法功底、边界条件敏感度以及在一小时里把思路落成可运行代码的硬功夫。这份第二场的编程题合集我前前后后带过好几个师弟师妹逐题复盘发现它的题型分布非常适合用来检验自己的基础是否扎实。今天就把我的拆解思路和完整解法整理出来希望能帮到正在准备算法岗笔试的朋友。整体设计与思路拆解1.1 这套题到底在考什么搜狗研究员岗的笔试和普通开发岗有明显区别。开发岗更看重工程能力比如你熟不熟悉某个框架、能不能快速调通接口而研究员岗的编程题通常只有两到三道但每道都藏了门槛它默认你熟练掌握常见数据结构默认你具备把数学描述转化成程序逻辑的能力同时还会故意在数据范围上设卡逼你优化复杂度。这份第二场试卷涉及的题型覆盖了深度优先搜索、动态规划、字符串处理、双指针这几个高频方向。我做完之后的第一感受是它不是那种“背模板就能过”的题每道题都需要你现场想清楚状态定义或者自己推导递推公式。这也是我推荐大家反复刷的原因——刷题不能只背答案而是要把每道题的“为什么这样做”想透。1.2 我的选题标准与代码环境说明我这次选择重点分析的几道题标准很简单必须能代表搜狗出题风格的典型题目必须包含值得展开讲的坑点必须能推广到其他同类问题。代码统一用Python 3.8实现环境是macOS终端配合VSCode调试。Python在笔试中的优势不用多说写起来快可读性强适合在有限时间内把思路完整表达出来。不过有一点要提醒如果目标岗位明确要求C或Java平时练习时一定要用目标语言写一遍。Python写顺手了突然切回C处理指针或者STL容器很容易在细节上翻车。我建议笔试前至少用目标语言把历年真题重写一遍确保语法和常用接口不会卡壳。核心细节解析与实操要点2.1 深度优先搜索题的经典陷阱第一道典型的深度优先搜索题我印象很深。很多资料里把它归类为“棋盘类搜索”大意是给定一个矩阵从左上角出发只能向右或向下走要求收集路径上的最大值且某些格子有特殊限制。第一眼看上去像是动态规划能解的题实际上因为限制条件的存在只有暴力搜索才能保证不遗漏。这类题的陷阱在于很多人一看到“最大值”“只能向右向下”就条件反射地写出二维动态规划。但动态规划成立的前提是问题具备最优子结构而这题的某些限制会导致局部最优不一定能推出全局最优。我见过不少基础不错的同学在这里栽跟头不是不会搜而是惯性思维害了自己。我的建议是见到“最大”“最小”“方案数”这类词先花三十秒想清楚题目有没有隐藏的限制条件再用状态转移方程去验证。搜索题的时间复杂度通常较高如果数据范围在15×15以内深搜加剪枝通常能过如果数据范围上百就要考虑记忆化搜索或者改成动态规划了。2.2 动态规划题的状态设计与转移还有一道动态规划题典型的“子序列”或“子数组”问题变形这种题型在各大厂笔试里出现频率极高。这类题核心在于状态定义。状态定义得好转移方程水到渠成状态定义得模糊后面怎么做都不顺畅。我常用的方法归纳为三步第一步明确dp数组下标代表的含义。是“以第i个元素结尾”还是“前i个元素中的最优值”这两个定义有天壤之别。第二步写出初始化和递推关系。初始值通常对应“空序列”或“长度为1的序列”这两种边界情况务必检查i等于0和i等于1时递推是否成立。第三步验证最终答案取自哪个位置。有的题答案在dp[n]有的题答案要遍历整个dp数组取最大值漏掉这一点会导致最终结果差一位。动态规划的提升没有捷径就是多练。每做一道题把状态定义写在纸上解释一遍给自己听能清晰解释出“为什么这样定义”的人基本就掌握了这一类题。2.3 字符串处理的边界条件字符串处理题是笔试的常客这场的题目涉及常见的运算符优先级或者括号匹配变形。这类题看似简单但边界条件极多。我总结出的坑点清单供大家参考输入可能包含空格是否要去除这会影响下标计算。数字可能有多位不能只按单个字符处理。可能出现空字符串必须提前防御。括号不匹配时程序应该如何表现是报错还是返回特定值针对这些边界我建议在设计算法时就把所有输入情况纸面模拟一遍写代码之前先在注释里列出“输入为空的处理方式”“输入为单个字符的处理方式”“极长输入会不会超时”。这些注释不是多余而是给自己理清思路。实操过程与核心环节实现3.1 深度优先搜索题矩阵路径最大值先看第一道题。题目大意是给定一个n×m的矩阵每个格子上有一个整数分数从左上角出发每次只能向右或向下移动要求到达右下角时经过格子的分数之和最大。但是有个限制最多只能走一次“斜向跳跃”所谓斜向跳跃就是从(i,j)直接到达(i1,j1)这个操作不经过中间的格子但只能用一次。第一次看到这道题的时候我的第一反应是加一个维度来记录还能不能使用跳跃操作不过搜索实现更直观。核心思路如下用深度优先搜索模拟所有路径每个状态记录当前位置和是否已经使用过跳跃。如果没有使用过跳跃可以枚举“从当前位置开始跳跃到未来某处”的可能也可以简化成每种状态都只能选择普通向右、普通向下、跳跃一次三种方向。注意跳跃的方向仍然是向右下方不会回头所以天然无环。我用Python实现了一个版本去掉注释后大概三十行def max_score(matrix): n len(matrix) m len(matrix[0]) memo {} def dfs(x, y, jumped): if x n - 1 and y m - 1: return matrix[x][y] key (x, y, jumped) if key in memo: return memo[key] best float(-inf) # 向右走 if y 1 m: best max(best, matrix[x][y] dfs(x, y 1, jumped)) # 向下走 if x 1 n: best max(best, matrix[x][y] dfs(x 1, y, jumped)) # 使用跳跃 if not jumped and x 1 n and y 1 m: best max(best, matrix[x][y] dfs(x 1, y 1, True)) memo[key] best return best return dfs(0, 0, False)记忆化搜索在这里特别重要如果不加memo指数级递归会直接卡死加上memo后每个状态只计算一次整个算法时间复杂度是O(n×m)空间上也是O(n×m)完全够用。这里面还有一个细节就是跳跃的步数。这里的实现是“只能从当前点跳到右下方相邻一格”这是简化后的理解如果实际题目允许跳到任意右下方位置则需要再加一层循环复杂度会变成O(n×m×(nm))数据范围大的情况下很容易超时。3.2 动态规划题最长有效括号子串第二道题是典型的动态规划但披着字符串的外衣。题目要求给定一个只包含左括号和右括号的字符串找出最长有效括号子串的长度。所谓有效括号子串就是左右括号匹配且连续。这道题经典的解法有栈和动态规划两种。搜狗这道题我用动态规划来做方便展示递推关系的推导过程。状态定义dp[i]表示以第i个字符结尾的最长有效括号子串长度。那么这个值只可能是0或者正偶数。递推分两种情况讨论如果当前字符是左括号那么以它结尾的子串一定不合法dp[i]0。如果当前字符是右括号那么需要看它的前一个字符如果前一个字符是左括号那么直接配对dp[i]dp[i-2]2。如果前一个字符是右括号那么要检查有没有更早的左括号与当前这个右括号配对。具体来说要找到i - dp[i-1] - 1这个位置如果这个位置是左括号说明可以嵌套配对此时dp[i]dp[i-1]2dp[i-dp[i-1]-2]。边界情况要特别注意所有下标取到负数时都按0处理。这题算是动态规划里比较考验细节的题递推公式不难难的是脑子里要把字符串下标画出来。代码如下def longest_valid_parentheses(s): n len(s) if n 2: return 0 dp [0] * n ans 0 for i in range(1, n): if s[i] ): if s[i-1] (: dp[i] (dp[i-2] if i 2 else 0) 2 else: left_index i - dp[i-1] - 1 if left_index 0 and s[left_index] (: dp[i] dp[i-1] 2 if left_index - 1 0: dp[i] dp[left_index - 1] ans max(ans, dp[i]) return ans这里最容易被忽略的是第二种子情况里还要拼接上更外层已经匹配的长度。比如字符串“()()(())”里最后一个右括号的匹配既要计算嵌套内部的长度还要把前面“()()”的长度接上。少了这一步结果就会偏小。3.3 双指针题按奇偶排序数组双指针题目是笔试中性价比最高的一类想明白思路后写起来很快。这套试卷里有一道很常规的题目给定一个数组要求将所有奇数移到偶数前面并保持奇数和偶数内部的相对顺序不变。如果是单纯的“奇数在前偶数在后”直接用首尾双指针交换就行但加上“保持相对顺序”这个条件很多O(nlogn)的解法就出现了比如先收集奇数再收集偶数或者用稳定排序。实际上这题在O(n)时间和O(1)空间下是可以做到的用的方法类似于插入排序只是把插入条件从“大小比较”变成了“是否为奇数”。思路如下维护一个指针odd_tail它之前的位置全部是奇数。遍历整个数组遇到奇数时把它保存下来把它之前的一段偶数整体后移一位然后把这个奇数放到odd_tail的位置odd_tail加一。def odd_even_sort(nums): odd_tail 0 for i in range(len(nums)): if nums[i] % 2 1: temp nums[i] for j in range(i, odd_tail, -1): nums[j] nums[j-1] nums[odd_tail] temp odd_tail 1 return nums这个解法的时间复杂度看起来是O(n²)因为内层有循环。但如果题目要求O(n)就需要用到辅助数组先用一次遍历把所有奇数按顺序收集到一个新数组再遍历把偶数接在后面。这个版本的代码非常简洁缺点是空间O(n)。笔试的时候我一般先看数据范围n小于等于一万O(n²)没问题n到了十万量级就乖乖用辅助数组。常见问题与排查技巧实录4.1 超时的常见原因与排查方法笔试中遇到超时大多数时候不是常数项的问题而是复杂度的量级出了问题。我总结出三个最常见的超时原因每个都是亲身踩过的坑第一递归搜索没有记忆化。哪怕状态空间只重复两次指数级递归都会让你跑到绝望。自己排查时可以加一个计数器打印递归入口次数如果发现同一个状态被反复进入就要考虑加缓存或者改递推。第二字符串拼接过于频繁。Python里字符串是不可变对象每次用加号拼接都会生成新对象循环里做一万次拼接就崩了。这类场景一律改用列表收集再用join拼接。第三输入输出使用不当。笔试系统如果用input()一行一行读大数据量就会很慢。正确做法是一次性读取然后按行解析。Python有sys.stdin.read()可以整读配合split处理速度会快很多。4.2 边界条件遗漏的终极排查口诀关于边界条件我提供一个自己常用的排查口诀空、单、双、极、反。五个字分别代表五种必测情况空输入为空数组或空字符串时你的代码是否报错单输入只有一个元素时循环是否还会执行双输入只有两个元素时状态转移是否覆盖了所有情况极输入极大时是否会超时或溢出反输入逆序、乱序时算法是否还能正确处理每道题写完按照这五个字逐项自测一遍能挡掉至少百分之八十的隐藏bug。特别是动态规划的题n1和n2是最高频的出错点很多递推公式在n1时下标就会变成负数。4.3 编程语言层面的避坑指南除了算法本身一些语言层面的坑也很容易在笔试中浪费时间。我在Python笔试中遇到过的问题包括负数取模的规则和其他语言不一致列表的切片操作会生成新列表误以为原地操作会把内存翻倍pypy和cpython在递归深度上的表现不同递归超过一定层数可能会直接崩溃。针对这些我的建议是遇到负数取模先想清楚题目是只需要结果还是需要商如果只需要结果可以在计算时加上一个足够大的数确保非负。大循环体里尽量避免切片操作需要修改顺序时用索引交换。如果递归深度可能超过一千首先把递归改成循环实在改不了就把sys.setrecursionlimit设置到一个可靠值但也要意识到这会消耗更多内存。4.4 笔试现场的时间分配策略平时刷题可能有充足时间慢慢想但笔试现场最大的敌人是焦虑。我个人的分配策略是这样先花三分钟把所有题目都看一遍大概估计每道题的难度然后先把最拿手、最有把握的题做出来保证基本分数到手最后再啃难题。这个策略可能和很多人的习惯相反大多数人喜欢按顺序做。但我见过太多人卡在第一道题上四十分钟结果后面几道简单的题根本没时间写这才是最亏的。笔试是按通过用例给分的哪怕只通过部分测试点也比零分强。所以我的原则是先拿稳定分数再冲高分。还有一个小技巧写代码前先在注释里简单写下思路哪怕只是三四行。一方面能梳理逻辑另一方面万一代码没写完阅卷人也许还能看到思路给一点过程分。当然这取决于考试系统的评分方式但至少对你自己的思路整理是有帮助的。题目的延伸与一题多解的价值5.1 从一道题扩展到一类题搜狗这道矩阵路径最大值题本质上和很多经典题是同源的。比如最小路径和、不同路径、带障碍物的路径计数都是同一个模型下的变体。如果能把这道题的一维跳跃状态理解透那么遇到“最多能使用多少次特殊能力”的问题就可以自然推广到多维状态。我建议刷题不要满足于AC每做完一道题至少问自己三个问题如果数据范围扩大十倍我的解法还行不行如果限制条件增加一个状态怎么改如果要求输出路径而不是路径长度代码要加什么这三个问题想明白了一道题的价值能顶五道题。5.2 动态规划反向推导的训练方法最长有效括号这道题我觉得特别适合用来练习“从答案推状态”的能力。拿到问题先不要急着写代码先把最简单的情况在纸上展开比如s()、s)(、s()(())手工算出每个位置的dp值再回头看递推公式是否完美覆盖了例子中没有体现的情况。大家可能觉得这样很慢但实际训练一段时间后速度反而会提升。因为你在用“慢思考”建立直觉一旦直觉建立了以后看到类似题目就能快速判断状态怎么定。这比盲目刷三十道同类型题效果要好得多。5.3 双指针题的内存优化版本按奇偶排序这道题首尾双指针的解法大家都会写但那个解法不保证稳定性。如果在真实业务场景中需要保持相对顺序就必须用稳定方式处理。我遇到过的实际需求里保持相对顺序比“只分类”更重要因为用户往往希望看到在原有顺序基础上的过滤结果而不是打乱重排的结果。这就是笔试题目和工程实践的关联之处。面试官考一道看似简单的题背后可能隐藏着对数据一致性、稳定性的考察。如果你在写代码时能主动提到稳定性这一点会给面试官留下不错的印象。应试心态与长线准备建议6.1 不要迷信押题把基本功练扎实每年校招季都会有很多“押题班”“高频题清单”流传。我不否认刷高频题有用但搜狗这种老牌公司出题风格其实比较稳定它不会去追逐网上那些风口题而是考察你能否在有限时间内解决一个中等偏上的算法问题。所以我的建议是把精力从“追新题”转移到“吃透老题”。一份高质量的真题集比如这份搜狗2019秋招研究员试卷你刷三遍每一遍都能发现新的理解盲区。第一遍要求AC第二遍要求写出一题多解第三遍要求限时完成并分析每种解法的时间和空间复杂度。走到第三遍的时候这套题就真正变成你自己的东西了。6.2 记录错题本的方法我有一个坚持了很多年的习惯每做错一道题不是简单把正确答案抄在错题本上而是用三句话总结我为什么错了正确思路是我没想到的哪一步如果再遇到同类题我的触发词应该是什么。比如“一看到跳跃/特殊能力就用一维状态记录是否已使用”这样以后遇到类似题大脑会自动弹出提示。错题本不在于笔记本多漂亮也不在于题量多大而在于你每次打开它时能不能在十秒钟内回忆出那三句话。如果能做到你的复习效率会非常高。6.3 模拟笔试环境的重要性最后一条建议至少做三次完整的限时模拟使用和真实笔试相同的编辑器或在线平台关闭手机设定好倒计时严格按照考试节奏来。平时刷题是“启发式探索”可以慢慢想但笔试是“考场上交卷”你必须在一小时或一个半小时内完成整套题。很多平时能AC的题在时间压力下就是会写错下标这不是能力问题而是不熟悉考场节奏。我见过一个同学他把历年真题模拟了五遍每一遍都记录自己在哪一题上花了超预期的时间然后针对性地调整做题顺序。最终笔试成绩非常理想。这足以说明编程能力是一方面考试策略是另一方面两者需要同时训练。从我个人的体会来说搜狗这套题真正有价值的并不是“标准答案”而是每一道题在推导过程中强迫你建立的思维路径。如果你能把文章中这些题型的思路真正内化哪怕没有押中任何原题面对类似的题目时也会更有底气。技术圈有句话叫“见过足够多的题考场上就不会慌”我深以为然。希望大家都能在笔试中发挥出自己的真实水平。