版权声明：本文为博主原创文章，转载请注明出处：https://twocups.cn/index.php/2022/11/25/48/
面试内容介绍
我最近面了Google，认为这是一次很棒的面试体验，所以记录一下。
2022年7月15日，我在Google的招聘官网上投递了自己的简历。
2022年9月9日，Google的HR加了我简历上的微信，跟我说最近Google上海这边开了一些岗位出来，问我有没有兴趣。最终向我发起面试邀请的是上海的Pixel部门，主营业务是无线通信。正好我本科的专业就是通信，对这个还挺感兴趣的，就接受了。
Google的面试是我所有经历过的面试中最标准的，一场是45分钟。我面试的部门所使用的语言是C++，但面试中的编程语言是不受限制的，所以我就用我最熟悉的Golang来解题。面试类型分为两种，一种是Coding面试，另一种是Googleyness & Leadership（以下简称G&L）面试。Coding面试主要就是针对面试官提出的一个情景，自己编写一个算法来解决问题。通常面试官会先给出一个比较简单的问题，然后在此基础上逐步变难。而G&L面试考察的是个人的软能力，是纯聊天，只不过聊的都是专业性的内容。
我经历的面试一共五轮。
2022年9月27日，一场初试，中文，coding面试。
2022年10月13日和14日，四场复试，两英文两中文，三轮coding面试和一轮G&L面试。
2022年11月28日，Hiring Team的反馈是工程能力和面试表现都很优秀，但目前他们更加期待有数据仓库背景的候选人，所以比较遗憾没能拿到Google的Offer。
面试经验
就我个人感受而言，Google的面试明显比我之前面的微软和AWS要难很多。Google更看重的是面试者的思维能力和沟通能力，而不是单纯地看面试者能不能把题目直接做出来（当然你必须也要做出来）。如果思路上遇到卡壳，是可以跟面试官要思路的。不要想着一次就直接想到完美的解决方法，不太现实。毕竟Google是有自己实时更新的题库的，如果在网上看到题目被泄露，题库中会删除相应的题目，所以不太可能遇到原题。正确的做法是从基础一步一步推算，不用一次就想的完美，但要最终全部想清楚。这个过程中也应该跟面试官全程交流，同时验证自己的想法。
拿到题目之后该如何思考呢？
首先，我会去考虑题目的算法类型。常用的算法类型有数组处理、字符串处理、二分（整数/小数，精确查找/范围查找）、双/多指针、数学计算、位运算、特殊数据结构（链表/栈/滑动窗口/堆/单调栈/HashMap/Trie/并查集）、树/图、DFS、BFS、动态规划（线性/区间/数位统计/状态压缩/树形/记忆化搜索）、贪心。
通常来说，知道算法类型之后应该能想到最基础的暴力解法。之后，我会计算出这个解法的时间和空间复杂度，然后优化算法。优化算法的时候可以考虑先降低时间复杂度，如果不行再考虑降低空间复杂度。如果我能猜到最优的时间复杂度，那么我就能逆推出算法。
时间复杂度一般有三种。
O(logn) 二分、双指针
O(n) 遍历、滑动窗口、单调栈、线段树、一维数组DP
O(n^2) 双指针
如果面试官在描述题目的时候提醒你，由于答案可能会很大，所以你需要取余后输出，那么这句话的意思是用到了累加/累乘。累加一般会是组合公式，或者二维DP。
如果仍然没有解题思路的话，接下来我会采取将题目降维的策略。简单来说，就是先修改题目，把题目变得简单，得到最优解后，再一步一步地将题目变回原来的难度。在这个过程中，我就可以清晰地知道是什么在阻挠我解题，然后逐个击破就好了。
还有一个难点就是动态规划。我会先假设我已经得到了这个动态规划的状态转移方程，那么如果状态数组的长度从n变成了n+1，那么多出来的那个状态会对整体的结果造成什么影响呢？只要想明白这点，就相当于知道数组的情况（状态）是如何变化（转移）的，状态转移方程自然就出来了。我的这种解法其实就是动态规划的本质，是需要大量练习的，但练出来以后动态规划问题几乎都能解决。
如果对于最优解仍然毫无头绪，那么只能通过模拟来解题了，也就是我们俗称的暴力解法。模拟永远是最后一条路，不到万不得已不要用。
在Google的能力考察里，沟通能力和解题能力是同等重要的。
在Coding面试的过程中，我需要不停地说话，不停地向面试官表达我现在正在思考的东西。我认为这是一个难点，特别是在英文Coding的情况下。英文Coding中，我需要倾听面试官的表达，同时向面试官用英文表达我自己的思路，这个表达的过程我要尽量地放慢，因为我需要确保对方能听清我在说什么。但是我脑中是用中文在思考的，这个思考的过程我是全程加速的，因为我必须要在尽量短的时间内想出解决问题的方法，并且查漏补缺。这种一心二用的能力我刚开始也是完全做不到，但正巧初试和复试中间隔了一个国庆假期，所以在自己专门的训练后也很熟练了。我当时用的是Pramp，这是一个完全免费的模拟面试网站。在这里我可以作为面试官给别人面试，同时作为面试者接受别人的面试。我当时一天约五场，全英文高强度训练，效果还是很好的。
关于Coding，我有三个建议。
第一，变量名一定要能代表变量的含义，要让面试官看到你的变量名就知道这个数据结构中存储的是什么数据，千万不要起array或者queue这种名字。
第二，每写完一段代码就回头看看，以一个旁观者的视角看看自己能不能清楚地理解这段代码，问问自己这段代码的逻辑是否清晰。这么做是为了维护代码的可读性，这非常重要。
第三，代码规范非常重要，可以去看下自己语言的Google代码规范。还有就是创建数组的时候先算一下要用多少容量，然后初始化数组的时候带上初始容量，否则数组扩容很耗费时间。
Google的Coding面试正因为标准，所以每次的流程是非常相似的，下面有我自己总结的Coding面试模板。
因为存在英文Coding，所以必须熟练掌握所有英文中数据结构和算法的表达，下面有我自己总结的Coding单词表。
G&L面试的本质是看你是否符合Google的企业文化，很重要的一点是不要把它当成考试，而是把它当成一次交流，和面试官聊聊就好。当然，面试官那里肯定是有评判标准的，所以聊的时候也请长点心。
Coding面试模板
如果是没有面试经验的面试者，可以从我自己总结的模板入手练习。等熟练之后，就可以自由发挥了。需要注意的是，每个时间段需要做的事情是固定的，只是自己表达的方式可以更加自由。只要面试官能够听懂你在说什么，并且所有的注意点都提到了，怎么表达都可以，没有固定句式的。
0 ~ 10min 听题 + Clarification Questions
面试官是通过口述的方式给出题目，而我这里能看到的就只有一个白板。所以最开始一定要听清楚题目描述的情景和要求自己解决的问题。当面试官说完题目之后，自己一定要把题目再复述一遍，和面试官沟通题目的意思，直到完全弄清楚题目才行。
在确定自己已经弄清题目之后，首先要做的就是约定输入和输出。
I will define a function to solve this problem. The input is …, and the output is …
之后就要跟面试官明确题目中他没有提到的一些条件（Clarification Questions）。
I got the problem, but I have some clarification questions that I want to discuss with you.
Anything I can know about the size of array and the range of values? （明确数据范围）
What should I do if there is no valid answer? Do you want me to throw exception? Or simply return a special value such as minus one? （如果答案不存在，那我该如何处理）
Since integer calculations appear, I assume all the data will not overflow when calculated.（假设数据在计算过程中不会溢出）
There is some edge cases that I want to share with you. （考虑边缘情况）
10 ~ 15min 描述解题思路 + 跑一个案例 + 分析时空复杂度
接着就可以开始思考如何去解决这个问题，这个过程中也应该积极地跟面试官沟通自己的思路，而不是自己闷头想。当然，我知道边说话边思考会大大减慢思考的速度，更何况用英文，但在面试过程中这是必要的，也是需要大量的练习才能熟练。
有了思路就可以跟面试官表明该如何解决当前的问题。
With these clarification questions, I will use … to solve this problem.
为了确保面试官能够听懂自己的思路，我还会用一个案例来过一边自己的思路。
Here, I want to use the example to show my ideas.
Firstly, I will iterate / go through the array…
After, we find that …
Finally, …
之后再计算一下自己算法的时间复杂度和空间复杂度。
Let me think about the complexity of my algorithm.
The time complexity is …
The space complexity is …
15 ~ 25min 完成Coding + 再跑一个案例
写代码的同时，要告诉面试官你正在处理的逻辑，和你现在的思路。
Here I am using a loop to …
Now, we need to check …
25 ~ 40min Follow up
当已经解决了一个问题的时候，面试官往往会在刚才问题的基础上修改一些条件，使这个问题变得更难。
我们需要注意的是他修改了什么条件，并且会对题目的解法造成什么样的影响。我们知道如何解题之后，再重复上述解题的过程。
Since the elements are not unique now, …
The array is … so we can do it simply, but we need to care about more cases.
What will happen if the integers are not unique?
Coding单词表
algorithm 算法
data structure 数据结构
item 项
logical structure 逻辑结构
phyical structure 物理结构
linear structure 线性结构
atomic data type 基本数据类型
linear list 线性表
stack 栈
queue 队列
string 串
array 数组
tree 树
graph 图
search 查找/搜索
update 更新
sort 排序
insert 插入
delete 删除
predecessor 前趋
successor 后继
double-ended queue 双端队列
circular queue 循环队列
pointer 指针
first-in first-out list 先进先出表
last-in first-out list 后进先出表
bottom 底部（栈底）
top 顶部（栈顶）
push 入栈
pop 出栈
front 队头
rear 队尾
overflow 上溢
underflow 下溢
matrix 矩阵
multi-dimentional array 多维数组
symmetric matrix 对称矩阵
sparse matrix 稀疏矩阵
linked list 链表
linear linked list 线性链表
single linked list 单链表
multi linked list 多重链表
circular linked list 循环链表
head node 头节点
head pointer 头指针
tail pointer 尾指针
blank string 空白串（空格串）
null string 空串（零串）
substring 子串
subtree 子树
forest 森林
root 根
leaf 叶子
node 节点
depth 深度
level 层次
parents 双亲
children 孩子
brother 兄弟
ancestor 祖先
descendant 子孙
binary tree 二叉树
balanced binary tree 平衡二叉树
full binary tree 满二叉树
complete binary tree 完全二叉树
traverse binary tree 遍历二叉树
binary sort tree 二叉排序树
binary search tree 二叉搜索树
preorder traversal 先序遍历
inorder traversal 中序遍历
postorder traversal 后序遍历
directed graph 有向图
undirected graph 无向图
connected graph 连通图
weighted graph 加权图
directed acyclic graph 有向无环图（DAG）
spares graph 稀疏图
dense graph 稠密图
edge 边
vertex 顶点
path 路径
cycle 回路（环）
source 源点
destination 终点
initial node 初始节点
terminal node 终端节点
adjacent edge 相邻边
adjacent vertex 相邻节点
indegree 入度
outdegree 出度
shortest path 最短路径
adjacency matrix 邻接矩阵
adjacency list 邻接表
spanning tree 生成树
minimum cost spanning tree 最小生成树
topological sort 拓扑排序
critical path 关键路径
match 匹配
linear search 线性（顺序）查找
binary search 二分查找
block search 分块查找
hash table 散列表
immediately allocating method 直接定址法
addition 加法
subtraction 减法
multiplication 乘法
division 除法
plus 加
minus 减
times 乘
divided by 除以
sort 排序
internal sort 内部排序
external sort 外部排序
insertion sort 插入排序
selection sort 选择排序
heap sort 堆排序
quick sort 快速排序
merge sort 归并排序
redix sort 基数排序
monotonic stack 单调栈
iterate 迭代
recursion 递归
edge cases 边缘案例
clarification questions 澄清问题
union find 并查集
time complexity 时间复杂度
space complexity 空间复杂度
brute force 暴力解
optimal solution 最优解
indicate 表明
by default 默认
trie tree 字典树
be greater than 比...大
be greater than or equal to 大于等于...
be less than 比...小
be less than or equal to 小于等于...
be equal to 等于
sliding window 滑动窗口
dynamic programming 动态规划（DP）
contiguous sequence 连续序列
cell 格子
distinct 不同的
judge 判断
array expansion 数组扩容
candidates 候选
consecutive 连续的
N-ary tree N叉树
best 最好
worst 最差
memorandum 备忘录
optimal substructure 最优子结构
diagonal 对角线
maintain 维护
ascending 上升的
inherit 继承
duplicate elements 重复元素
parentheses 括号
compound question 复合问题
in addition to 除了
respectively 分别地