前阵子翻云盘翻到一份2016年校招季的笔试存档里头正好有搜狗研发工程师的编程题记录。那会儿互联网公司笔试还没现在这么卷题目也不玩偏门怪招但恰恰是这种“看起来不难、做对不容易”的风格最能刷掉一批基础不扎实的人。当时我做完这套题最大的感受是搜狗作为搜索引擎公司出的编程题和它的业务气质高度一致——字符串处理、数组规律、TopK这类问题都是搜索和输入法场景里天天要碰的东西。这篇文章就把我回忆并重新整理的几道代表题完整拆一遍从题目分析、解法和现场踩过的坑都写清楚给正在准备研发岗笔试的同学做个参考。这套题很适合三类人看一是准备校招笔试的应届生拿来做算法基本功自测二是工作两年左右想跳槽到搜索、推荐、输入法这类业务线的朋友提前感受一下面试官对编码细节的偏好三是纯粹想巩固一下动态规划、桶排序、字符串翻转、快排partition这些经典知识点的读者。我尽量把每一步的“为什么”也讲明白而不是只丢一个答案。1. 先聊这套题的整体气质它到底在筛什么人搜狗2016年这批研发工程师笔试题整体难度放在今天来看不算高但非常“挑人”。和我同场笔试的人里有人四道题全部AC有人第一道就卡死在初始化上。区别不在智商而在平时写代码有没有养成边界意识。我按流传下来的题目和我自己的回忆挑了四道最有代表性的题题号核心考点涉及知识点难度1字符串最小编辑距离动态规划、滚动数组中等2排序后相邻元素最大差值桶排序思想、鸽笼原理中等偏难3句子单词倒置字符串处理、双指针简单4数组中第K大元素快速选择、堆中等这套题暗含的筛选逻辑有三层。第一层是“编码基本功”能不能在短时间内写出无语法错误、无逻辑漏洞的代码。第二层是“算法敏感度”看到题能不能迅速判断出该用什么数据结构和算法。第三层是“边界意识”空输入、单元素、重复值、极端大小——这些用例你是不是每次都会主动测试。搜索引擎这种业务线上对性能和正确率的要求都很高。一个查询词的编辑距离计算错一位搜索结果可能就完全跑偏。一个排序后的差值算错相关性排序的日志分析就会出问题。所以笔试题目看着基础背后考察的其实是候选人对细节的执拗程度。这个基调定了我们再逐题往下看。2. 第一题编辑距离动态规划里最值得背下来的入门题2.1 题目描述与业务背景题目的标准描述是这样的给定两个字符串A和B每次你可以对A执行三种操作之一——插入一个字符、删除一个字符、替换一个字符求把A变成B所需的最少操作次数。这就是经典的编辑距离问题也叫Levenshtein距离。为什么搜索引擎和输入法特别爱考这道题因为编辑距离在真实业务里太常用了。用户在搜索框里敲错字搜索引擎需要判断“昨天体闻”和“昨天新闻”之间差几次编辑操作从而决定要不要给纠错提示。输入法更需要实时计算用户输入拼音和目标词之间的编辑距离用来做候选取词。这个算法如果只会背模板、不懂状态转移笔试现场很容易在初始化环节翻车。2.2 状态定义与转移方程的推导编辑距离的标准解法是二维动态规划。定义dp[i][j]表示A的前i个字符转换成B的前j个字符需要的最少操作次数。这里注意dp[0][j]和dp[i][0]的初始化是很多人的第一个坑——空字符串变成j个字符只能靠连续插入j次所以dp[0][j] j同理dp[i][0] i。状态转移分两种情况如果A[i-1] B[j-1]当前两个字符已经一样不需要额外操作所以dp[i][j] dp[i-1][j-1]。如果两个字符不等就需要在删除、插入、替换三者中选代价最小的dp[i][j] 1 min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])dp[i-1][j]对应“删除A的第i个字符”dp[i][j-1]对应“在A的末尾插入B的第j个字符”dp[i-1][j-1]对应“把A的第i个字符替换成B的第j个字符”。这个逻辑想清楚整道题就通了。2.3 参考实现与滚动数组优化我当年笔试直接用二维数组写代码清晰但浪费空间。后来整理题解时优化成了滚动数组只需要两行其实一行也够。这里给出Python版本def min_edit_distance(a, b): m, n len(a), len(b) # 空间优化保证外层循环遍历较长的字符串 if m n: a, b b, a m, n n, m dp list(range(n 1)) for i in range(1, m 1): prev dp[0] dp[0] i for j in range(1, n 1): temp dp[j] if a[i - 1] b[j - 1]: dp[j] prev else: dp[j] 1 min(dp[j], dp[j - 1], prev) prev temp return dp[n]滚动数组的写法里最关键的是prev变量保存的是dp[i-1][j-1]。很多人在内层循环更新完dp[j]之后才发现原来dp[i-1][j-1]已经被覆盖了。我在笔试时就是在这里卡了十分钟最后老老实实回到二维数组版本才AC。后来总结出一个经验除非时间非常紧张否则笔试时先用最直观的二维数组写出正确代码AC之后再考虑优化空间。2.4 复杂度和边界用例时间和空间复杂度都是O(mn)滚动数组优化后空间是O(min(m,n))。笔试时如果字符串长度在1000以内二维数组完全够用如果到10000就要考虑滚动数组。还有一个不起眼的边界如果输入的两个字符串都为空dp初始是[0]循环不会执行直接返回0恰好是正确答案。自测用例建议覆盖这些场景(, )返回0(abc, abc)返回0(kitten, sitting)返回3经典用例(, abc)返回3(abc, )返回3其中“kitten到sitting”这个用例是我每次写完都要跑的它能同时验证插入、删除、替换三种操作是否都正确处理。如果输出不是3说明转移方程里某个分支写错了。3. 第二题数组排序后相邻元素最大差值桶思想才是真正的考点3.1 题意和直觉上的陷阱题目描述很简洁给定一个无序数组如果把它排序求排序后相邻两个数之间差值的最大值要求时间复杂度O(n)。举个简单例子数组是[3, 6, 9, 1]排序后是[1, 3, 6, 9]相邻差分别是2、3、3最大值是3。很多人第一反应是“这不就排序后遍历一遍嘛”但题目明确要求O(n)的时间复杂度。用快排的话最好情况O(n log n)不满足要求。这题的真正考点是能不能想到用桶排序的思路在不用全局排序的前提下只比较相邻桶之前的差值。3.2 桶的设计为什么能保证不漏答案核心思路是找出数组的最小值min和最大值max把区间[min, max]均匀分成n1个桶n是数组长度。每个桶只记录落入该桶元素的最小值和最大值。因为有n1个桶、n个元素根据鸽笼原理必然存在至少一个空桶。空桶的存在是整个算法的灵魂。它保证了两件事一是同一桶内元素之间的差值一定小于桶的跨度二是排序后的最大差值一定发生在跨桶的相邻元素之间而不可能出现在同一个桶内部。所以只需要按顺序遍历所有非空桶计算“当前桶的最小值 - 上一个非空桶的最大值”取其中的最大值即可。这里要特别注意不是单纯比较“相邻的两个桶”而是要跳过中间连续的空桶。我最初写的时候只比较了物理相邻的桶结果把中间隔着三个空桶的更大差值漏掉了。因为相邻非空桶可能中间夹着多个空桶只有用“上一个非空桶的max”和“当前非空桶的min”做差才能把空桶跨度算进去。3.3 参考实现def max_gap(nums): n len(nums) if n 2: return 0 min_val, max_val min(nums), max(nums) if min_val max_val: return 0 bucket_size max(1, (max_val - min_val) // n) bucket_count (max_val - min_val) // bucket_size 1 bucket_min [float(inf)] * bucket_count bucket_max [-float(inf)] * bucket_count has [False] * bucket_count for v in nums: idx (v - min_val) // bucket_size if idx bucket_count: idx bucket_count - 1 bucket_min[idx] min(bucket_min[idx], v) bucket_max[idx] max(bucket_max[idx], v) has[idx] True ans 0 prev_max bucket_max[0] for i in range(1, bucket_count): if has[i]: ans max(ans, bucket_min[i] - prev_max) prev_max bucket_max[i] return ans代码里有几个细节值得展开。bucket_size max(1, (max_val - min_val) // n)这行是防止当数组元素全部集中在一个很小的区间时除法结果变成0。比如[1, 2, 3, 4]max-min3n4直接整除得到0桶大小就非法了必须保底为1。第二个细节是idx的处理。理论上max_val计算出来的桶下标可能正好等于bucket_count需要做一次越界修正。我在本地跑的时候没注意结果用[1, 2, 3, 100]测试时直接IndexError这个坑算是比较隐蔽的。3.4 易错点与实战体会这道题在笔试现场的错误率很高主要原因是“知道要用桶但不会设计桶”。我见过不少同学把桶设计成固定大小比如每10个数一个桶然后纠结桶的数量怎么确定。实际上桶的大小和数量都跟数组长度n挂钩这是保证鸽子笼原理成立的关键。另一个容易出错的地方是“同桶内的元素是否需要比较”。因为空桶一定存在所以同桶内的差值永远不会成为全局最大值这一点需要理解透。如果你只是背代码而不懂原理面试官追问一句“为什么同桶内不用比较”很容易支支吾吾答不上来。自测用例建议[1, 1, 1, 1]所有元素相等返回0[1, 100]只有两个元素返回99[3, 6, 9, 1]返回3[1, 2, 3, 4]返回1此时所有元素都落入不同桶[1, 10, 100, 1000]返回900跨越多个空桶其中[1, 100]这种情况最容易被忽略因为n2时桶数量计算、循环逻辑都要额外验证一下。4. 第三题句子单词倒置字符串题里最容易丢分的边界战4.1 题意和最简单的解法这道题描述很简单输入一个英文句子比如“I am a student.”要求输出“student. a am I”单词内部字符顺序不变单词之间用空格分隔。有的版本会要求压缩多余空格去掉首尾空格。最直接的解法就是先按空格切分单词再把单词列表反转重新用空格拼接。Python里可以写得非常短def reverse_sentence(s): return .join(s.strip().split()[::-1])但我必须强调这种极简写法在笔试里未必是加分项。如果题目要求“不开辟额外空间”你必须用双指针或者两次翻转的写法。笔试平台一般会检查用例输出但面试官后续追问“你的空间复杂度是多少”时split会暴露你对底层内存分配的不敏感。4.2 用两次翻转解决空间问题如果不想额外开辟单词数组可以用经典的“先整体翻转再逐个单词翻转”思路。比如原串是“I am a student.”先整体翻转变成“.tneduts a ma I”然后把每个单词的内部字符再翻转一次就变回“student. a am I”。这个思路需要自己写一个翻转函数同时维护单词的起始和结束下标。def reverse_words(s): s s.strip() arr list(s) n len(arr) def reverse_range(left, right): while left right: arr[left], arr[right] arr[right], arr[left] left 1 right - 1 reverse_range(0, n - 1) start 0 for i in range(n 1): if i n or arr[i] : reverse_range(start, i - 1) while i n and arr[i] : i 1 start i return .join(arr)这版代码里用了一个关键技巧在for循环里手动跳过连续空格同时更新下一个单词的起点。如果不跳过连续空格多个空格会把空串当成一个“单词”翻转后出现多余的空格。4.3 边界条件这道题真正的分数分割线字符串处理题最怕的不是主逻辑写不出来而是边界用例没想到。我整理了当年踩过的坑空字符串输入输出也是空字符串。很多写法在strip()之后得到空串再split()得到空列表最终返回空串这没问题。但如果你直接对空串做reverse_range(0, n - 1)n-1是-1会直接报错。全是空格的字符串strip()后也是空串必须单独处理。首尾有空格、单词之间多个空格先strip()再split()可以自动压缩多余空格但这依赖语言库的实现。C里用istringstream很舒服Java里可以用trim().split(\\s)。标点符号如逗号、句号、引号和单词连着必须跟着单词走不能单独拆出来。比如“Today is a good day, right?”翻转后逗号和right不能分开。当时和我一起笔试的同学主逻辑写对了恰恰挂在“首尾空格”这个用例上。搜狗这套题里的字符串题输入用例大概率就包含这种边界所以建议拿到题先别急着写代码花一分钟把“空串、单空格、多空格、首尾空格、标点”这几个测试用例在心里过一遍。4.4 为什么这道简单题也有区分度单词倒置在很多题库里被标为“简单”但笔试场景下的简单题往往不是送分题而是“陷阱题”。简单题的区分度在于你能不能一次性写对。因为大家都会做只要错一个用例排名就掉下去。我在那次笔试里这道题反而花了最多时间做自测因为我有预感越简单的题测试用例越刁钻。如果这道题你五分钟写完且一次通过说明你的字符串处理基本功很扎实这三分钟就能拿到手的分算是稳了。如果卡在空格处理上后面的难题心态也会受影响。5. 第四题第K大元素partition和堆两种姿势选哪个5.1 题目描述与高频变形题目描述给定n个整数找出其中第K大的数。比如数组[3, 2, 1, 5, 6, 4]K2第2大的数是5。这个题在LeetCode上是215题但在2016年的笔试年代它已经是各大公司笔试题库里的常客了。搜狗把它放在编程题里一点都不意外因为排序、TopK、海量数据处理都是搜索引擎后端经常要面对的问题。限制条件通常有两类一类是n比较大要求时间复杂度O(n)另一类是K比较小要求空间复杂度优化。这两种限制对应两种主流解法快速选择算法和维护大小为K的小顶堆。5.2 快速选择基于快排partition的期望O(n)解法快速选择的核心是复用快排的partition操作。我的做法是以数组最右边的元素为基准把大于基准的元素放到左边小于基准的放到右边返回基准最终所在的位置p。如果p正好是第K大元素的位置直接返回如果p在K的左边说明第K大元素在右侧区间如果在K的右边则在左侧区间继续找。def partition(nums, left, right): pivot nums[right] i left for j in range(left, right): if nums[j] pivot: nums[i], nums[j] nums[j], nums[i] i 1 nums[i], nums[right] nums[right], nums[i] return i def quick_select(nums, left, right, k): if left right: return nums[left] p partition(nums, left, right) rank p - left 1 if rank k: return nums[p] if rank k: return quick_select(nums, p 1, right, k - rank) return quick_select(nums, left, p - 1, k)这里最容易写错的点是rank的语义。我以“从大到小”的方式做partition那么rank表示当前元素在区间内是第几大。如果rank k说明第K大的数在右半部分而且只用在右半部分找第k - rank大。如果rank k说明第K大的数在左半部分K不需要变因为左半部分的元素都大于基准。我当年第一次写时把“第K大”和“第K小”搞混了导致partition里的大于小于号全写反。这个错误很难通过肉眼看出来因为你测试[3,2,1,5,6,4]K2时结果可能刚好撞对了换一组数据就错。建议写完后用一个乱序数组多测几个K值。5.3 堆解法代码更稳适合K远小于n的场景如果K很小用堆更稳妥。做法是维护一个大小为K的小顶堆遍历数组时如果当前元素比堆顶也就是当前K个最大元素里的最小值还要大就把堆顶弹出把当前元素放入。遍历结束后堆顶就是第K大的数。import heapq def find_kth_largest(nums, k): heap [] for v in nums: if len(heap) k: heapq.heappush(heap, v) elif v heap[0]: heapq.heapreplace(heap, v) return heap[0]堆解法的时间复杂度是O(n log K)空间复杂度O(K)。它的好处是代码短、不容易写错而且在海量数据场景下不需要一次性把所有数据加载到内存——这点其实很贴合搜索引擎处理海量日志的场景。快速选择的期望复杂度虽然更优但最坏情况是O(n²)而且递归深度可能很大笔试平台的递归栈在某些语言里会爆。5.4 边界情况与笔试选择的建议这道题的边角案例很值得单独列一下K1返回最大值Kn返回最小值。这两个极端如果代码里的下标处理不好很容易越界。K比n还大属于非法输入。笔试题目一般不考这个但如果你写函数时留了参数校验面试官会高看你一眼。数组里有大量重复值。比如[5,5,5,5]K2第2大还是5。partition处理重复值时可能退化成O(n²)需要一定的优化思路。数组只有一个元素K1直接返回这个元素。这个用例用来检验递归出口。我的实战建议是笔试时优先写堆解法因为正确性更容易保证如果题目明确要求O(n)的时间复杂度再考虑写快速选择并且要意识到随机化pivot的重要性。我在搜狗那套题里用的是快速选择的非递归写法避免递归过深导致栈溢出。非递归写法就是用while循环不断缩小区间取代递归调用代码稍长但更稳。非递归版本的思路是维护left和right两个指针循环里不断partition然后根据rank和k的关系收缩区间直到区间长度为1或者找到目标。这样写的好处是不会有递归爆栈的担忧笔试题里n如果真的给到十万甚至百万也能扛得住。6. 笔试实战最容易被忽略的细节时间分配、平台格式、自测清单6.1 时间分配先暴力拿分再优化拿满意度搜狗当年的编程题大概是3到4道时间两个小时左右。我自己的策略是每道题先保证写出一个正确但可能不是最优的解法测试用例通过后再考虑优化。比如编辑距离这道题先用二维DP写下AC如果还有时间再改成滚动数组版本。第K大这道题先用排序nums.sort()取第n-k个元素搞定如果题目不要求复杂度这已经能通过大部分测试用例。不少人一上来就挑战最优解结果卡在细节上最后连最基础的实现都没交上去。笔试平台是按通过用例数给分的部分AC永远比零分强。除非每道题难度都很大、题目数量有限否则我不建议在一道题上死磕超过40分钟。6.2 笔试平台的坑输入输出格式比算法更容易翻车互联网公司笔试题大多在牛客网或者赛码网这类在线评测系统上做。这类平台最让人头疼的地方是输入输出格式。搜狗当年的题目有的要求读入多组测试数据有的要求先读入n再读入数组输出时不能有多余空格和换行。我用Python写的时候经常因为忘了sys.stdin.readline()会带换行符而出现空白字符不匹配。建议平时练习时尽量用在线评测平台的模拟环境跑一遍确认以下几点第一行是单个整数还是多个整数是测试用例组数还是数组长度第二行数组元素之间用什么分隔符空格还是逗号输出结果后要不要换行能不能一次读取所有输入sys.stdin.read()和sys.stdin.readline()的区别是否清楚我记得当年有人在第K大那道题的输出行尾多打了一个空格被判WA这种错误真的非常可惜。6.3 我能给的一份通用自测清单笔试写完代码不要急着提交。花三分钟做一轮自测优先级从高到低排列空输入空字符串、空数组、n0。很多代码在空输入时会直接抛异常。单元素输入一个字符串、一个整数的数组。这类用例能测试出循环边界和递归出口是否正确。重复值所有元素相等、包含大量重复元素。能测试出partition在重复元素上的退化问题。极值最大整数、最小整数、字符串长度为零。能测试出是否发生溢出或越界。格式要求首尾空格、输出换行、多余分隔符。这个清单是我被牛客网和赛码网虐出来的经验之谈。每次做笔试我都先花时间跑这几个用例再点提交整体的AC率明显提升。特别是像单词倒置和最大差值这类题边界用例往往就是区分满分和零分的关键。实际写这套题时我的心态是“能做对不算本事能在边界条件下依然做对才算本事”。这句话后来也一直是我做技术题、写生产代码的准则。如果你正在准备笔试不需要刷几千道题把这些经典问题的原理吃透、边界练熟比盲目堆题量有效得多。