2019年秋天我坐在电脑前参加搜狗秋招研究员岗的第一场笔试。旁边放着水和准考证心态还算稳结果打开编程题页面第一道题就让我意识到搜狗的编程题跟普通开发岗完全不同它不是在考你会不会写代码而是在考你能不能把一个模糊的搜索场景问题翻译成清晰的算法模型再写出经得起边界测试的代码。现在回过头看那套题印象最深的是它把字符串、动态规划、图论、概率统计全部揉进了搜索引擎和自然语言处理的业务背景里。很多题表面上是“编程题”实际上是在模拟搜狗日常业务里遇到的真实问题。这篇文章我按当时的记忆把第一场里的部分题目整理成合集每道题都会给出题意、输入输出示例、完整可跑的Python3解法以及我在现场踩过的坑。不管你是准备投搜狗算法岗还是在刷大厂研究员方向的笔试这套题都值得认真过一遍。1. 搜狗这张试卷的整体画像题型结构、时间线、考察重点1.1 从“研究员岗”三个字读懂出题逻辑搜狗的研究员岗和普通后端开发岗笔试编程题的差异非常大。后端岗的题更像“力扣原题抽查”考的是你刷题量够不够。研究员岗的题则是“带着业务问算法”每一道题都在模拟搜索、推荐、NLP环节里的一个真实子问题。比如字符串题它不会直接考“给你两个字符串求编辑距离”而是会包装成“搜索引擎里用户输入的查询词和索引词之间最少需要多少次字符操作才能匹配”。图论题也不会直接说“给你一张有向图求最短路径”而是会说“两个同义词之间是否能通过一组同义词关系转换过去最短需要几步”。所以备考这个岗位光刷题不够你得学会把题目“外壳”剥掉看到里面那层数据结构。第一场编程题一共6道总时间120分钟。我记得大致分值是前两道每题20分中间三道每题15分最后一道30分。这个分值分布本身就传达了一个信号压轴题不是给你“试水”的而是用来区分候选人层次的。我在考场上给自己定的策略是先保证前面拿满再说后面的大题事后证明这个策略是对的。1.2 第一场的题目分布与阅卷侧重点从题目分布看字符串类2道动态规划2道图论1道概率统计1道。这个比例很“搜狗”因为搜狗的核心业务是搜索和输入法字符串处理本来就是基本功而研究员岗做排序、推荐、广告系统时动态规划和高阶概率统计又是绕不开的底层工具。阅卷侧重点也有迹可循。搜狗的笔试是机试自动判分但判的不是“压测用例全对”才给分而是按通过的测试用例比例给分。也就是说如果你暴力解法能过30%的用例就能拿到30%的分数而不是像某些大厂一样只有AC和零分两种结果。这一点非常关键意味着你的代码哪怕不完美只要思路对、能处理一部分边界也能拿分。建议不要因为一道题想不出最优解就直接放弃先把暴力和半优化的方案写上去能捞一分是一分。2. 字符串题看似考API实际全是边界2.1 “最少移动次数”那题先找最长可保留前缀第一道字符串题是这样的给定两个等长的字符串s和t每次操作可以把s中的任意一个字符移动到字符串末尾问最少操作多少次可以让s变成t。这题我一开始想复杂了以为需要用动态规划记录每个字符移动之后的位置。后来冷静下来发现它其实等价于一个贪心问题要让移动次数最少就等同于让“不用移动的字符”尽可能多。而这些不用移动的字符在s里的相对顺序必须和在t里的出现顺序完全一致而且它们在t里必须是一段连续的前缀。为什么是连续前缀而不是任意子序列因为每次操作只能把字符移到末尾一旦你移走某个字符它后面所有没被移动的字符的相对位置是保住的但你不可能让t中排在后面的字符“越过”前面已有的字符。所以只有t的某个前缀能保留下来。举个例子s “abcdef”t “abcfed”最多能保留的是t的前缀“abcf”对应s里的“abcf”因为它们的顺序在s里一致所以要移动的是“de”两个字符。代码实现就是逐个字符匹配找到t中能作为s子序列出现的最长前缀长度。def min_moves(s: str, t: str) - int: n len(t) j 0 # 用s去匹配t的前缀找到最长可保留前缀长度 for ch in s: if j n and ch t[j]: j 1 return n - j这里的核心是理解为什么匹配到最长前缀后剩余字符移动一定可以到位。因为s中那些“没被匹配”的字符可以按照t中从j位置往后的顺序逐个移动到末尾最终拼成t。这道题实测下来最容易踩的坑是有人贪心反向匹配从后往前找最长后缀但注意操作是把字符移到末尾不是移到开头所以只能是前缀不能是后缀。2.2 带通配符的模式匹配双指针不是唯一解第二道字符串题是给一个文本串text和一个模式串patternpattern里包含两个通配符“?”匹配任意单个字符“*”匹配任意长度的任意字符包括空串问文本串中第一个匹配的位置。如果没有匹配返回-1。这题如果只是判断整体是否匹配标准解法是动态规划但题目要的是“第一个匹配位置”所以整体动态规划会超时。现场我采用的贪心双指针是经典解法两个指针i指向textj指向pattern再用star记录遇到“”时text的位置match记录“”匹配结束之后text需要从哪个位置继续尝试。def first_match(text: str, pattern: str) - int: # 我们按字符逐个匹配找第一个完整匹配的起点 n, m len(text), len(pattern) # 为了找第一个匹配位置这里先尝试从每个起点匹配复杂度O(n*m) def match_from(start: int) - bool: i, j start, 0 star -1 match_pos start while i n: if j m and pattern[j] *: star j match_pos i j 1 elif j m and (pattern[j] ? or pattern[j] text[i]): i 1 j 1 elif star ! -1: j star 1 match_pos 1 i match_pos else: return False while j m and pattern[j] *: j 1 return j m for start in range(n 1): if match_from(start): return start return -1注意这里的实现我为了讲清楚“找位置”的逻辑采用了从每个起点尝试匹配的方式复杂度是O(n²m)考试时用例不大可以过。如果是追求性能应该做一次线性匹配记录第一次可能匹配的起点。不过说实话这种题在考场上最重要的不是最优复杂度而是先保证逻辑正确。2.3 字符串题的三个必查边界字符串类题是笔试最容易丢分的板块因为边界情况太多了。综合这两道题我总结出三个必查边界空串s或t为空时返回值是不是符合预期。比如第一题如果s和t都为空答案应该是0而不是报错。全通配符pattern全是“*”时结果一定是0第一个位置就能匹配很多人会在这一步忘记处理。字符重复s里有很多重复字符时贪心匹配是否仍然正确比如s“aaaa”t“aa”答案应该是2匹配逻辑要能正确算出前缀长度。这些边界在本地跑的时候可能觉得无所谓但线上判题会有专门的边界用例一旦没处理就是整道题零分。我的习惯是写完代码先自己在脑内跑三个特殊输入再提交。3. 动态规划状态设计决定你能走多远3.1 多一个“空窗期”的股票买卖第三题是一道买卖股票的变体给定一个数组表示连续n天的股价每天只能选择买入或卖出或持有而且卖出之后第二天必须休息一天冷静期问最大收益是多少。这就是带冷却期的股票买卖问题。现场第一反应是状态机动态规划。相比普通股票买卖只有“持有/不持有”两个状态多了冷却期之后不持有也要分成“卖出后第二天不能买”和“可以买”两种状态。状态定义dp[i][0]第i天结束时持有股票的最大收益dp[i][1]第i天结束时不持有股票且处于冷静期的最大收益dp[i][2]第i天结束时不持有股票且不在冷静期的最大收益def max_profit_with_cooldown(prices): n len(prices) if n 2: return 0 dp [[0, 0, 0] for _ in range(n)] dp[0][0] -prices[0] for i in range(1, n): # 今天持有要么昨天持有今天不动要么昨天不在冷静期今天买入 dp[i][0] max(dp[i-1][0], dp[i-1][2] - prices[i]) # 今天卖出后进入冷静期 dp[i][1] dp[i-1][0] prices[i] # 今天不在冷静期要么昨天就是不在冷静期要么昨天刚卖完今天冷静期结束 dp[i][2] max(dp[i-1][2], dp[i-1][1]) return max(dp[n-1][1], dp[n-1][2])这道题给我最大的启发是状态机DP的题目关键是把“业务的限制”翻译成“状态的转移限制”。冷静期这个条件听起来复杂但一旦定义好三个状态转移方程其实非常自然。考试时如果时间紧可以先画状态转移图再写代码不要一上来就硬套dp数组。3.2 最大子段和最小化先怀疑二分答案第四题给了一个数组要求把它分成连续的k段使得所有段的和的最大值最小输出这个最小值。典型的最大值最小化问题标准解法是二分答案加贪心检查。当时我脑子里闪过的第一个解法是动态规划dp[i][j]表示前i个元素分成j段的最小最大值复杂度O(n²k)n给到10^5的话肯定超时。后来意识到这题“最大值最小”的表述几乎就是在暗示二分答案。def split_array(nums, k): def can_split(limit): cnt 1 cur 0 for x in nums: if cur x limit: cnt 1 cur x else: cur x return cnt k left, right max(nums), sum(nums) while left right: mid (left right) // 2 if can_split(mid): right mid else: left mid 1 return left检查函数里注意一个细节每个元素本身就是一个段的和下限所以二分左边界不是0而是数组中的最大值。这个细节不处理遇到“每个数字都很大”的用例会死循环或者答案错误。3.3 动规题现场提速的两个技巧想给还在刷题的同学两个实战技巧先确认数据范围再决定解法。n小于1000可以考虑O(n²)的DPn大于10^5基本要和二分答案、贪心、单调队列这类优化思路挂钩。数据范围就是出题人给你的解法提示。状态定义里如果出现“最多”“最少”“最小化最大值”这类词优先怀疑二分。尤其是“最小化最大值”和“最大化最小值”几乎是二分答案的专属信号。4. 图论题研究员岗更爱考场景化图问题4.1 同义词集团并查集先做路径压缩第五题是典型的并查集应用。题目大意是给定M组同义词关系比如(A, B)、(B, C)那么A和C也互为同义词。问这组关系把单词划分成了几个等价类。这题考的就是并查集没有太多花哨的地方但有一个小陷阱单词不是整数是字符串。处理办法是先用字典把字符串映射成整数编号再做并查集。class UnionFind: def __init__(self, n): self.parent list(range(n)) self.rank [0] * n def find(self, x): while self.parent[x] ! x: self.parent[x] self.parent[self.parent[x]] x self.parent[x] return x def union(self, x, y): rx, ry self.find(x), self.find(y) if rx ry: return if self.rank[rx] self.rank[ry]: self.parent[rx] ry elif self.rank[rx] self.rank[ry]: self.parent[ry] rx else: self.parent[ry] rx self.rank[rx] 1 def synonym_groups(pairs): words {} index 0 uf None for a, b in pairs: if a not in words: words[a] index index 1 if b not in words: words[b] index index 1 if uf is None: uf UnionFind(index) uf.union(words[a], words[b]) # 统计根的数量 roots set() for i in range(index): roots.add(uf.find(i)) return len(roots)并查集如果只是普通的向上找父节点最坏情况下会退化成链路径压缩和按秩合并这两个优化建议都加上。笔试时不用写得太复杂但路径压缩一定要写否则大数据用例会超时。这题给我的教训是场景化的图论题第一步永远是“把业务实体映射成图的顶点”。4.2 同义词转换的最短路径BFS模板第六题是压轴大题的铺垫部分但单独拿出来也是一道完整的题给定一个单词字典每次可以改变单词中的一个字母问从单词start变成单词end最少需要多少步。这就是典型的单词接龙问题用BFS求无权图最短路。BFS的标准模板其实很固定队列、访问标记、逐层扩展。我考场上遇到的主要问题是如何快速生成“相邻单词”。最暴力的做法是遍历字典里每个单词比较是否只差一个字母复杂度O(N²L)N是字典大小L是单词长度。更好的做法是对于当前单词把每个位置分别替换成26个字母再看是否在字典集合里复杂度O(26L)。两边的字典都小可以用前者字典大就用后者。from collections import deque def ladder_length(start, end, word_list): word_set set(word_list) if end not in word_set: return 0 q deque([(start, 1)]) visited {start} letters abcdefghijklmnopqrstuvwxyz while q: word, dist q.popleft() if word end: return dist for i in range(len(word)): left, right word[:i], word[i1:] for ch in letters: nxt left ch right if nxt in word_set and nxt not in visited: visited.add(nxt) q.append((nxt, dist 1)) return 0这里有一个非常容易错的地方visited集合必须在入队时标记而不是出队时标记。如果把visited标记放在出队时同一个节点可能被多个方向加入队列导致重复扩展严重时会超时。这是个很经典的BFS优化细节。4.3 图论题控制代码量的三个习惯搜狗这场笔试的图论题代码量不大但很考验熟练度。我的建议是邻接表用defaultdict(list)而不是自己维护二维数组省代码还安全。成对输入先建图再写算法不要边读边算逻辑会乱。BFS的visited标记时机、DFS的递归深度限制这两个点写之前就确认清楚。5. 概率统计题这部分最容易被忽视5.1 二叉树分流问题期望别算错单位最后一道压轴题考的是概率。题意大概是有一个满二叉树根节点有一个单位的水量每到一个节点水会以1/2概率流向左孩子1/2概率流向右孩子问所有叶子节点接收水量的期望分布。这道题表面上是一个二叉树树的遍历但核心考的是随机过程的期望计算。每个叶子节点接收水量的期望是(1/2)^depth其中depth是从根到该叶子的深度。因为每经过一条边水量概率乘1/2而路径的选择互不影响。所以解法就是遍历二叉树每个叶子节点累加期望值class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right def expected_water(root): res [] def dfs(node, prob): if not node: return if not node.left and not node.right: res.append(prob) return if node.left: dfs(node.left, prob / 2) if node.right: dfs(node.right, prob / 2) dfs(root, 1.0) return res这题容易出错的点是题目问的是“期望分布”有人会误以为要算每个节点收到水量的概率分布把简单的期望当成了复杂的联合分布。考场上如果你觉得一道概率题要算很久先停下来想想是不是出题人故意用复杂表述包装了一个简单问题。5.2 抛硬币胜率别傻傻列无穷级数还有一道概率题印象也很深两个人轮流抛一枚均匀硬币先抛出正面的人获胜问先手胜率。这题看起来像是无穷级数求和但可以用递推关系快速求解。设先手胜率为P。先手第一轮抛硬币如果抛出正面直接获胜概率1/2如果抛出反面那么局面变成后手先抛此时后手胜率为P所以先手胜率为1-P。于是有 P 1/2 1/2 × (1 - P) 解得 P 2/3。这种“自己调用自己”的概率递推法比分段列无穷级数要快得多也不容易算错。搜狗这类人工智能岗位笔试特别喜欢考这种“看似复杂、本质上就是小学奥数”的概率题因为它在考查你有没有把问题抽象成递归模型的能力。5.3 概率题的常见陷阱概率题拿分不容易我总结出三个常见的陷阱事件是否独立。很多题里两个事件明显不独立强行相乘概率就错了。先手/后手的对称性。遇到二人轮流操作问题试着找“双方对称”的递推关系能省很多时间。期望的单位。有的题目期望答案要求整数有的要求浮点数输出格式写错也会扣分。6. 笔试现场的时间分配与提交策略6.1 零分卷是怎么出现的我当时在考场认识的一个同学同一场笔试最后只交了第一题的代码。他下来跟我复盘时发现他不是不会做而是卡在第三题股票买卖上花了四十多分钟一直觉得自己的状态转移“差一点就对了”结果越调越乱后面的大题直接没时间看。这种场景在算法笔试里太常见了。一道题卡住超过20分钟最理性的选择是放弃先去做后面能拿分的题。搜狗的计分规则是按用例比例给分哪怕暴力解法也能拿个30%到50%的分这比在一道难题上死磕到零分要划算得多。6.2 按权重分配时间的实操建议结合这套题的难度分布我的建议是把120分钟切成三段前40分钟把前四道题全部AC或者拿到大部分分数。这几题考的是基本功40分钟足够。中间40分钟主攻压轴题能过多少用例就过多少用例。如果压轴题完全没思路至少把输入读进来、写个暴力框架捞一个基础分。最后40分钟回头检查前面的代码。重点是边界条件、输出格式、空间复杂度是否超限。至于哪些题先做我的原则是先做字符串题再做图论题最后做DP和概率。因为字符串和图论解法相对固定代码写起来不会出现大的思路反复DP和概率题需要多推导几步放到心态稳定的后半场更合适。提示搜狗教研岗笔试允许使用本地IDE但不要在本地写一堆调试代码不清理就提交。我见过有人提交的代码里带着print调试信息直接判错。提交前一定要删掉所有调试输出尤其是循环里高频打印的情况。最后再分享一个刷这类题的小技巧平时练习用Python3因为你不知道考场机器上编译器是什么版本Python3是兼容性最好的选择。遇到需要高精度的概率题直接用float算别用分数类库输出的时候保留指定位数浮点误差在这方面几乎可以忽略。这套题整体难度不算特别高但它充分体现了搜狗“用算法解决搜索/NLP真实问题”的用人风格。刷完这套题再去面其他互联网公司的算法岗你会发现很多题都有一种似曾相识的感觉。关键不是记题解而是把“字符串边界处理、状态机DP、BFS模板、概率递推”这几个核心技能练成肌肉记忆考场上你才能稳得住。