搜狗2019秋招研究员试卷的编程题在当年的校招圈里口碑一直挺两极分化——有人说考得偏基础有人说题型很“搜狗”。我自己的感受是这份卷子虽然不像某些大厂那样动不动上红黑树和仙人掌优化但它非常看重“代码能不能落地”和“边界条件想得全不全”这恰好是搜狗做搜索、做输入法、做NLP落地时最真实的工程素养。今天就把第一场试卷里涉及的编程题类型、背后的考点以及我当年踩过的坑和复盘思路整理出来。不管是准备搜狗的面试还是单纯想练算法手感这份拆解应该都能帮上忙。先说结论搜狗2019秋招研究员第一场编程题整体覆盖了字符串处理、动态规划、数据结构设计和二分答案这几大块难度介于LeetCode Medium到Hard之间但更偏向实际业务场景的抽象建模而不是纯粹炫技。题目量不大但每道题都很考验对边界条件的敏感度和代码实现的稳健度。这场笔试适合两类人参考一类是正在准备算法岗校招、想练真题手感的人另一类是已经入行、想看看搜索引擎和输入法业务背后到底考什么思维能力的人。1. 搜狗研究员笔试的出题逻辑与岗位画像1.1 研究员岗在搜狗到底做什么搜狗的研究员岗尤其在北京总部主要分布在搜索事业部、输入法事业部和AI交互技术中心。2019年前后搜狗在AI上的押注集中在自然语言处理、语音识别、图像识别和知识图谱几个方向上王小川本人也一直在强调“语言AI”是搜狗的护城河。所以这场笔试里的编程题表面看是通用的算法题但如果你仔细揣摩能发现很多题其实在模拟搜索引擎和输入法的典型场景。举个例子搜索引擎里最常干的事是什么是处理用户输入的查询词和候选文档做匹配排序。这个过程抽象出来就是字符串的匹配、编辑距离的计算、前缀树的构建。输入法呢核心是拼音串到候选词的转换本质上是一个基于统计语言模型的动态规划解码过程。所以你去看搜狗的编程题会出现大量字符串类题目这不是巧合而是岗位需求驱动的出题逻辑。1.2 笔试环节的结构与时间压力搜狗2019秋招的笔试一般是线上双机位模式时长通常在90到120分钟之间。研究员岗位的试卷一般由两部分组成选择题和编程题。选择题覆盖机器学习基础、概率统计、线性代数、数据结构等而编程题通常有2到3道分布在试卷的后半段。编程题部分的时间压力非常大。我当时拿到卷子第一件事不是急着敲代码而是先花五分钟把全部题目扫一遍评估每道题的难度和大概需要的代码量。这个习惯我到现在都推荐给所有人——校招笔试不是考试而是“在有限时间内争取最多分数”的资源分配游戏。如果有一道题一眼看上去需要写八十分钟另外两道题各要三十分钟那正确策略一定是先确保两道简单题做对再回头啃难题。1.3 为什么这份卷子值得反复刷搜狗2019秋招第一场的编程题放到今天来看依然有很高的训练价值原因有三个。第一它不偏不怪考的都是算法面试里的核心高频知识点不存在那种“不会就是不会”的偏门题。第二它的数据范围设计得很用心会故意在边界条件上埋坑比如数组为空、字符串长度极大、数值溢出等这些恰恰是实际开发中最容易出bug的地方。第三它的场景抽象方式比较典型很多题看似是竞赛题其实都能映射到搜索引擎或NLP业务中的真实问题。所以这份卷子值得反复刷而且刷的时候不要只满足于ACAccepted要追问自己如果线上环境里数据量扩大一百倍这个解法还成立吗如果输入里混入非法字符程序会不会崩这种“工程化思维”才是搜狗笔试真正要筛选的东西。2. 编程题核心考点拆解与解题思路2.1 字符串处理类题目编辑距离与最长公共子序列的变体2019年搜狗第一场笔试中有一道典型的字符串题目——考察的是编辑距离的变体。原题大致是给定两个字符串允许三种操作插入一个字符、删除一个字符、替换一个字符问最少需要多少次操作能让两个字符串相等。这道题本身是LeetCode 72的经典题但搜狗在上面加了一个变化字符集不再是全ASCII而是限定为小写字母和数字并且额外给了一个条件就是相同字符的替换代价可能不是1而是根据字符类型有所区别。我当时在这个变体上卡了挺久因为标准的二维DP动态规划转移方程是固定的但一旦代价发生变化初始化状态时要特别小心尤其是当第一个字符就存在替换代价差异时很容易漏掉初始状态的定义。解题的关键在于不要被“变体”吓住本质上还是动态规划的核心逻辑dp[i][j]表示字符串A的前i个字符转换成字符串B的前j个字符的最小代价。转移时有三种情况删除dp[i-1][j] 删除代价、插入dp[i][j-1] 插入代价、替换dp[i-1][j-1] 替换代价当A[i]等于B[j]时代价为0。代码本身并不长二十分钟内完全可以写出来。这类题的实操心得是遇到字符串DP先把状态定义写清楚再手推一遍小规模用例确认初始化没问题再动手写代码。很多人一上来就套模板结果边界条件一错调试时间比写代码时间还长。2.2 动态规划进阶带约束的路径规划问题第二道编程题是一道带约束的路径规划问题题目大意是在一个网格中从左上角走到右下角每次只能向下或向右移动网格中某些格子有障碍物不能走另外每个格子有一个权值要求找出一条路径使得经过格子的权值和最大。这道题的第一反应是标准二维DPdp[i][j] grid[i][j] max(dp[i-1][j], dp[i][j-1])遇到障碍物时跳过即可。但搜狗在这里加了一个约束走过的路径长度不能超过某个阈值K。这就把问题从普通DP变成了带限制条件的DP需要考虑增加一维状态来记录步数。我当时想到的解法是把dp[i][j]扩展成dp[i][j][k]表示走到(i, j)且步数为k时的最大权值和转移时从左边和上边累加。但很快发现一个问题步数和路径长度其实是绑定的格子数等于步数加1所以“步数不超过K”这个限制实际上就是限制格子数。这时候可以换一个思路把“走得远”转换成“步数少”用BFS或者带剪枝的搜索来做。这道题给我们的启示是动态规划的核心不是背状态转移方程而是根据题目条件灵活设计状态维度。当二维状态无法满足要求时大胆增加一维只要时间复杂度在可接受范围内一般n*m*K在100万量级以内就没问题就可以放心做。2.3 数据结构设计题LRU缓存与高频词统计除了纯算法题搜狗还考了一道数据结构设计题——本质上是LRU缓存Least Recently Used最近最少使用的变体实现一个固定容量的缓存支持读和写操作当容量满时淘汰最久没被访问的数据并要求读写操作的时间复杂度都为O(1)。LRU缓存是校招高频题但搜狗这道题的细节在于数据不是简单的key-value对而是带有访问频次信息淘汰策略是“先按最近访问时间排时间相同再按访问频次少的优先淘汰”。这就把标准LRU升级成了LRU-LFU混合体。实现思路建议用“哈希表 双向链表”的结构。哈希表负责O(1)查找双向链表负责O(1)插入和删除。对于频次维度有两种做法一种是每个频次维护一个双向链表再用一个全局变量记录最小频次另一种是直接在节点里记录频次淘汰时先找链表中频次最小的节点。前者实现复杂度高但性能更好后者代码简单但最坏情况会退化成O(n)。我当时在笔试里选择了后者因为时间有限而且笔试数据量通常不会太大O(n)的淘汰虽然理论复杂度不是最优但能在规定时间内跑通。这里建议各位在笔试时学会“成本收益分析”先用简单方案拿到部分分如果时间充裕再优化成全O(1)版本。2.4 二分答案与贪心结合的边界问题最后一类高频题型是二分答案。搜狗的编程题里有一道涉及“最小化最大值”的问题给定一个数组需要把它分成连续的K段问每段和的最大值最小是多少。这类题的套路非常固定先判断某个候选答案是否可行然后对答案进行二分搜索。判断函数用贪心实现从左到右遍历数组累加当前段的和一旦超过限制就另起一段最后看看段数是否超过K。二分下界是数组中的最大值上界是数组总和。但搜狗在这里加了两个小坑第一数组可能包含负数第二K可能大于数组长度。负数这个坑很典型一旦有负数字面意义上的“段和的最大值最小化”就意味着要尽量把负数归入某一侧来压低最大值这时候二分判断函数的贪心策略就不成立了。我当时的处理办法是如果数组中存在负数改用DP来验证可行性虽然时间复杂度高一些但至少保证正确性。K大于数组长度时直接返回-1或特殊值。这类题给我们的教训是二分答案的模板三分钟就能背下来难的是判断函数在各种边界条件下是否依然成立。建议在做完一道二分题后专门花时间手推几个包含负数和极小值的边缘用例确保逻辑的完备性。3. 核心题型的代码实现与细节优化3.1 编辑距离变体的参考实现以编辑距离变体为例我给出一个可以直接参考的C实现框架。这个实现考虑了替换代价随字符类型变化的情况#include bits/stdc.h using namespace std; int minDistance(string word1, string word2) { int n word1.size(), m word2.size(); vectorvectorint dp(n 1, vectorint(m 1, INT_MAX / 2)); // 初始化空串转换到任意串只能靠插入 for (int j 0; j m; j) dp[0][j] j; for (int i 0; i n; i) dp[i][0] i; for (int i 1; i n; i) { for (int j 1; j m; j) { int insCost 1, delCost 1, repCost 1; // 自定义替换代价字母→字母代价1数字→数字代价1字母→数字代价2 bool isDigit1 isdigit(word1[i-1]); bool isDigit2 isdigit(word2[j-1]); if (isDigit1 ! isDigit2) repCost 2; dp[i][j] min(dp[i-1][j] delCost, // 删除 dp[i][j-1] insCost); // 插入 dp[i][j] min(dp[i][j], dp[i-1][j-1] (word1[i-1] word2[j-1] ? 0 : repCost)); // 替换 } } return dp[n][m]; }注意这段代码里我用INT_MAX / 2做初始化而不是INT_MAX这是为了防止后续加法溢出。这是我在笔试里踩过的一个小坑——直接用INT_MAX初始化DP数组后任何加上一个正数的操作都会溢出成负数导致比较逻辑完全错乱。类似的细节在面试手写代码时非常容易被忽略但这种细节恰恰是面试官想看的工程素养。3.2 带约束路径规划的状态设计对于带最大步数约束的路径规划如果沿用二维DP并无法同时满足“步数限制”和“最大权值”两个条件可以考虑增加一维状态。以下是伪代码级别的实现思路// dp[i][j][k] 表示走到(i, j)经过k步时的最大权值 // 初始化dp[0][0][1] grid[0][0]因为第一步是起点 int n grid.size(), m grid[0].size(); int K maxSteps; // 给定的最大步数格子数 vectorvectorvectorint dp(n, vectorvectorint(m, vectorint(K 1, INT_MIN / 2))); dp[0][0][1] grid[0][0]; for (int k 1; k K; k) { for (int i 0; i n; i) { for (int j 0; j m; j) { if (grid[i][j] 0) continue; // 障碍物 if (i 0) dp[i][j][k] max(dp[i][j][k], dp[i-1][j][k-1] grid[i][j]); if (j 0) dp[i][j][k] max(dp[i][j][k], dp[i][j-1][k-1] grid[i][j]); } } } // 最终结果是 dp[n-1][m-1][k] 在第K步以内的最大值状态复杂度是O(n * m * K)当网格尺寸为50x50、K为100时状态量是25万个完全在可接受范围内。值得留意的是网格坐标从(0,0)出发到(m-1, n-1)的最短步数是n m - 2所以当K小于这个值时可以直接剪枝返回无解避免无意义的状态遍历。3.3 LRU-LFU混合结构的关键实现细节对于LRU-LFU混合结构我建议用一个unordered_mapint, listNode::iterator做哈希索引再用一个listNode表示访问顺序Node里记录key、value、freq以及一个unordered_mapint, listNode::iterator类型的频次索引。这个方案对容量的维护比较直观淘汰时先遍历链表找到第一个频次最小的节点删除同时更新哈希表和频次索引。struct Node { int key, value, freq; Node(int k, int v, int f) : key(k), value(v), freq(f) {} }; class LFUCache { private: int capacity; unordered_mapint, listNode::iterator keyMap; mapint, listNode freqMap; // freq - nodes // ... 省略部分实现 public: int get(int key) { if (keyMap.find(key) keyMap.end()) return -1; auto it keyMap[key]; int value it-value; int freq it-freq; freqMap[freq].erase(it); if (freqMap[freq].empty()) freqMap.erase(freq); freqMap[freq 1].push_front({key, value, freq 1}); keyMap[key] freqMap[freq 1].begin(); return value; } };这里有一个很关键的细节用mapint, listNode而不是unordered_mapint, listNode来维护频次。因为淘汰时需要找最小频次map的begin()直接就是最小频次节点时间复杂度为O(1)。这个设计比遍历所有频次找最小值要优雅得多也是我在笔试后复盘时发现的优化点。4. 笔试实战中的高频问题与避坑指南4.1 输入输出格式的“阴间”处理搜狗的笔试平台和很多公司一样对输入输出格式要求非常严格尤其是多组测试用例的情况。有些题目会要求一次读入多个测试用例以特定符号作为结束标志或者要求输出时严格按格式比如末尾不能有多余空格。我的血泪教训是拿到题目一定先花两分钟阅读输入输出说明不要直接看示例就开写。曾经有一道题输出要求每个结果占一行最后一行不能有换行符我因为多打了一个\n被判了Presentation Error格式错误整体扣分很亏。4.2 语言选择C还是Python搜狗2019年笔试支持的语言包括C、Java、Python等。我的建议是如果你对C足够熟练优先用C因为它的STL在实现LRU、二分答案、堆等数据结构时效率更高而且不容易出现Python在大数据量下超时的情况。如果你更熟Python也不是不行但需要注意Python在深层递归时容易爆栈写DFS遍历树时记得改成迭代版本。实测下来同一道二分答案题Python版本比C版本平均慢3到5倍。在时间限制为1秒的题目中Python稍不注意就会TLETime Limit Exceeded。所以我个人在校招笔试时的原则是能用C就用C只有在没有把握在两个小时内把C语法写对时才退而求其次用Python。4.3 做题顺序与时间分配的“田忌赛马”策略笔试题量通常不大但每道题都有不同的难度系数。我强烈建议按以下顺序做题先做最简单、思路最清晰的题哪怕它分值不高先拿到手再说然后做中等难度的题最后再啃最难的题。以搜狗这份卷子为例如果三道题中有一道是编辑距离变体有一道是带约束路径规划还有一道是LRU-LFU混合结构我建议先做编辑距离因为它代码量最小、最容易AC再做路径规划因为DP框架清晰最后做LRU-LFU因为链表操作细节多、容易写出隐藏bug。这个策略的核心逻辑是笔试的评分标准并不只是“是否AC”而是“通过了多少测试用例”。一道题即使没有完全AC只要部分用例通过也能拿到相应的部分分。所以与其在一道难题上耗死不如把简单题做完美再花剩余时间在难题上拿部分分。4.4 调试技巧善用打印日志很多同学在笔试时不敢用cout或printf打印调试怕影响成绩。其实完全可以放心用——只要在提交前把调试打印删掉即可。笔试平台不会因为你在代码里打印额外信息而判错但如果输出格式没删干净会导致大量测试用例格式错误。我的习惯是写完核心逻辑后先构造几个小用例手动跑一遍包括空输入、单元素输入、全同元素输入、最坏规模输入这四类用例确认无误后再提交。这一步看似繁琐但能拦截掉至少一半的边界条件错误。5. 复盘总结与后续能力提升建议5.1 从题目反推岗位能力要求搜狗这份编程题卷子表面考的是算法背后筛的其实是几个核心能力第一快速建模能力——面对一段业务描述能不能用数据结构和算法把它抽象出来第二边界敏感性——能不能在写代码时主动考虑空数组、溢出、负数、重复元素等异常场景第三代码实现的稳健性——同样的思路能不能一次写对而不是反复试错。这三个能力在搜狗的日常研发中都很重要。搜索引擎的线上服务处理的是海量真实用户输入输入数据的“脏”程度远超任何笔试题一个没考虑到的边界分支就可能导致整个召回链路崩溃。输入法每天要处理几十亿次按键一次内存越界就可能导致输入法崩溃用户体验直接崩塌。所以搜狗笔试偏爱这种“看起来简单做起来要小心”的题目其实是有意的。5.2 后续刷题方向建议如果你准备的是搜狗或其他AI公司的算法岗我的建议是别只盯着LeetCode刷还要关注以下几个方向首先动态规划的各类变形一定要吃透包括区间DP、状态压缩DP、树形DP。搜狗这类公司喜欢考DP不是偶然因为NLP里的CRF解码、句法分析、机器翻译的序列生成本质上都是DP问题。其次字符串算法要重点掌握包括KMP、Trie树、Aho-Corasick自动机这些在搜索关键词匹配、输入法联想词推荐中是基础设施级别的存在。最后多练习带工程约束的题目比如内存限制、时间复杂度限制、输入输出格式要求这些在实际业务中比纯算法题更常见。5.3 关于这份卷子的一些个人感受整理搜狗2019秋招研究员试卷的过程让我回想起当年自己刷题的那段日子。那会儿每天泡在牛客网上反复刷各大厂的笔试真题刷到后来看到“动态规划”四个字就想吐但真的拿到offer回头看那段训练带来的收益是长期的——不只是会解题更重要的是养成了“先想清楚再动手”的习惯以及面对复杂问题时拆解小步骤的能力。如果你现在正在准备校招笔试我的建议是不要只满足于“把题解出来”要强迫自己在每道题后面写一段复盘记录这道题考察的知识点、自己卡在哪一步、最优解的思路是什么。这样刷三十道题效果可能比别人刷一百道题还好。这个习惯我从校招坚持到现在在工作里做技术方案设计时也一直在用受益非常明显。最后再分享一个小技巧刷题时准备一个“错题本”把每次笔试、面试中做错的题整理归档标注错误原因和正确思路。隔两周再翻出来重新做一遍直到能脱离参考代码独立完成才算真正掌握。这个方法很笨但极其有效——人的记忆会骗人但错题本不会。