每年秋招季，牛客上关于搜狗2019秋招研究员试卷第二场的讨论帖都会被翻出来，一批人回忆题面，一批人贴代码，还有一批人在评论区争论某道题的复杂度到底是多少。这套题在当时的评价是“不难，但很搜狗”——题型覆盖了字符串、递推、概率统计这几个和搜索、推荐强相关的方向，不像大厂那样动辄上硬核图论，但每道题都足够检验候选人能不能把一道常规题写对、写稳、写干净。
网上流传的版本大多是回忆版，原题措辞不一定对得上，但这不影响我们复盘。对准备算法岗笔试的人来说，这套题更值得关注的不是具体题目，而是背后的题型分布、答题节奏和容易踩坑的细节。这篇文章我把几个典型的题目方向展开讲一遍，顺便聊聊我当时在考场上的思考和交卷后的复盘。
1. 开考先做什么：第二场试卷的题型地图与答题顺序
1.1 为什么很多人倒在第一道题上
我见过太多人一进笔试系统，看到第一道题好像很简单，就直接开始敲键盘，结果写完提交，发现各种边界不过，又回头改，一来一回耗掉半小时，后面两道题只能草草收场。这个问题在搜狗的试卷上尤其明显，因为它的编程题通常不是按难度严格递增排列的，第一道题看着是字符串处理，可能中间藏着几个很刁钻的边界条件。
所以我现在的习惯是：开考后先花5分钟把整张卷子所有编程题都读一遍，哪怕不细想解法，也要知道题目在问什么、数据范围大概是什么量级、自己心里有没有底。这一步花的时间很少，但能极大避免“在一道题上浪费太久”的悲剧。
1.2 我在试卷上画出的三档清单
读完题之后，我会在心里把所有编程题分成三档：
- 送分题：5分钟内能想到暴力解法，边界条件也大概能列出来的题。
- 中等题：有思路，但需要花时间推导状态转移或者优化复杂度的题。
- 压轴题：一时半会儿没有完整思路，只能想到个大概方向的题。
对搜狗研究员这类的算法岗笔试，编程题常见的题型组合是：一道字符串或模拟题、一道递推动态规划题、一道概率统计或海量数据题。第二场的题量和第一场差不多，但难度分布往往更平均，也就是说不会有一道题是完全做不出来的“劝退题”，但每一道题想拿满分也没那么容易。
我当时的策略很朴素：先把送分题的稳定分数拿到手，再做中等题，压轴题如果时间不够，就写暴力和部分思路，能拿多少算多少。笔试平台的判题逻辑通常包含部分分，哪怕只是在大数据上超时，小数据用例跑对了也能拿到一些分，总比空着强。
1.3 提前背下来的输入输出模板
还有一个容易被忽略的点是输入输出。很多候选人平时在本地IDE里写代码，用惯了补全和格式化，一上笔试系统连读入都写得磕磕绊绊。我的建议是提前准备一套自己最顺手的模板，尤其是高频的几种写法。
比如Python读入一大串数字，用sys.stdin.read()一次读完再split()，比一行行input()快得多；C++ 开ios::sync_with_stdio(false)关掉同步；Java 用BufferedReader而不是Scanner。这些不是技巧，是基本功。真正在考场上，省下来的每一分钟都可能决定你能不能把最后一道题的思路写完。
2. 字符串处理题：搜索引擎笔试题里的隐形送分题
2.1 一道典型的异位词子串题是怎么问的
搜狗做搜索起家，字符串处理在它的笔试里出现频率很高。那套试卷第二场里就有一道题，按我的记忆整理出来大概是这个意思：给定一个字符串s和一个模式串p，要求返回s中所有与p构成字母异位词的连续子串的起始下标。所谓字母异位词，就是字母组成相同但排列顺序不同的词，比如abc和cba就是异位词。
这类题和搜索引擎里的查询改写、同义词匹配有很强的关联：用户搜best restaurants，系统可能想匹配包含restaurant best的文档，两个词只是顺序反了，语义上却一致。所以搜索公司考这种题一点都不奇怪。
2.2 暴力解法先跑通，再推滑动窗口
我看这道题的第一反应是先写暴力：枚举所有长度等于len(p)的子串，把子串和模式串分别排序后比较。如果字符相同，排序后的结果一定相同。这个方法逻辑完全正确，但复杂度有问题。假设s的长度是n，p的长度是m，枚举所有子串是 O(n)，每次排序是 O(m log m)，总复杂度 O(n m log m)。当n和m都到 10^5 级别时，这个复杂度完全不可接受。
优化的核心思路是滑动窗口加计数。因为字母异位词只关心字符出现的次数，不关心顺序，所以我们只要维护一个长度为m的窗口，统计窗口里各个字符的出现次数，然后和模式串的字符计数比较即可。
窗口每次向右滑动一格，左边出去一个字符，右边进来一个字符，更新两个位置的计数，再比较。这样整个窗口扫一遍，复杂度是 O(n)，代价只是额外的 O(1) 空间，因为字母表长度固定。
下面是一个Python的实现，我通常用长度为26的数组来计数，题目如果明确说明只含小写字母，这是最快的方式：
def find_anagrams(s: str, p: str): n, m = len(s), len(p) if n < m: return [] target = [0] * 26 window = [0] * 26 for ch in p: target[ord(ch) - 97] += 1 for ch in s[:m]: window[ord(ch) - 97] += 1 def is_match(): for i in range(26): if target[i] != window[i]: return False return True res = [] for i in range(n - m + 1): if is_match(): res.append(i) if i + m < n: window[ord(s[i]) - 97] -= 1 window[ord(s[i + m]) - 97] += 1 return res这里每次is_match比较26次，所以整体复杂度是 O(26n)，在实际的1秒时限下足够通过。如果担心常数问题，可以维护一个diff变量记录当前窗口和模式串相差的字符种类数，每次滑动只更新diff，这样就能把比较从 O(26) 降到 O(1)。不过在笔试中，O(26n) 通常已经稳过，我建议优先保证代码清晰。
2.3 窗口计数更新的几个易错点
这个写法看起来简单，但有几个细节特别容易错。
第一个是滑动窗口的更新时机。我在代码里用的是先判断再更新，也就是在判断完当前位置后，如果还能往右滑，才做窗口更新。如果把更新放在判断之前，或者边界条件写错，就会导致漏掉第一个窗口或者数组越界。
第二个是字符范围。26个字母的假设只在题目明确说明“只含小写字母”时成立。如果题目说大小写混合，数组长度就要扩到52或者128，更好的做法是用字典Counter。我见过不少人在这个点上翻车，题目明明给了s和p只有小写字母，但没注意p可能为空串。
第三个是空串问题。如果p是空串，n < m的判断不会触发（因为 m 为 0），然后窗口初始化只加了s[:0]，也就是什么都没加，is_match会一直返回 True，结果是把所有下标都当成答案。这显然是错的。所以写代码前第一件事，就是和出题人确认或者在代码里显式处理p为空串的情况。
2.4 如果字符集不是26个小写字母怎么办
遇到字符集不固定或者包含中文的情况，用数组计数就不合适了，这时候我建议直接用collections.Counter。窗口进入和出去时对对应字符的计数做增减，然后和target直接比较。Python 的Counter重载了相等比较，两个Counter相等当且仅当所有键值对相同。
不过要注意，Counter的相等比较在键很多时也会有一些开销，但比起排序已经好太多。整体思路和滑动窗口是一样的，只是数据结构换一下。这种“换数据结构不变思路”的能力，在笔试里比背模板更重要，因为出题人可能会把题目包装成各种奇怪的场景，但底层逻辑往往就是那些经典套路。
3. 递推类编程题：从记忆化到一维DP的推导全过程
3.1 网格路径题的状态定义
第二场试卷里有一道很经典的递推题，大体是一个二维网格，每个格子里有一个非负分数，从左上角走到右下角，每次只能向右走或者向下走，求路径上经过格子的分数之和最大值。
很多人的第一反应是用 DFS。确实可以，但从左上角到右下角，路径数量是组合数 C(m+n-2, m-1)，当网格达到 100×100 时这个数已经大到无法枚举。所以必须引入动态规划。
状态定义很简单：dp[i][j]表示从左上角走到格子(i, j)能获得的最大得分。因为只能向右或向下，所以到达(i, j)的上一步只能来自(i-1, j)或(i, j-1)，转移方程是：
dp[i][j] = grid[i][j] + max(dp[i-1][j], dp[i][j-1])这个方程成立的前提是：路径不允许走回头路，所以不存在环，每一步都只依赖已经算过的子问题。如果题目改成可以上下左右走，那就不能这么简单地用DP了，因为可能存在环，需要用 Dijkstra 之类的最短路径算法来处理。出题人一般不会在常规题里这么坑人，但要在读题时留意方向限制。
3.2 一维数组为什么能省掉一个维度
二维DP写起来最直观，定义dp = [[0] * n for _ in range(m)]，两层循环填表，最后返回dp[m-1][n-1]。但有一个问题：当矩阵很大时，二维数组占用的空间是 O(mn)。如果m和n都到 10^5，内存直接爆掉。
这时候需要做空间优化。观察转移方程可以发现，dp[i][j]只依赖当前行的左边一格(i, j-1)和上一行的同一列(i-1, j)，不依赖更早的行。也就是说，我们只需要保留上一行的数据，而不需要存储所有行。
于是可以把二维数组压缩成一维数组dp[j]。更新之前，dp[j]保存的是上一行第j列的最优值；更新之后，它变成当前行第j列的最优值。这里的核心是更新顺序：必须从左到右更新。因为dp[j]需要用到dp[j-1]，而dp[j-1]在当前行已经更新过了，正好是(i, j-1)的最优值；同时dp[j]还没被覆盖，里面还是上一行(i-1, j)的值。如果从右往左更新，dp[j-1]就还是上一行的旧值，结果必然错误。
这个一维滚动数组的写法是递推题的高频优化点，值得背下来：
def max_score(grid): m, n = len(grid), len(grid[0]) dp = [0] * n for i in range(m): for j in range(n): if i == 0 and j == 0: dp[j] = grid[0][0] elif i == 0: dp[j] = dp[j - 1] + grid[i][j] elif j == 0: dp[j] = dp[j] + grid[i][j] else: dp[j] = grid[i][j] + max(dp[j], dp[j - 1]) return dp[n - 1]第一行只能往右走，所以dp[j] = dp[j-1] + grid[i][j]；第一列只能往下走，所以dp[j] = dp[j] + grid[i][j]，因为 dp[j] 里存的还是上一行的值。这个边界处理很多人会写错，尤其是第一列，容易写成dp[j-1]这种不存在的引用。
3.3 边界条件和输出路径的扩展
如果题目只是求最大得分，上面这套代码就够了。但如果要求输出最大得分对应的路径，就需要额外记录每个格子是从哪个方向来的。我的做法是再维护一个二维数组pre，pre[i][j]记 0 表示来自上方，记 1 表示来自左方。填完dp之后，从终点倒推回起点，再把路径反转一下。
还有一种常见变体是网格里包含障碍物，比如某些格子不能走。处理方式很简单：转移时跳过障碍物格子，或者把障碍物格子的dp值设为一个极小值（比如负无穷），这样它不可能成为后续格子的来源。但要注意，如果用负无穷，要防止整型溢出，建议用float('-inf')或者一个足够小的负数，具体看题目给的分数范围。
我在复盘这套题时最大的感受是：递推类题目真正的失分点不是在你推导不出转移方程，而是在初始化、边界处理和一维优化时写错。很多候选人脑子里知道二维怎么解，但为了显得高级直接写一维，反而在边界上栽跟头。如果时间紧张，我建议先写二维版本，确保正确性，再花两分钟优化成一维。两道题都拿到的分数，比一道题闷头优化拿到的最优解分数高得多。
3.4 递推题的失分点：不是公式，是初始化
再展开说说初始化。dp[0][0]到底等于grid[0][0]还是 0，取决于题目定义的路径得分是否包含起点。大部分题目是包含的，但也有些题目把起点当成“位置”，不计分。这种出题细节会直接影响答案，如果理解错了，代码写对也拿不到分。
我的习惯是读完题先不要急着写代码，在草稿纸上写两个极端例子：一个 1×1 的网格，一个 1×n 的网格，一个 m×1 的网格。这三个例子能检验绝大多数初始化错误。就像写单元测试一样，先想清楚最小输入的行为，再动手。
4. 概率统计与海量数据：研究员岗位才会出现的差异化题型
4.1 蓄水池抽样：等概率抽样一个未知长流
搜索公司每天产生的日志量是百亿级别的，很多时候我们无法把全部数据载入内存，但又想从中随机抽取一部分作为样本，用来做模型训练或者数据分析。这个场景对应着笔试里的一道经典题：未知长度的数据流，要求只遍历一次，等概率随机选出 k 个元素。
如果数据长度已知，随机抽 k 个很简单。但数据流长度未知，而且不能回放，这就是蓄水池抽样要解决的问题。k=1 的版本最容易理解：维护一个变量res作为当前选中的元素，遍历每个元素，如果是第 i 个（从1开始计数），就以 1/i 的概率用这个元素替换res。遍历结束后，res就是以等概率从所有元素中选出的一个。
为什么这样是对的？可以用乘法概率来证明。第 i 个元素最终被选中，需要它在第 i 次时被选中，并且后面所有元素都没有替换它。第 i 次选中的概率是 1/i，之后第 i+1 个元素替换它的概率是 1/(i+1)，不替换概率是 i/(i+1)，每个后续元素的不替换概率依次是 i/(i+1), (i+1)/(i+2), ..., (n-1)/n。把这些连乘起来正好得到 1/n。所以每个元素最终被选中的概率相等。
代码也非常短：
import random def sample_one(stream): res = None for i, item in enumerate(stream, start=1): if random.randint(1, i) == 1: res = item return resk 个样本的版本稍微复杂一點：先把前 k 个元素放进一个大小为 k 的数组，从第 k+1 个元素开始，以 k/i 的概率决定是否替换数组中的某一个元素，替换时在数组内等概率选一个位置。最终的结论是数组中每个元素留下的概率都是 k/n。这个结论在笔试中可以直接用，但建议把推导过程写一遍，因为面试官很可能会追问。
在搜狗这种场景下，蓄水池抽样可以用于从搜索日志中均匀采样，做后续的点击率分析或者用户行为研究。考这道题不是为难人，而是看候选人有没有海量数据的直觉。
4.2 海量URL求TopK：哈希分片加小顶堆
另一道高频题是：给定 100 亿个 URL，求出现次数最多的前 100 个。URL 总量远超内存，不能一次性加载，所以需要分而治之。
第一步是对 URL 做哈希分片。比如hash(url) % 1000，把 URL 分散到 1000 个小文件中。同一个 URL 的哈希值一定相同，所以它只会出现在同一个小文件里，这样每个小文件的规模就小到可以装进内存。第二步是对每个小文件单独做词频统计，用哈希表计数，然后取每个文件里的 Top 100。第三步是归并，把所有小文件的 Top 100 放到一起，再取一个全局 Top 100。
第三步怎么取？这里有个容易搞反的点：求出现次数最大的 k 个，要用小顶堆，而不是大顶堆。小顶堆的堆顶是整个堆里最小的元素，每来一个新元素，如果它比堆顶大，就替换堆顶并调整堆；这样遍历完后，堆里留下的就是最大的 k 个元素。如果错用大顶堆，每次把最大的顶上去，堆里反而存不下 k 个元素。
这个题的复杂度主要是哈希分片的 O(n) 和每个文件内的统计，堆的调整是 O(n log 100)，因为 k=100 是常数，所以整体可以认为是线性的。真正的考点反而是思路的完整性：有没有提到哈希分片、有没有提到堆、有没有解释为什么小顶堆。如果笔试要求写代码，代码量也很小。
4.3 这类题在笔试里的正确打开方式
概率统计和海量数据题和前面的字符串、DP 不太一样，它往往不需要写出特别复杂的代码，而是要你把思路讲清楚，把关键步骤和复杂度分析写明白。很多候选人看到这种题就慌了，觉得自己没准备过海量数据，其实这类题套路很固定，蓄水池抽样、哈希分片、位图、布隆过滤器、堆排序，翻来覆去就是这几板斧。
我在考场上做这类题的经验是：先写结论，再写步骤，最后写复杂度。比如蓄水池抽样，先写“维护大小为k的池，第i个元素以k/i概率替换池中元素”，然后写实现，再附上概率证明。这样即使代码有个别小错误，阅卷人也知道你是真的懂。
5. 交卷后的复盘：三个差点翻车的细节
5.1 空串和大小写：字符串题最常见的隐形杀手
考完复盘时我发现，最让我后怕的不是最后一道压轴题，反而是第一道字符串题。我第一版代码根本没考虑模式串为空的情况，如果不是提交前突然意识到find_anagrams在空串时会误判，那道题大概率就拿不到满分了。
后来我总结出一个习惯：任何字符串题，动笔前先在草稿纸上写下几个边界用例。空串、单字符、全相同字符、包含大写字母、包含数字或空格，每个都要想清楚程序应该输出什么。这比多背几道算法模板有用得多。笔试里的用例不会那么贴心，出题人最喜欢在边界上设置隐藏坑。
5.2 先写暴力拿分，再谈优化
另一个教训是不要一上来就写最优解。我当年做递推题时，明明二维DP已经想得很清楚了，硬要直接写一维滚动数组，结果边界条件写错，调试花了十几分钟。后来我明白了：在一个时间有限的笔试环境里，最快的路径往往是先写一版自己最有把握的解法，确保它能通过一部分用例，再在它基础上做优化。哪怕最后优化没写完，原来的暴力或者次优解已经为你保住了基础分。
尤其是DP题，二维版和暴力DFS往往已经能通过小规模数据。先把这些分拿住，再用剩余的时间优化，而不是一上来就挑战最高难度。
5.3 用在线评测平台练手的真实价值
最后一件让我反思的事是操作熟练度。平时我在本地IDE写代码，有代码补全、有语法高亮，甚至报错都提示得清清楚楚。但笔试系统的网页编辑器非常简陋，没有自动补全，连括号配对都要自己注意。我记得当时连 Python 的ord和chr都犹豫了一下，这种平时根本不会卡壳的小事在考场上就是浪费时间。
我的建议是，在秋招开始前，至少用牛客、赛码这种在线笔试平台练五套真题，全程模拟笔试环境，不开IDE，不查文档，计时完成。这个过程不是为了学新算法，而是为了让你的手和脑适应那种“没有任何辅助工具”的状态，把常用模板练成肌肉记忆。
不过说实话，这套题给我留下的最深的印象不是某个具体算法，而是它对基本功的重视。你不需要会什么冷门的黑科技，但必须把滑动窗口、DP、蓄水池抽样这些常规套路掌握到“条件反射”的程度。搜狗这类公司真正想考察的，就是你能不能把一个看似普通的题目写对、写稳、写干净。这套题过去几年了，我偶尔还会把其中的模板翻出来看一眼，尤其是滑动窗口和一维DP那两段代码，每次看都能提醒自己：基础永远比技巧值钱。
