每年秋天都是技术岗笔试扎堆的时候前几天还有朋友翻出牛客网收藏夹里那套“搜狗2016研发工程师编程题”问我放到现在还有没有刷的必要。我的观点很明确值得而且非常适合拿来做校招笔试的系统性热身。这套题的整体难度放在今天看并不夸张但覆盖了字符串、位运算、动态规划、TopK这几个研发岗笔试最常出现的算法方向风格也贴近真实招聘场景不会出偏题怪题。无论你正在准备秋招还是想系统补一补算法基础这套题都能当很不错的练手材料。下面我把流传版本里出现频率最高、最有代表性的几道题拿出来完整复盘考点、解法和考场上容易踩的坑。1. 搜狗2016研发工程师编程题整体画像与出题逻辑1.1 为什么这套题放到现在还有人翻出来刷很多后来准备校招的同学看到“2016”这个年份第一反应是“题库是不是已经过时了”。实际情况恰好相反我能翻到这套题就是因为它在牛客网的收藏夹里挂了很久每年秋招都有人重新拿出来刷。这是一个很有意思的信号如果一套题纯粹因为旧被淘汰不会到今天还有人点开。搜狗当年的业务重心在搜索、输入法、浏览器这几个方向研发工程师笔试的编程题风格也带着明显的“搜索公司气质”不搞冷门数据结构手写题很少考红黑树、跳表、平衡树这种偏竞赛的内容而是把注意力集中在数组、字符串、动态规划、位运算、排序上。这几个方向恰恰是研发岗日常开发里最常用的算法能力所以题目生命力很强。还有一点值得说的是这套题的难度梯度安排得比较合理。简单题大概十几分钟能写完中等题需要现场把状态转移或者边界条件想清楚难题则对思路和代码稳定性都有要求。这和当下绝大多数公司笔试的节奏很接近。刷这套题练出来的手感放到今天依然能用。1.2 拿到笔试题目前3分钟该想清楚什么很多人做编程题的习惯是读题之后立刻开写结果写到一半发现复杂度不达标或者边界条件漏了只能推倒重来。我见过太多这种情况也包括我自己当年踩过的坑。后来我养成了一个习惯拿到题目先不碰键盘花3分钟把三件事想清楚。第一看输入规模。题目里数组长度是10^3还是10^5字符串最大多长k的取值范围是多少这些直接决定算法复杂度能不能过。比如后面要复盘的最长回文子串如果长度上限是1000那么O(n^2)的中心扩展法完全没问题如果长度是10^5就必须上Manacher了。第二确认输出格式。有的题让你返回长度有的题让你返回子串本身有的题返回下标。底层算法一样但输出差一个字符就是零分。2016年这套题里就有一道题题目描述里写的是“返回最长回文子串”有人当成返回长度做写得很顺结果全错。第三提前列出边界情况。空数组、空字符串、单元素数组、全是重复元素、包含负数这些情况在写代码前先在草稿纸上列一遍。很多笔试翻车不是算法不会而是边界没处理好。后面每道题我都会把这部分单独拎出来说因为这才是真正决定分数的地方。2. 真题复盘最长回文子串中心扩展还是Manacher2.1 题目长什么样考点在哪里题目大概是这样的给定一个字符串s找到s中最长的回文子串。假设s的最大长度为1000。示例输入babad输出bab或者aba都行输入cbbd输出bb。这题是所有字符串算法里最经典的入门题之一。考点很清楚字符串遍历、回文判断、边界条件处理。为什么说它经典因为回文串本身有很好的对称结构最直观的暴力解法是枚举所有子串再逐个判断复杂度O(n^3)长度稍微大一点就超时。它考察的核心是你能不能利用回文的对称性把重复判断优化掉。搜狗这类搜索公司特别喜欢考字符串题因为字符串处理本来就是搜索、输入法、自然语言处理的底层基本功。一道回文题看起来简单但能把中心扩展、动态规划、Manacher三种解法讲清楚的人说明对字符串问题的理解确实到位。2.2 中心扩展考场上最稳的写法回文串的本质是以某个中心对称。这个中心可能是某一个字符比如aba的中心是b也可能是两个字符之间的空隙比如aa的中心在a和a中间。所以中心扩展的思路就是遍历字符串的每一个可能中心向左右两边同步扩展直到左右字符不一致记录当前中心能形成的最长回文长度。上面说的两种中心情况要分别处理对应奇回文和偶回文。代码实现起来很直接def longestPalindrome(s: str) - str: if not s or len(s) 1: return s start, end 0, 0 def expand_around_center(left: int, right: int) - int: while left 0 and right len(s) and s[left] s[right]: left - 1 right 1 return right - left - 1 for i in range(len(s)): len1 expand_around_center(i, i) # 奇数长度回文中心是单个字符 len2 expand_around_center(i, i 1) # 偶数长度回文中心是两个字符之间 cur_len max(len1, len2) if cur_len end - start 1: start i - (cur_len - 1) // 2 end i cur_len // 2 return s[start:end 1]时间复杂度O(n^2)空间复杂度O(1)。我重点说两个代码细节也是很多人写错的地方。第一个是长度转换成左右端点的公式。假设中心下标是i当前回文长度为L。如果L是奇数比如L5中心在i那么左端点是i-2右端点是i2如果L是偶数比如L4中心在i和i1之间先往左取2个字符左端点是i-1右端点是i2。统一写成start i - (L - 1) // 2、end i L // 2这个公式奇偶都适用。第二个是“扩展后停止”的位置。while循环结束时left和right已经指向不相等的位置实际回文区间是(left1, right-1)长度是right-left-1。这个长度值我见过很多人算错。2.3 动态规划和Manacher怎么选中心扩展虽然写起来简单但O(n^2)不是最优。面试官如果继续追问通常希望你能说出动态规划或者Manacher的思路。动态规划的想法是用dp[i][j]表示s[i:j1]是否回文。状态转移很清晰如果s[i] ! s[j]dp[i][j]一定是False如果s[i] s[j]且j - i 2说明是a或aa这种短串直接是True否则要看dp[i1][j-1]是不是True。这样做时间复杂度O(n^2)空间复杂度也是O(n^2)。代码逻辑比中心扩展绕一点笔试时如果时间紧张我不会优先写DP版本。Manacher算法把时间复杂度压到了O(n)是字符串回文题目的最优解。核心思想可以概括为两句第一在原字符串每个字符两侧插入特殊分隔符比如#让所有回文串都变成奇数长度统一处理奇偶情况第二维护一个当前已知的最右回文边界R和对应中心C当遍历到边界内的位置i时可以借助对称点算出初始回文半径减少重复扩展。笔试中如果不是对Manacher特别熟不建议现场写因为边界计算很容易出错。面试时能说出“插入分隔符统一奇偶”和“利用最右边界减少匹配”这两个关键词其实就已经能说明你了解了。2.4 关于这道题我踩过的三个坑第一个坑是只写奇数中心。我第一次做这题的时候循环里只调用了expand_around_center(i, i)测试aba能过一换成cbbd就输出c。原因就是偶数回文的中心不在字符上必须用(i, i1)再扩一次。这个坑特别隐蔽因为很多示例都是奇数回文。第二个坑是start/end公式记反。