Google 2011笔试卷复盘：算法、系统设计与工程思维

前几天整理旧硬盘，翻出一份2011年的Google笔试卷电子版。看着那些熟悉的题目，我愣是坐那儿看了半小时——不是怀旧，是真的感慨：十几年过去了，互联网公司的面试题换了一茬又一茬，但Google这套笔试卷里的核心考点，依然能在今天各大厂的题库里找到影子。很多人把它当成“上古文物”，其实它更像是大厂技术面试的“源代码”。

这份试卷最吸引我的地方，是它几乎不考任何“背了就会”的知识，而是把算法、工程、概率和系统设计揉在了一起。当年我拿到卷子的时候，第一反应是“这也能在纸上写完？”，后来才明白，它要的不是一个答案，而是你思考问题的全过程。这篇文章我就以亲历者和面试官的双重视角，把这份卷子里最有含金量的几类题拆开揉碎，讲讲它们背后的出题逻辑、最优解推导，以及在真实工程里到底有什么用。

1. 整体思路拆解：Google 2011笔试卷的考察模型

1.1 题型配比与考察重点

先说一个很多第一次接触这套题的人都会问的问题：Google笔试到底考什么？2011年前后，Google的笔试以算法编程题为主，通常1.5到2小时，5到7道题，配比大概是这样：

• 算法题占60%到70%，集中在数组、链表、树、字符串和动态规划；
• 系统设计或开放设计题占15%到20%，只给场景，不给标准答案；
• 语言与工程细节占10%左右，比如C++的内存管理、Java的集合类、代码风格；
• 剩下少量的数学或概率题，用来考察思维的严密性。

这个比例放到今天依然成立，但2011年更强调“硬算法”，没有太多项目和系统深挖的环节。原因是Google当年的招聘量远小于投递量，必须用一套标准统一、机器可评判的方式来初筛候选人。算法题天然适合这个场景：对就是对，复杂度高就是高，边界没处理就是没处理。

还有一个容易被忽略的点：这份试卷不考“你用过什么框架”，也不考“你记得哪个API”。它考的是脱离工具之后，你的底层能力还剩多少。这跟今天很多大厂面试第一轮考算法题的逻辑一脉相承——框架可以速成，算法底子和逻辑思维短期内提不上去。

1.2 一道题背后的“三层考察”

看这份试卷不能只看题目本身，要看出题人埋在下面的考察点。我习惯把一道题拆成三层：

第一层是“能不能解出来”。这层只区分会与不会，暴解也算解。但Google很鸡贼，它会在题目描述里加限制条件，比如“要求O(log(m+n))”“尽量让空间复杂度为O(1)”，逼你走出舒适区。

第二层是“能不能证明你的解法是对的”。比如洗牌题，很多人能写出Fisher-Yates算法，但能在现场说明白“为什么这样洗牌是均匀分布”的人就少一半。Google特别看重这种概率与数学直觉，因为这直接关系到搜索引擎、广告系统里的随机采样和A/B实验设计。

第三层是“代码写出来有没有工程味”。变量命名是否清晰、函数粒度是否合理、有没有多余的拷贝、能不能处理空输入。2011年Google笔试是纸质作答或简单的文本编辑器，没有编译器帮你检查，所以代码风格和细节习惯会直接暴露在卷面上。

这三层考察完，一个人的算法水平、数学功底和工程素养基本就摸清了。这也是为什么这套卷子的题目过了十几年，依然被各大题库收录——它考的从来不是死知识，而是可迁移的思维模型。

2. 核心算法题复盘：原题与最优解推导

2.1 两个有序数组的中位数：O(log(m+n))是怎么想出来的

题目：给定两个大小分别为 m 和 n 的有序数组，要求找出它们合并后中位数，时间复杂度要求O(log(m+n))。这题后来成了LeetCode第4题，当年在卷子上出现时，难倒了一批人。

先看暴力解法：把两个数组合并成一个，再找中位数，时间复杂度O(m+n)，空间复杂度O(m+n)。如果题目没限制复杂度，这么写已经能过。但O(log(m+n))这个复杂度非常扎眼——看到log，第一反应就是二分。

这题的正解是二分“划分位置”。核心思路：不需要真的合并数组，只需要找到一条分割线，把两个数组分成左右两部分，使得左边的所有数都不大于右边的所有数，并且左右两边的元素个数相等（或相差1）。中位数就是左边最大值和右边最小值的组合。

具体做法是：在较短的数组上二分分割位置i，另一个数组的分割位置j = (m+n+1)/2 - i。判断条件是nums1[i-1] <= nums2[j] && nums2[j-1] <= nums1[i]，如果不满足，就调整i的上下界。最后中位数分奇偶处理。

我当年在考场上的代码（遵循Google C++命名风格）大概是这样的：

class Solution { public: double FindMedianSortedArrays(const vector<int>& nums1, const vector<int>& nums2) { if (nums1.size() > nums2.size()) { return FindMedianSortedArrays(nums2, nums1); } int m = nums1.size(); int n = nums2.size(); int left = 0; int right = m; while (left <= right) { int i = (left + right) / 2; int j = (m + n + 1) / 2 - i; int left1 = (i == 0) ? INT_MIN : nums1[i - 1]; int right1 = (i == m) ? INT_MAX : nums1[i]; int left2 = (j == 0) ? INT_MIN : nums2[j - 1]; int right2 = (j == n) ? INT_MAX : nums2[j]; if (left1 <= right2 && left2 <= right1) { if ((m + n) % 2 == 0) { return (max(left1, left2) + min(right1, right2)) / 2.0; } else { return max(left1, left2); } } else if (left1 > right2) { right = i - 1; } else { left = i + 1; } } return 0.0; } };

有一个极其关键的细节：为什么一定要在较短的数组上二分？因为j的推导依赖另一个数组的长度，如果直接在长数组上二分，j可能越界，而且二分次数取决于较短数组的长度，复杂度是O(log(min(m,n)))，更优。这个点我在面试别人时也经常问，能答出来的人说明真正理解了二分，而不是背模板。

这题对工程的意义不只是面试。搜索系统里经常需要在两个有序列表中找分位点，比如广告系统合并两个排序的候选队列取Top K，都会用到类似的分治思想。Google当年在广告排序和检索系统里大量依赖这种高效合并，所以它出现在笔试卷上一点也不意外。

2.2 洗牌算法：怎么证明你的随机是公平的

题目：给定一个数组，实现一个洗牌函数，让每种排列出现的概率相等。这道题在2011年的笔试和面试里出现过多个变体，核心就是Fisher-Yates（也叫Knuth）洗牌算法。

低级的错误写法是：遍历每个位置，和随机位置交换。这个写法的问题在于，它生成的排列不是均匀分布的。证明方法很简单：n个元素的全排列有n!种，而“每个位置和随机位置交换”的随机路径分布并不均匀——某些排列出现的路径更多，某些更少。只有在i从0到n-1遍历，每次从[i, n-1]（而不是[0, n-1]）中随机选一个位置交换，才能保证每个排列恰好以1/n!概率出现。

void Shuffle(vector<int>& nums) { for (int i = 0; i < nums.size(); ++i) { int j = i + rand() % (nums.size() - i); swap(nums[i], nums[j]); } }

注意这里的rand依赖C库，真实工程里应该用std::mt19937或C++11的 库。

为什么Google这么爱考洗牌？因为搜索和广告系统里到处是随机性：抽样评估、A/B分流、MapReduce里的数据倾斜处理、机器学习里的随机梯度下降数据打乱。一个对概率没有直觉的工程师，很容易写出有偏的采样逻辑——线上跑几天才发现数据分布不对，那种事故比功能bug隐蔽得多。

当年我在卷子上写的是“从[0, n-1]全范围随机交换”，幸好提前留了草稿检查，推了一遍概率发现问题，才改成正确写法。这里有个经验：凡是涉及到“随机”“均匀”“期望”的题，写完之后一定要用“排列计数”的方式验证。比如n=3，列举所有可能路径，数一数每个排列出现了几次，不均匀马上能看出来。

2.3 编辑距离：从字符串DP到拼写纠错的桥梁

题目：给定两个字符串，允许插入、删除、替换三种操作，求最少操作次数，让两个字符串相等。

这题是动态规划入门的经典题，也是Google笔试里的常客。状态定义很朴素：dp[i][j]表示字符串a的前i个字符到字符串b的前j个字符的最短编辑距离。转移方程：

• 如果 a[i-1] == b[j-1]，dp[i][j] = dp[i-1][j-1]；
• 否则，dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1。

边界条件是dp[i][0] = i、dp[0][j] = j，因为其中一方为空串时，只能一直插入或删除。

int EditDistance(const string& a, const string& b) { int m = a.size(); int n = b.size(); vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); for (int i = 0; i <= m; ++i) { dp[i][0] = i; } for (int j = 0; j <= n; ++j) { dp[0][j] = j; } for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) { if (a[i - 1] == b[j - 1]) { dp[i][j] = dp[i - 1][j - 1]; } else { dp[i][j] = min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]}) + 1; } } } return dp[m][n]; }

空间可以滚动数组优化到O(n)，笔试时如果要求空间最优，记得提这一嘴。我当时还顺手写了一个“用编辑距离生成拼写纠错候选词”的扩展方案，后来才发现这几乎是Google搜索系统里spell checker的简化版本。

现在回看，这道题的价值不在DP本身，而在它是很多真实系统的简化模型：搜索引擎的“您是不是想找”，代码编辑器的自动修正，基因序列比对里的相似度计算，全部可以归约到编辑距离。2011年Google正在大规模优化搜索的“Did you mean”功能，这道题简直就是为这个场景量身定制的考察。

2.4 螺旋矩阵与矩阵旋转：把几何题变成工程题

题目：给一个n x n矩阵，要求按螺旋顺序输出所有元素，或者将矩阵就地旋转90度。这类题在2011年高频出现，主要考察“几何思维转成坐标变换”的能力。

螺旋矩阵的解法是分层处理：每圈是一个独立的子问题，用四个变量（top, bottom, left, right）控制边界，按“左->右、上->下、右->左、下->上”的顺序遍历。边界细节非常多：最后一行或最后一列可能只有一个元素，重复添加会导致结果错误。

矩阵旋转90度的正解是“先转置，再左右翻转”，或者“按层进行四个元素循环交换”。转置配合翻转的思路比直接写旋转坐标更不容易出错。

这类题的工程意义在哪里？图形学里纹理旋转、图像处理里的图片旋转、地图瓦片组织中的坐标变换，本质上都是这套矩阵变换逻辑。2011年正是Google Earth、Google Maps大量处理卫星图像和地图瓦片的年代，一个能快速把几何坐标映射到数组下标的工程师，对地图团队来说是稀缺资源。

另外一个隐藏考点是“原地操作”。Google非常在意空间复杂度。很多候选人能输出正确结果，但开了一个额外的二维数组，就会在“Follow up：能用O(1)额外空间吗？”上卡住。所以我的建议是：刷矩阵题时，养成先写“暴力+额外空间”，再优化成“原地”的习惯，笔试时把两种方案都写出来，会显得你很有工程意识。

3. 语言细节与设计题：Google式工程思维的体现

3.1 代码风格与语言细节：写在卷面上的“隐形分”

2011年的Google笔试卷上，不会明着写“本题考察代码风格”，但阅卷人会看。当时Google内部推行严格的C++ Style Guide，核心规则包括：变量名用snake_case，函数名用PascalCase，类成员变量加后缀下划线，禁止使用异常，智能指针优先于裸指针，头文件自包含、减少依赖。

在笔试里，最直接能体现风格的细节是变量命名和函数拆分。比如上面中位数代码，如果写成int n1, n2, l, r, mid;，阅卷人第一眼就知道你没接受过严格的Code Review。如果写成nums1, nums2, left, right, division1, division2，一眼望去就知道每行在干什么，即使有个小bug也容易修复。

还有一个语言细节是整型溢出。比如计算j的时候，(m + n + 1) / 2 - i，当m和n都很大时，m+n本身不会溢出（数组长度有上线），但如果写left + right做二分，left+right可能溢出。笔试时最好写成left + (right - left) / 2，这是面试官很喜欢的细节。

3.2 Guice与依赖注入：设计模式在笔试里怎么考

热词里有人搜“google的guice怎么使用”。Guice是Google开源的Java轻量级依赖注入框架，2011年前后在Google内部广泛使用。笔试虽然不会让你手写Guice代码，但会在系统设计题里隐性地考察“解耦”和“可测试性”这两个概念。

依赖注入的核心思想是：一个类不自己new它的依赖，而是通过构造函数、接口或注解的方式把依赖传进来。这样做的最大好处是替换方便、可测试性强——你可以很轻松地注入一个mock对象，而不用改被测代码。

Google考察这个，是因为一个大型搜索系统里，模块之间的依赖星罗棋布。如果每个模块自己new依赖，整个系统就是一团乱麻。反过来，依赖注入能让模块边界清晰，单测覆盖容易，A/B实验时也能通过替换实现来切换算法。

笔试时遇到“设计一个XX系统”的题，我建议你在方案里加入DI的表述：“模块之间通过接口交互，依赖由容器注入，便于测试和替换。”这句话写上去，阅卷人知道你理解真实工程，评分会明显不一样。

3.3 两道常见系统设计题：短链接与拼写纠错

2011年笔试卷里系统设计题出现过这些场景：设计一个URL短链接服务、设计一个拼写纠错系统、设计一个内存缓存、设计一个分布式计数器。我挑前两个讲思路。

短链接服务的核心链路是：接收长URL，生成短码，存储映射关系，访问时302重定向。设计考察点包括：短码生成算法（哈希取模、自增ID + Base62、随机数），存储选型（MySQL还是KV），缓存策略（热点短码如何加速），以及重定向用301还是302（301对SEO友好但无法统计，302可以做访问分析）。2011年Google对短链接的需求主要来自Google URL Shortener服务，现在这个服务虽然关了，但设计思路依然经典。

拼写纠错系统的考察点则更偏算法：用户输入一个词，怎么判断它拼错了？怎么生成候选词？怎么排序？候选词生成可以用编辑距离（呼应2.3节），也可以用BK树加速近邻查询。排序时还要考虑词频和上下文，把高频词排在前面。这道题最精彩的地方是：它把一个笔试算法题（编辑距离）直接接到了一个生产级系统（搜索引擎）里，考的是“你能把知识点用起来吗”。

多年以后回头看，Google开源的MediaPipe Hands这类实时手势追踪系统，本质上就是在做延迟和精度的权衡——算法层用轻量模型，工程层用流水线调度，这和笔试设计题里“资源有限、延迟敏感”的约束完全一致。也就是说，当年那套笔试卷训练的能力，后来直接作用于真实产品。

4. 实操过程：笔试现场的工具、输入法、时间分配

4.1 考场里的工具坑：从输入法到浏览器离线包

作为过来人，我必须说：Google笔试最难的不是题，是环境。我当年用的是考场提供的Ubuntu机器，默认编辑器是Vim或Emacs，输入法配置一塌糊涂。我在写着写着代码，突然发现自己打的注释全是英文还好，但旁边一位兄弟用搜狗输入法，死活切不出中文，连注释都写不了。

这种问题放在今天更像热词里说的“Ubuntu 24.04搜狗输入法不能输入中文”——版本兼容、输入法框架（fcitx vs ibus）、环境变量，任何一个环节出错，中文就进不去。笔试考场碰到这种问题，我的建议是：别纠结中文注释，直接用英文。代码和注释都是给人看的，英文注释一样表达清楚，输入法根本不值得占你20分钟。

还有一个坑是浏览器。考场的Chrome版本很老，想更新但网络受限，只能找离线安装包。热词里有人搜“google浏览器离线下载”，这确实是Windows/Linux上装Chrome时最常遇到的情况——在线安装器经常因为网络问题失败，离线包一装一个准。在笔试现场，如果你被浏览器问题卡住，最好的策略是换一个预装好的浏览器，或者直接改用终端里的编辑器，别在不熟悉的环境上浪费时间。

4.2 时间分配与答题顺序

Google笔试的时间非常紧张，我总结出一套相对稳的答题策略：拿到卷子先花2分钟通读全部题目，把“能立刻写对”和“需要思考”的题目分开。先做自己最有把握的题，拿到保底分，再啃难题。千万不能从第一题顺序做到最后一题，因为往往第一题就是一道偏推导的难题，卡住20分钟后心态就崩了。

单道题目的时间分配，我建议大概是这样：理解题意+思考思路占20%，写代码占40%，检查边界和复杂度占30%，最后留10%的缓冲写注释和整理。看起来检查比例很高，但笔试扣分大多数不是“没做出来”，而是“做出来了但边界没处理”。空数组、单元素数组、负数、溢出、重复元素，每个都要在脑内跑一遍。

我当年在“矩阵螺旋遍历”这道题上就吃了亏：主体代码写完了，没有在草稿纸上跑一遍“恰好只剩一行”的边界，结果最后提交时重复添加了一个元素。这种低级错误在笔试里特别伤，因为阅卷人会觉得你算法懂，但工程严谨性不够。

4.3 笔试后的复盘方法

笔试不是交卷就结束了，真正的学习发生在复盘。我的做法是：每道题整理三份笔记——第一份是题目和解法本身；第二份是最优解和暴解的复杂度对比，以及为什么最优解能降复杂度；第三份是“这道题还能怎么变形”，比如中位数改成分位数、编辑距离加上代价权重、螺旋矩阵改成蛇形矩阵。

三遍刷题法也很管用。第一遍看懂答案，把代码敲一遍；第二遍合上答案，从零开始写；第三遍隔一周再做，看自己能不能讲清楚思路。要是能把它讲给一个完全没做过这道题的人听懂，这道题才算真的掌握。

还有一个技巧：给自己的错误分门别类。我当年统计过自己的错题类型，发现70%是边界条件，20%是状态转移想错，10%是看不出最优解。于是后面刷题就有针对性了——专门找边界多的题目练，专门总结状态转移的套路，效果立竿见影。

5. 常见问题与避坑清单

5.1 算法题最高频的5个翻车点

先从阅卷角度来看，我在审校工程师笔试卷时见过最多的翻车点，整理成一张表：

这里面最隐蔽的是二分死循环。二分模板背得再熟，边界一改就容易出问题。我的经验是：二分循环里，如果while条件是left <= right，那么更新时一定要让mid改变，要么left = mid + 1，要么right = mid - 1；如果while条件是left < right，更新时left = mid或right = mid，两者必须有一个能保证区间收缩，否则必死循环。

5.2 代码质量自查清单

写完代码后花1分钟自查，按这个顺序来：第一，变量名是否表达了含义，有没有i、j、k满天飞。第二，函数体是否超过50行，超过就考虑拆函数。第三，有没有冗余拷贝，vector传参是不是const引用。第四，边界输入是否处理了。第五，有没有写清楚核心注释，尤其是状态转移和边界条件的注释。

Google C++风格对注释的态度是：解释“为什么”，而不是解释“是什么”。比如洗牌算法里，最好的注释是“从[i, n-1]中随机选择，保证所有排列等概率”，而不是“交换两个元素”。前者让后来维护代码的人知道你的意图，后者纯粹是噪音。

5.3 从2011到现在的变化：这套题还适用吗

有人会问：十几年过去了，这套笔试卷是不是过时了？我的看法是：核心算法部分完全不过时，二分、DP、概率、树和图的遍历，这些是计算机科学的地基，地基不会变。但考察方式的侧重点确实变了。

现在的面试更强调系统设计：分布式缓存、消息队列、微服务治理、存储引擎选型，这些问题在2011年的笔试卷里只有简化的版本。Google本身也从“靠一个天才写一段完美算法”演变为“靠协作构建大型系统”，所以面试的重心自然偏移。但2011年笔试卷里训练出来的“快速建模能力”，依然是做系统设计的底层能力。

另一个变化是工程化体系更复杂了。比如现在Android开发者发布App时要用AAB格式，超过150MB要配置install-time分包，这和2011年直接打包APK完全是两个时代。热词里有人搜“Google Play AAB大于150M分包install time”——这种问题在2011年根本不存在。但解决这类构建问题的思路，依然是二分定位、模块拆分、依赖分析这些笔试里反复训练的东西。

所以我的结论是：Google 2011笔试卷不是用来背的考古题，而是一套“思维训练的度量衡”。你不需要把每道题的答案背下来，但你需要通过这套题，训练出严谨的边界意识、概率直觉和复杂度的敏感度。这些能力放到任何时代、任何技术栈里，都不会贬值。

我自己在带新人时，还是会让候选人做一遍这套卷子里的经典题，不是为了考倒谁，而是为了在几个小时内看清一个工程师怎么思考、怎么写代码、怎么应对被追问。这份2011年的卷子，就像一把经过时间打磨的尺子，它量出来的不是记忆的厚度，而是思维的密度。