企业官网建设流程全解析

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和一个模式串pattern，pattern里包含两个通配符：“?”匹配任意单个字符，“*”匹配任意长度的任意字符（包括空串），问文本串中第一个匹配的位置。如果没有匹配，返回-1。

这题如果只是判断整体是否匹配，标准解法是动态规划，但题目要的是“第一个匹配位置”，所以整体动态规划会超时。现场我采用的贪心双指针是经典解法：两个指针i指向text，j指向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²)的DP；n大于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[i+1:] 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, val=0, left=None, right=None): 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模板、概率递推”这几个核心技能练成肌肉记忆，考场上你才能稳得住。