每年秋招季牛客上关于搜狗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的长度是np的长度是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(mn-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 边界条件和输出路径的扩展如果题目只是求最大得分上面这套代码就够了。但如果要求输出最大得分对应的路径就需要额外记录每个格子是从哪个方向来的。我的做法是再维护一个二维数组prepre[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 个很简单。但数据流长度未知而且不能回放这就是蓄水池抽样要解决的问题。k1 的版本最容易理解维护一个变量res作为当前选中的元素遍历每个元素如果是第 i 个从1开始计数就以 1/i 的概率用这个元素替换res。遍历结束后res就是以等概率从所有元素中选出的一个。为什么这样是对的可以用乘法概率来证明。第 i 个元素最终被选中需要它在第 i 次时被选中并且后面所有元素都没有替换它。第 i 次选中的概率是 1/i之后第 i1 个元素替换它的概率是 1/(i1)不替换概率是 i/(i1)每个后续元素的不替换概率依次是 i/(i1), (i1)/(i2), ..., (n-1)/n。把这些连乘起来正好得到 1/n。所以每个元素最终被选中的概率相等。代码也非常短import random def sample_one(stream): res None for i, item in enumerate(stream, start1): if random.randint(1, i) 1: res item return resk 个样本的版本稍微复杂一點先把前 k 个元素放进一个大小为 k 的数组从第 k1 个元素开始以 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)因为 k100 是常数所以整体可以认为是线性的。真正的考点反而是思路的完整性有没有提到哈希分片、有没有提到堆、有没有解释为什么小顶堆。如果笔试要求写代码代码量也很小。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那两段代码每次看都能提醒自己基础永远比技巧值钱。