Google 2011笔试卷这套题在算法面试圈里流传了十几年到现在还有不少人专门翻出来重刷。原因很简单它考的不是偏题怪题而是算法思维最底层的东西——二分、分治、动态规划、概率推导、系统估算。我当年准备面试的时候刷过这套流传题后来带团队面试新人时也经常从里面挑题目做考察。这试卷最迷人的一点是明明题目数量不多但每一道都能往深处挖出好几层挖到后面你会发现它考的已经不只是一道算法题了而是你面对未知问题时的思维路径。当时Google笔试的传统是算法题为主、概率题为辅偶尔夹杂一道系统设计或者开放思考题。它不要求你用某种特定语言也不考框架、库、API记忆因为这些东西一两年就会变但算法和数据结构的底层逻辑不会变。这套试卷放到今天依然很适合拿来检验自己的基本功。如果你正在准备大厂技术面试或者想系统性强化算法思维这期内容值得花一个下午认真过一遍。1. 2011年Google笔试卷的题型地图它到底在考什么1.1 为什么2011年的题目至今还有人重刷2011年前后正是Google在国内大规模校招比较活跃的时期笔试题风格很统一题量不大但每道题都像冰山表面看起来是个经典题底下埋着复杂度分析、边界条件、概率推导这些硬功夫。这套题的生命力在于它的通用性。跟现在很多公司的笔试题不同它不依赖任何语言特性C能写、Java能写、Python能写甚至用伪代码也不会被扣分。因为考官真正想看的是你的思路怎么展开、复杂度怎么分析、边界条件怎么覆盖。语言只是一个载体。另外一个原因是这些题目的变体至今还在各大厂的笔试题里出现。比如从一个有序矩阵里找目标值比如求第K大元素比如字符串编辑距离这些题目在LeetCode上都有对应的热门题但2011年的笔试卷把它们组合在一起形成了一种独特的考察密度短短两小时内你要在数组、字符串、概率、海量数据之间来回切换。1.2 当年的题型分布与能力模型根据当时流传出来的多个版本2011年Google笔试卷大致可以归纳为以下几类题型典型代表考察能力难度感受数组/查找二维有序矩阵查找、第K大元素二分思想、划分解法、复杂度分析中等容易在边界上翻车字符串/DP编辑距离、最长回文子串状态定义、转移方程、空间优化中高需要系统训练数据结构链表反转、判断链表是否成环指针操作、快慢指针中等考察代码基本功概率/数学用rand5生成rand7、洗牌算法概率推导、均匀性证明高很多人直接卡住海量数据/设计100亿个整数找前K大、短网址系统内存估算、分治思想、系统分层高考察综合素养这套试卷的聪明之处在于它不搞题海战术而是用少量题目覆盖多个维度。你算法题做得快概率题可能卡住你概率题推得顺系统设计题又可能不知道怎么开口。这就是Google想要的效果——它要找的不是某一项特别强的专才而是各项能力均衡、且在压力下仍然能保持清晰思路的工程师。2. 算法题拆解二维矩阵查找、第K大和编辑距离的“最优解路径”2.1 二维有序矩阵查找为什么起点必须是右上角题目描述很简单有一个 m x n 的矩阵每一行从左到右递增每一列从上到下递增给定一个目标值 target判断矩阵中是否存在这个数。很多人的第一反应是从左上角开始。左上角是整个矩阵的最小值如果当前值比target小那么有两个方向可以走——向右或者向下两条路都可能有目标值这就会导致搜索出现分支时间复杂度退化。所以左上角不是好的起点。正确的出发点是右上角。右上角的元素有一个性质它是当前行的最大值当前列的最小值。这就构成了一个完美的决策点如果当前值大于 target因为它是这一行的最大值说明整行都大于 target可以排除当前行指针向下移动一行。如果当前值小于 target因为它是这一列的最小值说明整列都小于 target可以排除当前列指针向左移动一列。每走一步要么排除一行要么排除一列最多走 mn 步就能完成搜索时间复杂度 O(mn)空间复杂度 O(1)。def search_matrix(matrix, target): if not matrix or not matrix[0]: return False rows, cols len(matrix), len(matrix[0]) row, col 0, cols - 1 while row rows and col 0: if matrix[row][col] target: return True elif matrix[row][col] target: col - 1 else: row 1 return False这题的坑点在于很多人理解了“从右上角出发”之后却在循环条件的边界上出错。注意row rows和col 0两个条件缺一不可一旦出现死循环先检查是不是少了某个边界判断。还有一个常见错误是混淆行和列的方向目标值比当前值大时应该往下走行增加目标值比当前值小时应该往左走列减少方向搞反就全错了。题目可以有很多变体如果左下角开始道理相同只是移动方向相反。如果问的是矩阵中有多少个元素小于某个值同一套排除逻辑也能用来做计数。这个“排除法”的思路在处理二维有序数据时非常通用。2.2 第K大快排partition思想与边界条件题目给定一个无序整数数组找出其中第K大的数。最容易想到的办法是把数组排序然后直接取下标 n-K 的元素时间复杂度 O(n log n)。但这道题的期望解法是 O(n) 的快速选择算法Quick Select利用快排的 partition 思想。每一次 partition 会确定一个元素在有序数组中的最终位置 pivotIndex。如果 pivotIndex 恰好等于 n-K那么 arr[pivotIndex] 就是第K大的数如果 pivotIndex 小于 n-K说明目标在右半部分只需要递归处理右半部分反之则处理左半部分。public int findKthLargest(int[] nums, int k) { int targetIndex nums.length - k; int left 0, right nums.length - 1; while (left right) { int pivotIndex partition(nums, left, right); if (pivotIndex targetIndex) { return nums[pivotIndex]; } else if (pivotIndex targetIndex) { left pivotIndex 1; } else { right pivotIndex - 1; } } return -1; } private int partition(int[] nums, int left, int right) { int pivot nums[right]; int storeIndex left; for (int i left; i right; i) { if (nums[i] pivot) { swap(nums, storeIndex, i); storeIndex; } } swap(nums, storeIndex, right); return storeIndex; }平均时间复杂度是 O(n)因为每次 partition 之后只需要处理一边整体的工作量是 n n/2 n/4 ...收敛到 2n。但最坏情况下比如每次选的 pivot 都是最大值或最小值复杂度会退化成 O(n^2)。解决办法是引入随机化 pivot或者使用 BFPRT 算法保证最坏 O(n)。这题的实际工程价值也很高。TopK 问题在大数据领域无处不在——电商系统要统计销量前100的商品监控系统要找访问量最高的接口搜索引擎要取相关性最高的网页。笔试考这道题不只是考算法本身更是在考察你有没有遇到“数据量超过内存”时的分治意识。后面第4部分我会专门讲海量数据场景。2.3 编辑距离从暴力递归到动态规划的思维跃迁这道题在Google笔试卷里出现过难度明显比前两道高。题目描述给定两个字符串 word1 和 word2你可以对一个字符串执行三种操作——插入一个字符、删除一个字符、替换一个字符求将 word1 变成 word2 的最少操作次数。暴力解法是递归枚举所有可能操作指数级复杂度字符串稍长就爆炸。正确做法是动态规划。定义 dp[i][j] 表示 word1 的前 i 个字符转换成 word2 的前 j 个字符所需的最少操作次数。转移方程需要仔细推导。当 word1[i-1] word2[j-1] 时当前字符不用操作dp[i][j] dp[i-1][j-1]。不相等时有三种选择插入在 word1 的前 i 个字符后插入一个字符使其匹配 word2[j]对应 dp[i][j-1] 1。删除删除 word1 的第 i 个字符对应 dp[i-1][j] 1。替换把 word1 的第 i 个字符替换成 word2 的第 j 个字符对应 dp[i-1][j-1] 1。三者取最小。def min_distance(word1, word2): m, n len(word1), len(word2) dp [[0] * (n 1) for _ in range(m 1)] for i in range(m 1): dp[i][0] i for j in range(n 1): dp[0][j] j for i in range(1, m 1): for j in range(1, n 1): if word1[i - 1] word2[j - 1]: dp[i][j] dp[i - 1][j - 1] else: dp[i][j] min( dp[i - 1][j] 1, # 删除 dp[i][j - 1] 1, # 插入 dp[i - 1][j - 1] 1 # 替换 ) return dp[m][n]这题的难点不在写代码而在于状态定义。很多人能从直觉上感觉到要用DP但定义不好状态转移方程就无从谈起。我的经验是遇到字符串比较类问题先考虑二维DPdp[i][j]一般是“前i个字符和前j个字符的关系”然后尝试写转移方程如果写不通再回头调整状态定义。工程上编辑距离的用途极广搜索框的拼写纠错、DNA序列比对、代码diff工具、语音识别结果纠错都是它的变体。我早期做搜索业务时就被要求实现一个“用户输入了错别字也能召回正确结果”的纠错模块底层就是编辑距离加上一个候选词表。笔试里的算法题很多都有这样的工程投影。3. 概率题的数学底子rand5生成rand7与洗牌算法的均匀性证明3.1 用rand5()生成rand7()拒绝采样背后的概率推导这道题在Google笔试里出现过多个版本核心思路是一样的。题目假设你已经有一个函数 rand5()它能等概率生成1到5之间的整数请你用这个函数实现 rand7()等概率生成1到7之间的整数。很多人第一想法是先把5个数直接映射到7个数比如rand5() 2之类的但这立刻就会破坏均匀性。正确的思路是拒绝采样Rejection Sampling。第一步用 rand5() 构造出一个更大的均匀分布空间。表达式(rand5() - 1) * 5 rand5()能等概率生成1到25之间的所有整数。为什么是均匀的因为两个 rand5() 相互独立每个组合出现的概率都是 1/25所以映射到1到25之间的每个整数概率也是1/25。第二步把1到25分成两部分1到21映射成1到7每个数对应三个原始值22到25拒绝并重试。这样1到7每个数字出现的概率就是 3/25 / (21/25) 1/7均匀性得到了保证。import random def rand5(): return random.randint(1, 5) def rand7(): while True: num (rand5() - 1) * 5 rand5() if num 21: return (num - 1) % 7 1这道题的期望调用次数是一个很容易被追问的点。每次采样的成功率是 21/25失败后重新采样所以采样次数的期望是 25/21 ≈ 1.19 次每次采样调用2次 rand5()总期望调用次数约为 2.38 次。理解拒绝采样之后可以秒答扩展题如果给你 rand7()要你实现 rand5()怎么做更简单——调用 rand7() 直到结果在1到5之间就返回期望调用次数是 7/5 ≈ 1.4 次。如果要求更大范围比如 rand11() 生成 rand13()思路完全一样关键在于构造一个均匀的大空间然后选取目标范围的整数超出部分丢弃。这种题在笔试中出现的价值在于它不考你背代码而是考你有没有概率直觉。很多候选人经提醒能写出代码但说不清楚为什么均匀这种回答在面试官眼里是要打折扣的。3.2 Fisher-Yates洗牌均匀随机排列的合法性证明洗牌算法看起来简单实际上坑很多。题目通常是这样给定一个数组要求随机打乱顺序并且每个排列出现的概率都相等。最常见的错误答案是给每个元素赋一个随机数然后按随机数排序。这种做法有两个问题。第一排序复杂度是 O(n log n)不如最优解 O(n)。第二更致命的是用随机比较器排序会导致结果不均匀——某些排列出现的概率远高于其他排列。很多实现里随机数产生随机比较时排序结果的分布是倾斜的不是均匀的。正确的算法是 Fisher-Yates shuffle也叫 Knuth shuffle。核心过程从数组末尾开始每次在 [0, i1) 范围内随机选一个下标 j然后交换 arr[i] 和 arr[j]。i 从 n-1 递减到 1。import random def shuffle(arr): n len(arr) for i in range(n - 1, 0, -1): j random.randint(0, i) arr[i], arr[j] arr[j], arr[i] return arr为什么这个算法是均匀的我们来做一个归纳证明。第一次迭代随机从n个元素中选一个放到最后一位每个元素成为最后一位的概率是 1/n。第二次迭代从前 n-1 个元素中随机选一个放到倒数第二位每个元素成为倒数第二位的概率是 ((n-1)/n) * (1/(n-1)) 1/n。依此类推最终每个元素出现在任意位置的概率都是 1/n每个排列的概率都是 1/n!。这里的关键点在于概率的独立性每次选择都在剩余未确定的位置中进行不会影响已经确定的位置。算法从后往前走因为每次都把当前选中的元素固定在最右边的未处理位置上这个位置以后不再参与后续交换。Fisher-Yates在实际工程中应用极广在线音乐播放器的随机播放、A/B测试的实验分组、机器学习训练数据的打散、推荐系统的候选集采样。我自己在做广告排序时经常需要从候选广告池中按特定概率抽取样本做评估底层就是 Fisher-Yates 的带权变体。4. 海量数据与系统设计题的答题框架从内存约束到分治估算4.1 从内存约束反推算法海量数据题的通用思路Google笔试里有一类题是直接描述海量数据场景的100亿个整数找出其中最大的前100个或者给定一个包含100亿条URL的文件统计出现次数最多的前10个URL。这类题目的核心挑战不是算法本身而是数据量远超内存。遇到这种题第一个动作永远是估算。100亿个整数如果每个int占4字节总共约40GB这在2011年已经远超一台普通服务器的内存今天的机器强一些但也不会拿40GB内存只为了存一组原始数据做简单排序。所以第一步判断就是内存装不下必须做分治。通用的解法是哈希分片。用一个哈希函数把每个数据映射到不同的文件比如对整数直接取模对URL字符串算哈希后取模。分片之后每个文件的数据量就缩小到了一个可处理的范围。假设内存可用2GB把40GB的数据哈希到200个文件每个文件约200MB完全能加载进内存。分片完成之后每个文件独立求解。找最大前100个就在每个文件内部用小顶堆大小为100维护前100大然后合并各文件的结果统计URL次数就先在每个文件内用HashMap统计出现次数再合并每个文件的Top10列表。这里必须注意的一个点是为什么一定要用哈希函数而不是随机分配因为同一个数据经过同一个哈希函数一定会被分到同一个文件中。如果随机分配同一个URL可能出现在多个文件中统计次数时就会重复计算破坏全局正确性。哈希分片的本质是让“相同元素”落到同一个桶里这才是分治算法正确性的前提。还有一个容易被忽略的工程细节哈希分片之后单个文件可能仍然过大。比如URL分片时如果某个哈希桶里恰好聚集了大量数据这个文件的规模还是远超内存。这种场景下需要对超大的文件再做一次二级哈希或者换用不同的哈希函数重新分片。这就像数据库的分库分表如果某几个用户的数据量特别大就会出现数据倾斜需要进一步拆分。笔试题的答题时间有限但如果你能主动提到“数据倾斜”这种边界情况面试官对你的评价会明显高一个档次。4.2 设计短网址系统笔试里少见的开放题怎么拿分Google的笔试卷里偶尔会出现一道开放系统设计题短网址系统就是经典中的经典。这种题的特点是没有标准答案但考察你有没有一套清晰的答题框架。短网址系统的本质很简单把长URL映射成一个短的唯一ID用户访问短ID时服务端查询映射关系并重定向到长URL。核心问题有三个短ID怎么生成、映射关系怎么存储、重定向时选择什么状态码。短ID生成的主流方案有两种。一是发号器方案用一个全局自增ID生成器比如数据库自增ID或雪花算法生成唯一ID然后把十进制ID转成Base62编码0-9a-zA-Z共62个字符长度6到8位能覆盖几百亿的URL。二是哈希方案对长URL做MD5或SHA1哈希截取前几位作为短ID但哈希存在碰撞的可能需要额外的碰撞检测和冲突处理机制。两种方案对比发号器方案更可控生成速度快不会碰撞是业界主流。存储层选择KV数据库比如Redis或Bigtable这类系统以短URL作为key长URL作为value。由于短网址服务是典型的读多写少场景——每次访问都需要查询但新URL的创建频率远低于访问频率所以需要引入缓存层。通常就是Redis做一层缓存热点短URL直接命中缓存不落数据库。这里有一个经常被追问的细节重定向应该返回301还是302。301是永久重定向浏览器会缓存这个跳转关系第二次访问直接不再请求服务器302是临时重定向每次访问都会经过服务器。从用户体验上看301更省资源但从运营和统计角度302更合适因为它让每次点击都能被记录方便做点击统计和来源分析。我当年在面试时重点提了一句“选择302是因为需要统计点击量”面试官明显态度更好——这说明你不只是在做技术而是在做产品决策。容量估算也可以简单说两句假设每天新增1000万个URL一年新增36.5亿条存储用KV数据库每条记录几十字节一年大约几十GB完全可控。QPS方面假设峰值1000次访问每秒Redis单机就能扛住大数据量后再做分片。这类题在笔试卷里不常见但一旦出现就是拉开差距的地方。算法题大家都会做系统设计题却能真实反映一个人有没有工程经验、有没有系统思考能力。5. 这些老题对今天准备技术面试还有多大用处5.1 从笔试到面试Google考察风格的延续与变化2011年之后的十多年里Google的面试体系经历了多次演进。从最初的纯算法笔试题逐渐发展成算法、系统设计、Go/工程能力、行为面试等综合流程。现在的面试更加强调与面试官的实时互动候选人需要边思考边讨论而不是闷头写代码。但核心的思维模式没有变把复杂问题拆解成小问题、对复杂度保持敏感、对边界条件有洁癖。2011年笔试卷上的这些算法题后来大量演变成了LeetCode上的高频题也沉淀为各家大厂面试题库的基本盘。二维矩阵查找对应LeetCode 240第K大对应LeetCode 215编辑距离对应LeetCode 72洗牌算法对应LeetCode 384。可以说这套老卷子是一份浓缩的面试题纲。我见过不少人有一种误解觉得“老题已经过时了大厂肯定考新题”。但实际情况是大厂题库的更新频率远没有大家想得那么快尤其是算法基础题翻来覆去就是那几类核心解法。真正变化的是提问方式和服务端场景的包装但底层永远是二分、DP、分治、贪心、图论这些地基。5.2 今天刷2011年笔试卷的正确姿势如果你准备用这套题来备战我的建议是不要直接对着答案看。先用一小时模拟笔试把每一道题都当作真正的考试来对待。做完之后重点不是对答案而是复盘每一步的“为什么”。我自己带候选人时经常做的事是让他们把每道题的解法讲给我听尤其是讲解法里那些关键选择。比如“为什么这个DP的状态定义是二维的”“为什么从右上角开始而不是左上角”“为什么这个算法平均复杂度是O(n)”能回答清楚这些说明你掌握了题目的本质如果只能说“这个题LeetCode上这么写”那就还需要深挖。刷题之外代码规范也值得单独花时间。Google对代码风格的执念是出了名的从笔试题就能看出端倪变量命名要语义清晰类名用大写开头函数名用动词开头变量名用小写加下划线这是Google C Style Guide的基本要求。即使现在写Java或Python这种命名习惯也会让面试官觉得你受过专业训练。另外Google的开源项目里Guice依赖注入框架和MediaPipe机器学习推理框架都是很好的学习素材——它们的代码组织方式、接口设计思路都体现了Google工程师的审美。如果你面试的是后端或机器学习相关的岗位面试官很可能会参考你对这类项目的理解程度。刷完这套题之后可以给自己做一个迁移练习把每个算法题对应到真实工程场景。第K大对应监控系统的TopK告警编辑距离对应搜索词纠错洗牌算法对应A/B测试随机分组海量数据分片对应数据库分库分表短网址设计对应一切KV服务的架构思路。这种迁移能力才是面试官真正想看到的。每次看这套题我都能感受到一个朴素的道理技术框架会过时工具链会迭代但底层算法思维永远保值。十几年前考的是这些东西十几年后大厂面试核心还是这些东西。与其追新题、背模板不如静下心把每一道经典题的推导过程吃透。我自己带团队这些年最后筛掉的人往往不是算法题做不出来而是讲不清自己写出来的代码为什么要这么写。理解背后的逻辑远比堆积题目数量重要。