说个暴露年龄的事我当年参加过搜狗2016年的研发工程师校招笔试。那会儿互联网公司笔试还普遍是纸质试卷加机试结合搜狗的题量不算特别大但覆盖面和迷惑性都挺有一套。这么多年过去我自己也参与过不少面试出题和简历筛选回头再看当年那些题会发现考的东西其实一直没变——数据结构、算法功底、语言细节、操作系统和网络基础再加上一点逻辑思维和临场心态。这篇文章不打算帮你“背答案”而是把搜狗这套2016年研发笔试题当成一个标本拆解它背后真正想考察的能力模型。无论你是在备战校招还是工作几年后想查漏补缺都能从中找到值得反复琢磨的点。1. 搜狗2016研发笔试整体出题思路与考点布局先说结论搜狗这套笔试题的定位非常明确——筛出“基本功扎实 能上手写代码 有排查问题潜质”的人。它不追求偏题怪题而是把计算机核心课程里的经典问题换了个马甲反复考察。你要是在学校只背了概念没动过手做起来会很难受。1.1 试卷结构与题型分布从当年考生回忆和网上流传的版本来看搜狗2016研发工程师笔试题大致分为四类题型题量考察目标单选/多选15~20题基础概念、语言细节、数据结构、操作系统、网络简答/填空3~5题概念理解、计算复杂度、内存布局、进程线程编程题2~3题手写算法、代码规范、边界处理综合/逻辑题1~2题系统设计思维、问题分析能力选择题覆盖面很广从C的虚函数表到TCP三次握手从二叉树遍历到数据库索引几乎每门核心课都会点到。简答题偏重“能不能说清楚”比如让你解释某个概念的区别或者给出一段代码问输出结果。编程题则是拉开差距的关键通常第一道是链表或字符串操作第二道是动态规划或二叉树相关第三道可能是场景模拟或搜索问题。这套结构其实代表了很多互联网公司笔试的通用模板先铺量看广度再用简答看深度最后用编程题见真章。1.2 高频考点背后的考察逻辑搜狗作为搜索引擎公司对算法和数据结构的重视程度自然不低。但和纯算法岗不同研发工程师更看重工程落地能力所以考题里你会发现很多“看似基础但很容易写错”的题目比如链表的反转、删除、判环字符串的匹配、去重、按规则转换二叉树的遍历方式、深度计算、层次输出排序算法的稳定性、时间复杂度和手写实现动态规划的人人都会但状态转移方程写不对的经典题这些考点背后考察的不是“背没背过”而是“有没有真正写过、调试过”。面试官想看到的是你面对一个需求时能否快速抽象出数据结构、设计合理算法并且写出边界条件完备的代码。说白了就是考察你有没有“工程感”。2. 考点实战拆解数据结构与算法重点题精讲我把当年搜狗笔试里出现频率最高、也最典型的几类算法题拿出来逐题拆解。每一道题我都会给出解题思路、关键代码和易错点这些思路直到今天的面试仍然适用。2.1 链表题反转链表与环检测的完整解法链表是笔试的“送分题”也是“送命题”。说送分是因为你肯定复习过说送命是因为手写时很容易在指针操作上翻车。先看单链表反转。这个题核心思路就是三个指针prev、current、next。struct ListNode { int val; struct ListNode *next; }; struct ListNode* reverseList(struct ListNode* head) { struct ListNode *prev NULL; struct ListNode *curr head; while (curr ! NULL) { struct ListNode *next curr-next; // 先保存下一个节点 curr-next prev; // 当前节点指向前一个 prev curr; // prev 前进 curr next; // curr 前进 } return prev; }这段代码看起来简单但有几个细节很关键一是next指针必须在修改curr-next之前保存否则节点丢失。很多人一紧张就写反了顺序。二是循环结束后返回值是prev而不是curr因为此时curr已经是NULL。三是如果链表为空或只有一个节点循环体和返回逻辑也能正确工作不用单独加特殊判断。再来看环检测。经典的快慢指针方法很简单但笔试里容易在“为什么快指针每次走两步、慢指针走一步就一定能相遇”上被追问。设链表起点到环入口的距离为 a环的长度为 b。当慢指针进入环后快指针已经在环内走了若干圈。由于快指针相对慢指针每次多走一步相当于每走一次快指针就靠近慢指针一步所以只要存在环就一定能相遇。相遇后把快指针移到链表头两者每次各走一步再次相遇处就是环入口。这个结论我不会让你死记建议自己画个图推导一遍笔试时如果遇到变体题理解了原理才能举一反三。2.2 动态规划最长公共子序列与状态转移方程搜狗笔试题里动态规划出现频率相当高其中最长公共子序列LCS是最经典的一道。别小看这个题很多人在纸上写状态转移方程时就会漏掉一种情况。题目通常是这样给定两个字符串 text1 和 text2返回它们的最长公共子序列长度。定义dp[i][j]表示 text1 的前 i 个字符和 text2 的前 j 个字符的最长公共子序列长度。转移方程分两种情况if text1[i-1] text2[j-1]: dp[i][j] dp[i-1][j-1] 1 else: dp[i][j] max(dp[i-1][j], dp[i][j-1])很多人的问题出在 else 分支。当当前字符不相等时最长公共子序列要么在 text1 去掉当前字符的子问题里要么在 text2 去掉当前字符的子问题里取两者最大值。有些人会写成dp[i][j] dp[i-1][j-1]这就错了因为两个字符串各去掉一个字符不一定能得到最优解。初始化时第一行和第一列都是 0。写代码时建议用二维数组从 i1、j1 开始循环。这道题能延伸出来的变体还有最长递增子序列、编辑距离都是同一个套路。如果你的目标公司笔试难度略高这几个题一定要一起练。2.3 字符串处理全排列去重与朴素匹配优化字符串题里搜狗出过全排列类的题目。要求输出一个字符串所有字符的全排列且不能有重复。思路是递归加交换。把字符串看成两部分第一个字符和剩余字符。每次把第一个字符与后面的每个字符交换然后递归处理剩余部分。去重的核心在于每次交换前检查当前字符在起始位置到当前位置之间是否已经出现过如果出现过就跳过。void permute(char *str, int start, int end) { if (start end) { printf(%s\n, str); return; } for (int i start; i end; i) { if (isDuplicate(str, start, i)) continue; swap(str[start], str[i]); permute(str, start 1, end); swap(str[start], str[i]); // 回溯 } }isDuplicate检查 s[start] 到 s[i-1] 之间是否出现过 s[i] 的值。这里有个容易踩的坑交换过后再回溯时千万别忘记把字符换回来否则递归调用就乱套了。我当年笔试时就因为漏了回溯输出结果全错。这类题很考察代码的鲁棒性面试官不会只看输出对不对还会看你有没有考虑空串、单个字符、重复字符这些边界情况。3. 语言、操作系统与网络题看似送分实则杀机四伏笔试里的选择题和简答题很多是“看着眼熟选的时候心里发虚”的类型。我整理几个搜狗2016笔试中出现的知识点结合真实考场体验说说。3.1 C/C语言细节指针、内存和关键字陷阱搜狗对C/C的考察一直比较重视。当年的选择题里出现过这么一道坑题sizeof和strlen的区别、指针数组和数组指针的区分、const修饰指针的两种形式。这些点单看都不难但混在一起出题正确率其实不高。举个例子char *p hello; char arr[] hello; printf(%lu %lu\n, sizeof(p), sizeof(arr));这个输出结果分别是 864位系统指针大小和 6五个字符加结束符。如果你写成了 5 和 5说明对sizeof的理解还不到位。sizeof(p)求的是指针本身占用的字节数跟字符串长度毫无关系sizeof(arr)求的是整个数组的大小包含末尾的\0。而strlen才算到\0为止不包含\0。还有一个高频考点是内存泄漏。一段代码里用malloc分配了内存但提前return时忘了free。选择题会问程序存在什么问题。这种题考察的是你有没有意识到“每一条 return 路径”都需要释放心态如果笔试时遇到记得把所有退出分支都检查一遍。3.2 操作系统与网络进程线程、死锁与TCP握手操作系统考点集中在进程与线程的区别、死锁产生的四个必要条件、虚拟内存和分页机制、进程调度算法。搜狗有一道简答是让解释“进程和线程的区别”并要求结合搜索引擎的一个实际应用场景来说。这时候不要只背概念要说“多线程适合IO密集型的抓取任务因为线程切换开销小可以同时等待多个网络请求返回多进程适合计算密集型任务能利用多核CPU并行能力”这样能体现你真的理解。网络部分重点是TCP三次握手和四次挥手、TCP和UDP的区别、HTTP状态码含义。其中有一个容易丢分的地方是为什么连接是三次握手而断开需要四次因为TCP连接是全双工的断开时每个方向都要单独关闭。主动方发送FIN只能表示自己不再发送数据但还能接收数据所以被动方先回复ACK等自己的数据也发送完毕后再发送FIN这样就比建立连接多了一次交互。3.3 数据库与Linux索引原理与常用命令数据库题里索引的实现原理和适用场景是必考。搜狗有一道选择题问的是在哪些列上适合建索引答案一般是频繁出现在 WHERE 条件的列、需要排序和分组的列、区分度高的列。反过来频繁更新的列、值大量重复的列不适合建索引。深入一点会考 B 树为什么适合做索引——它矮胖层数少磁盘IO次数少而且叶子节点用链表串联很方便范围查询。Linux命令填空也是常见题型比如统计文件行数用wc -l在文件里查找关键词用grep查找可执行文件路径用which或find查看端口占用用netstat -tlnp。这些命令平时不用根本记不住但笔试就是考你这点“肌肉记忆”。4. 编程题完整实战搜狗风格算法题的实现与优化根据当年的考生回忆搜狗笔试的编程题中有几道特别典型的题目我挑两道还原一下完整分析过程。第一题是“按之字形打印二叉树”第二题是“实现一个带过期时间的LRU缓存”。前者考遍历变形后者考数据结构和工程设计的综合能力。4.1 之字形打印二叉树层序遍历的进阶版本题目要求请实现一个函数按照之字形顺序打印二叉树即第一行从左到右打印第二行从右到左打印第三行再从左到右依此类推。解题思路是在常规层序遍历的基础上添加一个层号奇偶判断。我用队列做层序遍历用栈结构来辅助逆序输出。void printZigzag(struct TreeNode* root) { if (root NULL) return; struct TreeNode** queue (struct TreeNode**)malloc(sizeof(struct TreeNode*) * 10000); int head 0, tail 0; queue[tail] root; int level 1; while (head tail) { int levelSize tail - head; int *vals (int*)malloc(sizeof(int) * levelSize); for (int i 0; i levelSize; i) { struct TreeNode* node queue[head]; vals[i] node-val; if (node-left) queue[tail] node-left; if (node-right) queue[tail] node-right; } if (level % 2 0) { for (int i levelSize - 1; i 0; i--) { printf(%d , vals[i]); } } else { for (int i 0; i levelSize; i) { printf(%d , vals[i]); } } printf(\n); free(vals); level; } free(queue); }这里的关键点是先读取固定数量的节点再入队子节点避免把下一层的节点和当前层混在一起。如果不用 levelSize 记录每层节点数就无法判断什么时候该换行也就无法区分奇偶层。另一个细节是偶数层用逆序输出时不应该真的翻转队列里的节点顺序而是通过索引逆序打印即可。这道题的延伸考法还有按层输出二叉树、二叉树的最大宽度、填充每个节点的下一个右侧节点指针本质上都是层序遍历加一点状态管理。建议你把层序遍历练到闭着眼睛能写出来。4.2 手写LRU缓存很多公司的必修课当年搜狗笔试虽然没有明确要求手写LRU但综合题里出现过相关场景。现在这道题几乎是互联网公司笔试面试的标准配置提前练好不吃亏。LRULeast Recently Used的核心思想是当缓存满了优先淘汰最久没有被访问的数据。实现方案常用的就是“哈希表 双向链表”。哈希表负责O(1)查找双向链表负责O(1)插入和删除。我用C写一个核心结构版本class LRUCache { private: int capacity; listpairint, int cacheList; unordered_mapint, listpairint, int::iterator cacheMap; public: LRUCache(int capacity) { this-capacity capacity; } int get(int key) { auto it cacheMap.find(key); if (it cacheMap.end()) return -1; // 把访问的节点移到链表头部 cacheList.splice(cacheList.begin(), cacheList, it-second); return it-second-second; } void put(int key, int value) { auto it cacheMap.find(key); if (it ! cacheMap.end()) { it-second-second value; cacheList.splice(cacheList.begin(), cacheList, it-second); return; } if (cacheList.size() capacity) { auto last cacheList.back(); cacheMap.erase(last.first); cacheList.pop_back(); } cacheList.push_front({key, value}); cacheMap[key] cacheList.begin(); } };这里有两个细节很容易被忽略。第一splice操作不能自己写erase再insert因为这样会导致迭代器失效而且多了一次哈希查找。用splice直接调整链表节点位置效率最高。第二当插入一个已存在的键时要更新value并把它移到头部而不是直接返回或插入失败。工作中如果你真的在服务端实现了类似逻辑还要考虑多线程并发访问通常要加锁或使用读写锁。笔试阶段只要能写出单线程版本、说清楚为什么用哈希表和双向链表组合就足以过关。4.3 代码规范与边界条件拿到手写题的第一件事编程题除了算法正确性代码规范和边界处理也是隐形的评分点。标准阅卷时结构化清晰、命名规范、缩进整齐的答案天然比一团乱麻的代码更容易拿高分。拿到题目后我建议按这个顺序过一遍确认输入输出格式是不是用标准输入输出还是需要写完整函数考虑空输入、空字符串、指针为空的情况。考虑单个元素、重复元素、最大值最小值等边界。考虑程序是否可能溢出例如整数相加、字符串长度等。最后再优化时间复杂度和空间复杂度。很多人上来就写代码写到一半发现边界情况没考虑只能涂涂改改卷面变得很乱。更稳的做法是先花3到5分钟在草稿纸上列测试用例再动笔写。比如做逆序字符串时先写下空串、单字符、长度奇偶不同的用例然后对照写代码这样能覆盖绝大多数边界问题。5. 搜狗2016笔试中的经典逻辑与系统设计题除了纯算法基础搜狗笔试里还有一类让人意外的题就是逻辑推理题和简化的系统设计题。这类题不考某个具体API或语法而是考察思维方式和工程判断力。5.1 逻辑题从“两个烧绳计时”到“海量数据找重复”逻辑题比较经典的有“烧一根不均匀的绳子从头烧到尾要1小时怎么用它测出45分钟”还有“1000瓶药水有一瓶有毒最少需要多少只小白鼠测出是哪一瓶”。这些题流传很广搜狗笔试也喜欢换汤不换药地考。核心思路是转化为二进制或状态编码问题。1000瓶药水用10只小白鼠就能测出来因为2的10次方等于1024每瓶药水对应一个10位二进制编号让对应位的小白鼠喝这瓶药最后根据死亡情况反推出二进制编号。这类题做不出来不代表你不行但平时多刷逻辑题确实能提升思维的灵活性。建议遇到不会的题时先不要慌从“信息量”和“状态编码”两个角度去切入往往能找到突破口。5.2 系统设计题如何设计一个短链接服务搜狗笔试的综合题里出现过类似“设计一个短链接系统要求说明存储方案和跳转流程”的题目。这道题不算难但能看出你有没有系统设计的直觉。我当时的大致思路是生成短码用自增ID或随机数生成6到8位的短码。存储方案短码到原始URL的映射可以用关系型数据库比如MySQL表两个字段short_code 设为主键也可以加一层 Redis 做缓存热点数据直接命中内存。跳转流程用户访问短链接服务器解析短码查库或缓存拿到原始URL返回 302 重定向到目标地址。加分点在于你会考虑短码冲突怎么处理、原始URL被多个用户提交时是否复用同一短码、短码的字符集会否包含易混淆的字符比如0和O、如果被恶意刷量怎么办。这些点哪怕只是提一两句都能体现工程思维。笔试中遇到系统设计题不需要写出完整方案先把核心组件列出来再把关键流程说清楚最后补充一两个优化点基本就能拿到大部分分数。6. 备战时最该踩的雷真实经历与常见问题排查最后这部分是重头戏。我把当年复习和实际笔试中踩过的坑、以及每年考生最容易犯的错误集中整理一下希望能帮你少走弯路。6.1 时间分配失控选择题耗时过多导致编程题没做完搜狗笔试题量对很多人来说偏大。我当年就是选择题里抠一个C多继承的细节足足纠结了十分钟最后编程题写得匆匆忙忙第二道动态规划只写了一小半就交卷了。这是最典型的战略失误。从应试策略上讲选择题如果思考超过两分钟还没有明确思路就应该先标记一个最可能的选项并跳到下一题。编程题分值通常更高但很多考生出于惯性会优先死磕前面的难题。合理的时间分配是选择题控制在总时长的40%以内简答题和编程题至少留出55%的时间最后5%用于检查。6.2 手写代码的致命细节没有考虑空指针和内存管理平时在IDE里写代码编译器会自动提示空指针风险。但笔试是白纸或在线编辑器没有编译器辅助很多考生就会漏掉边界判断。比如反转链表时没有判断head是否为空最后访问空指针直接崩溃。另一个问题是内存管理。申请了堆内存后没有释放虽然是常规考点但面试官更希望看到你写代码时下意识地处理好内存释放。至少在编程题结尾用注释标注一下哪些地方需要free或者直接在代码里写出来这点很加分。6.3 混淆概念大小端、静态变量和线程安全历年考生容易在几个概念上反复出错搜狗也不例外大小端0x12345678 在大端机器内存中存储从高位到低位是 12 34 56 78在小端机器则是 78 56 34 12。一道选择题如果问“在32位系统上int a0x12345678取地址后第一个字节是什么”正确答案取决于你是大端还是小端。大多数PC是小端所以第一个字节是 0x78。静态变量函数内 static 变量只会初始化一次且存放在静态存储区多条线程同时读写时存在线程安全问题。一个简单的输出题就能难倒一片人。死锁产生条件互斥、占有且等待、不可抢占、循环等待四者同时满足。缺少任何一个都不会死锁这个点简答也常考。6.4 复习路线建议三轮刷题法根据我自己的备考过程我建议用三轮刷题法来准备这类研发工程师笔试。第一轮是系统性复习以教材和基础题为主。把数据结构的每一种结构都过一遍数组、链表、栈、队列、哈希表、树、图、堆每种结构至少手写一遍插入和删除操作。语言方面把C的指针、引用、内存模型、STL常用容器实现原理搞清楚。第二轮是按真题模拟训练。找近三年的搜狗真题或其他互联网公司同类笔试题限时两小时完整做一遍。这一轮不需要追求满分重点是找到自己最薄弱的章节。做完之后把错题归到对应知识点比如链表错题、动态规划错题、网络错题方便下一轮针对性突破。第三轮是把错题重做一到两遍。别只看答案要亲手写代码反复调试到能独立通过测试用例。到了考场上这些被打磨过的肌肉记忆会救你命。7. 写在最后那份笔试题带给我的不止是Offer搜狗2016年的研发笔试题距离现在已经有些年头了但那套题带给我的启发到现在依然适用。它用一道道题告诉我研发工程师的基本功容不得半点侥幸链表反转、动态规划、内存管理、TCP协议这些知识不是考完就扔的东西而是日后每一天写代码都可能碰到的底层能力。我后来的教训是刷题的目的不是为了“押中题目”而是为了在紧张状态下依然能写出干净正确的代码。真正到了考场上你靠的不是临场发挥而是平时训练积累出的下意识反应。如果你正在准备互联网公司的研发工程师笔试建议把这篇内容里的题目亲手做一遍、把每个易错点都写进自己的错题本里。纸上得来终觉浅绝知此事要躬行。共勉。
搜狗2016研发笔试题深度拆解：校招备战与算法核心考点剖析
说个暴露年龄的事我当年参加过搜狗2016年的研发工程师校招笔试。那会儿互联网公司笔试还普遍是纸质试卷加机试结合搜狗的题量不算特别大但覆盖面和迷惑性都挺有一套。这么多年过去我自己也参与过不少面试出题和简历筛选回头再看当年那些题会发现考的东西其实一直没变——数据结构、算法功底、语言细节、操作系统和网络基础再加上一点逻辑思维和临场心态。这篇文章不打算帮你“背答案”而是把搜狗这套2016年研发笔试题当成一个标本拆解它背后真正想考察的能力模型。无论你是在备战校招还是工作几年后想查漏补缺都能从中找到值得反复琢磨的点。1. 搜狗2016研发笔试整体出题思路与考点布局先说结论搜狗这套笔试题的定位非常明确——筛出“基本功扎实 能上手写代码 有排查问题潜质”的人。它不追求偏题怪题而是把计算机核心课程里的经典问题换了个马甲反复考察。你要是在学校只背了概念没动过手做起来会很难受。1.1 试卷结构与题型分布从当年考生回忆和网上流传的版本来看搜狗2016研发工程师笔试题大致分为四类题型题量考察目标单选/多选15~20题基础概念、语言细节、数据结构、操作系统、网络简答/填空3~5题概念理解、计算复杂度、内存布局、进程线程编程题2~3题手写算法、代码规范、边界处理综合/逻辑题1~2题系统设计思维、问题分析能力选择题覆盖面很广从C的虚函数表到TCP三次握手从二叉树遍历到数据库索引几乎每门核心课都会点到。简答题偏重“能不能说清楚”比如让你解释某个概念的区别或者给出一段代码问输出结果。编程题则是拉开差距的关键通常第一道是链表或字符串操作第二道是动态规划或二叉树相关第三道可能是场景模拟或搜索问题。这套结构其实代表了很多互联网公司笔试的通用模板先铺量看广度再用简答看深度最后用编程题见真章。1.2 高频考点背后的考察逻辑搜狗作为搜索引擎公司对算法和数据结构的重视程度自然不低。但和纯算法岗不同研发工程师更看重工程落地能力所以考题里你会发现很多“看似基础但很容易写错”的题目比如链表的反转、删除、判环字符串的匹配、去重、按规则转换二叉树的遍历方式、深度计算、层次输出排序算法的稳定性、时间复杂度和手写实现动态规划的人人都会但状态转移方程写不对的经典题这些考点背后考察的不是“背没背过”而是“有没有真正写过、调试过”。面试官想看到的是你面对一个需求时能否快速抽象出数据结构、设计合理算法并且写出边界条件完备的代码。说白了就是考察你有没有“工程感”。2. 考点实战拆解数据结构与算法重点题精讲我把当年搜狗笔试里出现频率最高、也最典型的几类算法题拿出来逐题拆解。每一道题我都会给出解题思路、关键代码和易错点这些思路直到今天的面试仍然适用。2.1 链表题反转链表与环检测的完整解法链表是笔试的“送分题”也是“送命题”。说送分是因为你肯定复习过说送命是因为手写时很容易在指针操作上翻车。先看单链表反转。这个题核心思路就是三个指针prev、current、next。struct ListNode { int val; struct ListNode *next; }; struct ListNode* reverseList(struct ListNode* head) { struct ListNode *prev NULL; struct ListNode *curr head; while (curr ! NULL) { struct ListNode *next curr-next; // 先保存下一个节点 curr-next prev; // 当前节点指向前一个 prev curr; // prev 前进 curr next; // curr 前进 } return prev; }这段代码看起来简单但有几个细节很关键一是next指针必须在修改curr-next之前保存否则节点丢失。很多人一紧张就写反了顺序。二是循环结束后返回值是prev而不是curr因为此时curr已经是NULL。三是如果链表为空或只有一个节点循环体和返回逻辑也能正确工作不用单独加特殊判断。再来看环检测。经典的快慢指针方法很简单但笔试里容易在“为什么快指针每次走两步、慢指针走一步就一定能相遇”上被追问。设链表起点到环入口的距离为 a环的长度为 b。当慢指针进入环后快指针已经在环内走了若干圈。由于快指针相对慢指针每次多走一步相当于每走一次快指针就靠近慢指针一步所以只要存在环就一定能相遇。相遇后把快指针移到链表头两者每次各走一步再次相遇处就是环入口。这个结论我不会让你死记建议自己画个图推导一遍笔试时如果遇到变体题理解了原理才能举一反三。2.2 动态规划最长公共子序列与状态转移方程搜狗笔试题里动态规划出现频率相当高其中最长公共子序列LCS是最经典的一道。别小看这个题很多人在纸上写状态转移方程时就会漏掉一种情况。题目通常是这样给定两个字符串 text1 和 text2返回它们的最长公共子序列长度。定义dp[i][j]表示 text1 的前 i 个字符和 text2 的前 j 个字符的最长公共子序列长度。转移方程分两种情况if text1[i-1] text2[j-1]: dp[i][j] dp[i-1][j-1] 1 else: dp[i][j] max(dp[i-1][j], dp[i][j-1])很多人的问题出在 else 分支。当当前字符不相等时最长公共子序列要么在 text1 去掉当前字符的子问题里要么在 text2 去掉当前字符的子问题里取两者最大值。有些人会写成dp[i][j] dp[i-1][j-1]这就错了因为两个字符串各去掉一个字符不一定能得到最优解。初始化时第一行和第一列都是 0。写代码时建议用二维数组从 i1、j1 开始循环。这道题能延伸出来的变体还有最长递增子序列、编辑距离都是同一个套路。如果你的目标公司笔试难度略高这几个题一定要一起练。2.3 字符串处理全排列去重与朴素匹配优化字符串题里搜狗出过全排列类的题目。要求输出一个字符串所有字符的全排列且不能有重复。思路是递归加交换。把字符串看成两部分第一个字符和剩余字符。每次把第一个字符与后面的每个字符交换然后递归处理剩余部分。去重的核心在于每次交换前检查当前字符在起始位置到当前位置之间是否已经出现过如果出现过就跳过。void permute(char *str, int start, int end) { if (start end) { printf(%s\n, str); return; } for (int i start; i end; i) { if (isDuplicate(str, start, i)) continue; swap(str[start], str[i]); permute(str, start 1, end); swap(str[start], str[i]); // 回溯 } }isDuplicate检查 s[start] 到 s[i-1] 之间是否出现过 s[i] 的值。这里有个容易踩的坑交换过后再回溯时千万别忘记把字符换回来否则递归调用就乱套了。我当年笔试时就因为漏了回溯输出结果全错。这类题很考察代码的鲁棒性面试官不会只看输出对不对还会看你有没有考虑空串、单个字符、重复字符这些边界情况。3. 语言、操作系统与网络题看似送分实则杀机四伏笔试里的选择题和简答题很多是“看着眼熟选的时候心里发虚”的类型。我整理几个搜狗2016笔试中出现的知识点结合真实考场体验说说。3.1 C/C语言细节指针、内存和关键字陷阱搜狗对C/C的考察一直比较重视。当年的选择题里出现过这么一道坑题sizeof和strlen的区别、指针数组和数组指针的区分、const修饰指针的两种形式。这些点单看都不难但混在一起出题正确率其实不高。举个例子char *p hello; char arr[] hello; printf(%lu %lu\n, sizeof(p), sizeof(arr));这个输出结果分别是 864位系统指针大小和 6五个字符加结束符。如果你写成了 5 和 5说明对sizeof的理解还不到位。sizeof(p)求的是指针本身占用的字节数跟字符串长度毫无关系sizeof(arr)求的是整个数组的大小包含末尾的\0。而strlen才算到\0为止不包含\0。还有一个高频考点是内存泄漏。一段代码里用malloc分配了内存但提前return时忘了free。选择题会问程序存在什么问题。这种题考察的是你有没有意识到“每一条 return 路径”都需要释放心态如果笔试时遇到记得把所有退出分支都检查一遍。3.2 操作系统与网络进程线程、死锁与TCP握手操作系统考点集中在进程与线程的区别、死锁产生的四个必要条件、虚拟内存和分页机制、进程调度算法。搜狗有一道简答是让解释“进程和线程的区别”并要求结合搜索引擎的一个实际应用场景来说。这时候不要只背概念要说“多线程适合IO密集型的抓取任务因为线程切换开销小可以同时等待多个网络请求返回多进程适合计算密集型任务能利用多核CPU并行能力”这样能体现你真的理解。网络部分重点是TCP三次握手和四次挥手、TCP和UDP的区别、HTTP状态码含义。其中有一个容易丢分的地方是为什么连接是三次握手而断开需要四次因为TCP连接是全双工的断开时每个方向都要单独关闭。主动方发送FIN只能表示自己不再发送数据但还能接收数据所以被动方先回复ACK等自己的数据也发送完毕后再发送FIN这样就比建立连接多了一次交互。3.3 数据库与Linux索引原理与常用命令数据库题里索引的实现原理和适用场景是必考。搜狗有一道选择题问的是在哪些列上适合建索引答案一般是频繁出现在 WHERE 条件的列、需要排序和分组的列、区分度高的列。反过来频繁更新的列、值大量重复的列不适合建索引。深入一点会考 B 树为什么适合做索引——它矮胖层数少磁盘IO次数少而且叶子节点用链表串联很方便范围查询。Linux命令填空也是常见题型比如统计文件行数用wc -l在文件里查找关键词用grep查找可执行文件路径用which或find查看端口占用用netstat -tlnp。这些命令平时不用根本记不住但笔试就是考你这点“肌肉记忆”。4. 编程题完整实战搜狗风格算法题的实现与优化根据当年的考生回忆搜狗笔试的编程题中有几道特别典型的题目我挑两道还原一下完整分析过程。第一题是“按之字形打印二叉树”第二题是“实现一个带过期时间的LRU缓存”。前者考遍历变形后者考数据结构和工程设计的综合能力。4.1 之字形打印二叉树层序遍历的进阶版本题目要求请实现一个函数按照之字形顺序打印二叉树即第一行从左到右打印第二行从右到左打印第三行再从左到右依此类推。解题思路是在常规层序遍历的基础上添加一个层号奇偶判断。我用队列做层序遍历用栈结构来辅助逆序输出。void printZigzag(struct TreeNode* root) { if (root NULL) return; struct TreeNode** queue (struct TreeNode**)malloc(sizeof(struct TreeNode*) * 10000); int head 0, tail 0; queue[tail] root; int level 1; while (head tail) { int levelSize tail - head; int *vals (int*)malloc(sizeof(int) * levelSize); for (int i 0; i levelSize; i) { struct TreeNode* node queue[head]; vals[i] node-val; if (node-left) queue[tail] node-left; if (node-right) queue[tail] node-right; } if (level % 2 0) { for (int i levelSize - 1; i 0; i--) { printf(%d , vals[i]); } } else { for (int i 0; i levelSize; i) { printf(%d , vals[i]); } } printf(\n); free(vals); level; } free(queue); }这里的关键点是先读取固定数量的节点再入队子节点避免把下一层的节点和当前层混在一起。如果不用 levelSize 记录每层节点数就无法判断什么时候该换行也就无法区分奇偶层。另一个细节是偶数层用逆序输出时不应该真的翻转队列里的节点顺序而是通过索引逆序打印即可。这道题的延伸考法还有按层输出二叉树、二叉树的最大宽度、填充每个节点的下一个右侧节点指针本质上都是层序遍历加一点状态管理。建议你把层序遍历练到闭着眼睛能写出来。4.2 手写LRU缓存很多公司的必修课当年搜狗笔试虽然没有明确要求手写LRU但综合题里出现过相关场景。现在这道题几乎是互联网公司笔试面试的标准配置提前练好不吃亏。LRULeast Recently Used的核心思想是当缓存满了优先淘汰最久没有被访问的数据。实现方案常用的就是“哈希表 双向链表”。哈希表负责O(1)查找双向链表负责O(1)插入和删除。我用C写一个核心结构版本class LRUCache { private: int capacity; listpairint, int cacheList; unordered_mapint, listpairint, int::iterator cacheMap; public: LRUCache(int capacity) { this-capacity capacity; } int get(int key) { auto it cacheMap.find(key); if (it cacheMap.end()) return -1; // 把访问的节点移到链表头部 cacheList.splice(cacheList.begin(), cacheList, it-second); return it-second-second; } void put(int key, int value) { auto it cacheMap.find(key); if (it ! cacheMap.end()) { it-second-second value; cacheList.splice(cacheList.begin(), cacheList, it-second); return; } if (cacheList.size() capacity) { auto last cacheList.back(); cacheMap.erase(last.first); cacheList.pop_back(); } cacheList.push_front({key, value}); cacheMap[key] cacheList.begin(); } };这里有两个细节很容易被忽略。第一splice操作不能自己写erase再insert因为这样会导致迭代器失效而且多了一次哈希查找。用splice直接调整链表节点位置效率最高。第二当插入一个已存在的键时要更新value并把它移到头部而不是直接返回或插入失败。工作中如果你真的在服务端实现了类似逻辑还要考虑多线程并发访问通常要加锁或使用读写锁。笔试阶段只要能写出单线程版本、说清楚为什么用哈希表和双向链表组合就足以过关。4.3 代码规范与边界条件拿到手写题的第一件事编程题除了算法正确性代码规范和边界处理也是隐形的评分点。标准阅卷时结构化清晰、命名规范、缩进整齐的答案天然比一团乱麻的代码更容易拿高分。拿到题目后我建议按这个顺序过一遍确认输入输出格式是不是用标准输入输出还是需要写完整函数考虑空输入、空字符串、指针为空的情况。考虑单个元素、重复元素、最大值最小值等边界。考虑程序是否可能溢出例如整数相加、字符串长度等。最后再优化时间复杂度和空间复杂度。很多人上来就写代码写到一半发现边界情况没考虑只能涂涂改改卷面变得很乱。更稳的做法是先花3到5分钟在草稿纸上列测试用例再动笔写。比如做逆序字符串时先写下空串、单字符、长度奇偶不同的用例然后对照写代码这样能覆盖绝大多数边界问题。5. 搜狗2016笔试中的经典逻辑与系统设计题除了纯算法基础搜狗笔试里还有一类让人意外的题就是逻辑推理题和简化的系统设计题。这类题不考某个具体API或语法而是考察思维方式和工程判断力。5.1 逻辑题从“两个烧绳计时”到“海量数据找重复”逻辑题比较经典的有“烧一根不均匀的绳子从头烧到尾要1小时怎么用它测出45分钟”还有“1000瓶药水有一瓶有毒最少需要多少只小白鼠测出是哪一瓶”。这些题流传很广搜狗笔试也喜欢换汤不换药地考。核心思路是转化为二进制或状态编码问题。1000瓶药水用10只小白鼠就能测出来因为2的10次方等于1024每瓶药水对应一个10位二进制编号让对应位的小白鼠喝这瓶药最后根据死亡情况反推出二进制编号。这类题做不出来不代表你不行但平时多刷逻辑题确实能提升思维的灵活性。建议遇到不会的题时先不要慌从“信息量”和“状态编码”两个角度去切入往往能找到突破口。5.2 系统设计题如何设计一个短链接服务搜狗笔试的综合题里出现过类似“设计一个短链接系统要求说明存储方案和跳转流程”的题目。这道题不算难但能看出你有没有系统设计的直觉。我当时的大致思路是生成短码用自增ID或随机数生成6到8位的短码。存储方案短码到原始URL的映射可以用关系型数据库比如MySQL表两个字段short_code 设为主键也可以加一层 Redis 做缓存热点数据直接命中内存。跳转流程用户访问短链接服务器解析短码查库或缓存拿到原始URL返回 302 重定向到目标地址。加分点在于你会考虑短码冲突怎么处理、原始URL被多个用户提交时是否复用同一短码、短码的字符集会否包含易混淆的字符比如0和O、如果被恶意刷量怎么办。这些点哪怕只是提一两句都能体现工程思维。笔试中遇到系统设计题不需要写出完整方案先把核心组件列出来再把关键流程说清楚最后补充一两个优化点基本就能拿到大部分分数。6. 备战时最该踩的雷真实经历与常见问题排查最后这部分是重头戏。我把当年复习和实际笔试中踩过的坑、以及每年考生最容易犯的错误集中整理一下希望能帮你少走弯路。6.1 时间分配失控选择题耗时过多导致编程题没做完搜狗笔试题量对很多人来说偏大。我当年就是选择题里抠一个C多继承的细节足足纠结了十分钟最后编程题写得匆匆忙忙第二道动态规划只写了一小半就交卷了。这是最典型的战略失误。从应试策略上讲选择题如果思考超过两分钟还没有明确思路就应该先标记一个最可能的选项并跳到下一题。编程题分值通常更高但很多考生出于惯性会优先死磕前面的难题。合理的时间分配是选择题控制在总时长的40%以内简答题和编程题至少留出55%的时间最后5%用于检查。6.2 手写代码的致命细节没有考虑空指针和内存管理平时在IDE里写代码编译器会自动提示空指针风险。但笔试是白纸或在线编辑器没有编译器辅助很多考生就会漏掉边界判断。比如反转链表时没有判断head是否为空最后访问空指针直接崩溃。另一个问题是内存管理。申请了堆内存后没有释放虽然是常规考点但面试官更希望看到你写代码时下意识地处理好内存释放。至少在编程题结尾用注释标注一下哪些地方需要free或者直接在代码里写出来这点很加分。6.3 混淆概念大小端、静态变量和线程安全历年考生容易在几个概念上反复出错搜狗也不例外大小端0x12345678 在大端机器内存中存储从高位到低位是 12 34 56 78在小端机器则是 78 56 34 12。一道选择题如果问“在32位系统上int a0x12345678取地址后第一个字节是什么”正确答案取决于你是大端还是小端。大多数PC是小端所以第一个字节是 0x78。静态变量函数内 static 变量只会初始化一次且存放在静态存储区多条线程同时读写时存在线程安全问题。一个简单的输出题就能难倒一片人。死锁产生条件互斥、占有且等待、不可抢占、循环等待四者同时满足。缺少任何一个都不会死锁这个点简答也常考。6.4 复习路线建议三轮刷题法根据我自己的备考过程我建议用三轮刷题法来准备这类研发工程师笔试。第一轮是系统性复习以教材和基础题为主。把数据结构的每一种结构都过一遍数组、链表、栈、队列、哈希表、树、图、堆每种结构至少手写一遍插入和删除操作。语言方面把C的指针、引用、内存模型、STL常用容器实现原理搞清楚。第二轮是按真题模拟训练。找近三年的搜狗真题或其他互联网公司同类笔试题限时两小时完整做一遍。这一轮不需要追求满分重点是找到自己最薄弱的章节。做完之后把错题归到对应知识点比如链表错题、动态规划错题、网络错题方便下一轮针对性突破。第三轮是把错题重做一到两遍。别只看答案要亲手写代码反复调试到能独立通过测试用例。到了考场上这些被打磨过的肌肉记忆会救你命。7. 写在最后那份笔试题带给我的不止是Offer搜狗2016年的研发笔试题距离现在已经有些年头了但那套题带给我的启发到现在依然适用。它用一道道题告诉我研发工程师的基本功容不得半点侥幸链表反转、动态规划、内存管理、TCP协议这些知识不是考完就扔的东西而是日后每一天写代码都可能碰到的底层能力。我后来的教训是刷题的目的不是为了“押中题目”而是为了在紧张状态下依然能写出干净正确的代码。真正到了考场上你靠的不是临场发挥而是平时训练积累出的下意识反应。如果你正在准备互联网公司的研发工程师笔试建议把这篇内容里的题目亲手做一遍、把每个易错点都写进自己的错题本里。纸上得来终觉浅绝知此事要躬行。共勉。