34

写给开发者的谷歌技术面试终极通关指南

 4 years ago
source link: https://www.tuicool.com/articles/m2iaq2e
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

通过谷歌面试是所有工程师的梦想。技术面试谷歌招聘流程必不可少的一环，它是对应聘者技术能力的终极测试，以评价你是否具备开发最优秀软件所需的编程与算法能力。谷歌面试是评价技术能力的关键衡量标准，可以说是决定是否聘用候选人的最重要决定因素。

想要顺利通过谷歌面试的话，你需要为面试中的重点环节提前做好准备。这篇文章就会教你相应的策略。此外，有大批企业都在模仿谷歌的面试风格，所以这篇文章也能帮你应付其他大型科技公司的面试。

本文中你将学到以下内容：

  1. 什么是谷歌面试？

  2. 谷歌面试与其他公司有何不同？

  3. 如何准备谷歌电话面试和谷歌现场（Onsite）面试

  4. 最常见的谷歌面试问题

  5. 其它与谷歌面试相关的资源

什么是谷歌面试？

谷歌面试与常见的面试区别很大。如果之前你经历过编程面试的话还好，否则谷歌面试和你习惯的那些流程是完全不同的。

你在谷歌面试中可能会遇到三大类型的问题：

  1. 编程面试问题

  • 问题：一项依赖数据结构和算法知识的编程问题。

  • 要求：在面试的时间限制内为问题提供有效且优化的解决方案。

  1. 系统设计问题

  • 问题：涉及复杂系统设计的高层次宽泛问题。例如，面试官可能会让你设计 Gmail。

  • 要求：能够与面试官一起确定系统关键组件的内容，并设计一个可扩展的解决方案。

  1. 一般分析问题

  • 问题：一个数学、设计或基于观点的问题，面试官想要考察你的思维逻辑，考察你作为员工的行事风格。

  • 要求：提供许多不同的解决方案，并能够讲出每个解决方案的各种利弊。这个过程犹如试金石，会让面试官了解你在团队中的作用和角色。

谷歌面试的大部分内容都是编写代码，这也是本文重点关注的内容。关于应对系统设计面试的策略，请参阅这篇 文章 。

谷歌面试与其他公司有何不同？

谷歌很乐于分享他们的招聘流程，还专门写了一整页 介绍 。

面试流程第一步是电话面试，如果通过就会进行一系列的现场面试。谷歌电面和现场面试在技术面试中是很常见的策略，但他们的流程有一些独一无二的细节特征：

谷歌电话面试

电话面试阶段会有至少一位谷歌员工与你沟通，给你发送编程试题。你会同面试官共享一份谷歌文档，并用它来编写面试官给出试题的代码。

高级技巧：在谷歌文档中写代码是很难受的，但如果你提前设置好自己的的偏好，那这个过程就能轻松很多很多了。这里是具体的 做法 。

这次面试将重点考察你在没有 IDE（集成开发环境）的情况下编写代码的能力。面试官提出的问题一般来说会有一个暴力解决方案，然后可以逐渐改进优化解决思路。

电话面试大约需要 30-45 分钟。如果你表现良好，谷歌招聘人员准备对你继续下一阶段考察的话，他们会再联络你并告诉你之后的流程。

如果他们要求进行第二次电话面试也不要失望。可能只是因为他们觉得一次电面得到的信息还不够下结论，这也很正常，不要因此在之后的面试中有任何心理负担。

谷歌现场面试

谷歌现场面试阶段，应聘者会同多名谷歌员工进行交流。这一阶段一般会有四到六次单独的访谈，包括一次“午餐面谈”。

一般来说他们问你的问题以编程为主，可能还有一两个涉及系统设计的问题。

你的工作经验越丰富，越可能被问到系统设计和特定领域的问题。谷歌很少向经验不足 5 年的工程师询问任何系统设计问题。

每位面试官都会记录一对一面谈中你的表现并汇报上去。几位面试官的报告是各自独立的，以避免从众效应和偏见。所以就算你觉得其中一次面试时自己表现不好，这次的记录也不会影响下次面试。

面试结束后

面试结束后谷歌会收集面试官们的报告并汇总。谷歌会对你的编码经验、分析能力等一系列表现分类打出 1-4 分，然后将汇总报告发给招聘委员会，以做出最终决定。一切顺利的话，你就可以开始同公司商讨薪水等事项了。

如果你没通过，也可以在半年到一年后 重新申请 。设定这个时限是考虑到你可以用这段时间重新学习，提升你的技能和经验，这样下次你的机会就会更多一些了。

尽管很多谷歌员工都曾在现场面试阶段失利，但投入了大量时间和精力之后还没能成功真的很打击人。最重要的是，要等待半年再次申请的规定可能会让人迷失方向，甚至干脆把最开始的雄心和计划抛在脑后了。

谋事在人，成事在天，但起码你可以做好准备，把握好自己可以做到的事情。接下来，我就会教你该如何为谷歌面试做准备。

准备谷歌面试

怎样为面试做好准备，争取一次就通过？像 HackerRank 、 LeetCode 、 ProjectEuler 、 TopCoder 这类网站都提供了技术面试的题库以便练习。你当然可以花费大量时间把 LeetCode 上所有习题都过一遍，但这真的值得吗？有没有更有效率的路子可走？

人的时间和精力都是有限的，因此我们要尽量高效地使用这两种资源。你需要专注、持续并有针对性的训练，这是通向谷歌面试成功之路的必要步骤。

模拟真实场景做训练

贴近现实的练习才有效率。

面试时，你会希望自己全神贯注，将大部分精力都投入到面试官提出的问题上。你不应该受无关因素，比如说不习惯在非 IDE 环境中写代码这种事情干扰。

以下列出了在制定练习方案时应注意的因素。

时间限制

电话面试时间为 30-45 分钟，每次一对一的现场面试大约持续 45 分钟到一小时。每次面试中你至少会被问到一个问题，多数情况下会是一个编程问题。

为了在这种时间限制下高效练习，一种方法是选一个特定问题入手。

一开始你可以从本文的附注资源部分下的书籍或视频中选择一个问题。然后开始计时，并尝试在不用 IDE 的情况下解决它。

这样针对几个不同类别的编程问题练习过后，你就差不多知道自己在时限内处理问题有哪些不足了。你的最终目标是在 30-45 分钟的时限内，针对各种难度的问题做出最佳解决方案。如果你正在努力实现这一目标，那么就应该为此做针对性的训练。

白板

无论是谷歌电面还是现场面试中，你都要在没有 IDE 的情况下写出语法正确的代码来。实话说这真的很难。

电话面试时代码要写在谷歌文档上；现场面试时你要在白板上手写代码。如果你从未练习过，那么就很难在白板上手写出正确的代码了。因此你要在练习时就习惯时间限制、习惯摆脱对 IDE 的依赖，这是非常重要的。

每次练习后可以把代码完整抄到编辑器中运行一下，你可能会惊讶地发现自己在白板上手写的代码竟然会有这么多错误。为了避免在面试中出这种问题，你应该练习在纸上手写代码。

你还必须非常熟悉面试中使用的语言。虽然你可以请面试官帮忙提供库功能来完成某项任务，但这会浪费时间，并且反映出你准备不足、缺乏领域相关知识的缺陷。

压力

作为应聘者，面试时你是被关注的焦点，大家的目光都聚焦在你身上。

面试时你要在限定时间内以不常见的方法解决一项颇具挑战性的难题，这时还要有人死死盯着你，这是非常让人不舒服的事情，很容易影响人们的表现。

对抗焦虑的一个好办法是训练自己在时间限制内用白板手写答案，同时找一位伙伴在旁边盯着你看。但你可能准备一个人去应聘谷歌，所以这种伙伴也不好找，怎么办？

这种情况下， Pramp 就可以帮助你解决问题。Pramp 会随机匹配两位程序员，你问同伴一个问题并扮演半小时的面试官角色，然后角色反转，你再扮演半小时的面试者角色。

高级技巧：你还可以通过 Pramp 了解成为面试官的感受，这是一个很好的角度。

测试和罕见情况

当你针对给定问题开发解决方案时，你需要考虑到可能由意外输入导致的罕见情况。这是一个很好的习惯，这样你的面试官就能知道你会考虑代码会出现哪些问题。

此外，你还要为这些罕见状况提出解决方案。

如果你发现自己能在设定的时间限制内解决指定的编程问题，那么可以编写一些单元测试，并好好考虑开发初始解决方案时可能遗漏的罕见状况。

养成写代码时考虑到将要或者应该做的测试的习惯，这样你就能预测面试官会提出哪些问题。经过充分练习后你就会形成条件反射，面试官提问时你就不会猝不及防了。

关键在于训练素材

在练习时选择覆盖所有种类题型的题库是很好的，但关键在于专注正确的训练素材。

虽然你可以在 LeetCode 上随机练题，但这样效率很低，多练一道题也不会大幅提升你通过谷歌面试的机会。

相反，何不专门练习过去谷歌面试中出现过的题库呢？这样会让你的时间和精力更加集中，提升效率。

下一节中，我们将介绍谷歌喜欢考察的具体问题和类型。

最常见的谷歌面试问题类型

我们在 Glassdoor 网站中收集了一些谷歌面试中出现的问题类型。

Glassdoor 有一个 谷歌专页 ，里面都是面试过谷歌的应聘者写的经历。他们一般会提到面试中被问到哪些问题，或者起码提及问题的类型。

我们分析了 Glassdoor 中的几百条面试经历，总结出了谷歌面试中最常问到的问题类型分布。

ANJNRzV.png!web

不算“系统设计”，只看“编程”大类，下面排行前三的分类分别是：

  1. 图 和 树

  2. 数组和字符串处理

  3. 递归 和 动态规划

高级技巧：谷歌通常只向至少有 3 到 5 年软件工程经验的应聘者提出系统设计类问题。

谷歌看起来很喜欢问这几类问题，所以应该把大部分时间和精力投入到与它们相关的练习上。接下来我们来看如何针对这几大类问题做针对训练。

图和树

注意：这部分内容应该配合这份关于二叉树的 Youtube 视频列表 学习。我们在本节中介绍的二叉树代码的完整实现都放到了 GitHub 上。

树和图是谷歌面试问题中经常涉及到的数据结构类型。你应该熟练设计、引导和操控这些结构来解决问题，这样就能在面试中得到高分。

为了检测自己对这些结构的了解程度，首先你可以自己编写一种树或图的实现。

比如说我们想要研究二叉树。了解二叉树概念的话，你肯定知道它是由节点对象组成的。

每个节点都有一些属性，除了指向左右子节点（如果有的话）的左右指针外，还包括存储在该节点中内容的特定数据字段。在 Python 中我们可以定义一个 Node 类，如下所示：

复制代码 

classNode(object):
def__init__(self, value):
self.value = value
self.left = None
self.right = None

我们还可以创建一个将由 Node 对象构造的 BinaryTree 组合类

复制代码 

classBinaryTree(object):
def__init__(self,root):
self.root =Node(root)

有了这个基本结构后，我们现在可以构造一个简单的 BinaryTree 对象：

复制代码 

# Set up binary tree:
tree = BinaryTree(1)
tree.root.left =Node(2)
tree.root.right =Node(3)

这个二叉树的根节点值为 1，左子节点值为 2，右子节点值为 3。

这个 视频 可以帮助你复习二叉树知识。

现在你对二叉树对象有了基本概念，知道了想要用好它，很重要的一点就是遍历它的结构。

接下来复习二叉树遍历算法，分为前序、中序和后序 三类 。

看完上面的内容后我们想要测试一下自己对二叉树数据结构的理解有多深刻。我建议尝试去解决一些二叉树问题来测试这方面的能力。

假设你已经复习到这一步了，那么你可以更上一个台阶，尝试实现一个水平遍历，也就是从上到下，从左到右遍历二叉树的全部节点。

做这个测试时试着给自己创造前文提到的压力环境，也就是给定时间、找伙伴模拟面试官，并在纸上或白板上手写代码。

之后你可以试着总结自己对二叉树结构的理解，并考察自己利用这些知识解决其它问题的能力，例如计算二叉树的大小和计算二叉树的高度。

通过这种渐进学习的过程，你就能逐步构建或增强对特定数据结构的知识框架。虽说并不是所有数据结构都需要这么复杂的学习过程，但是采用这种渐进深入的方法可以对特定数据结构建立非常深刻的理解，帮助你更好地利用它解决相关问题。

数组和字符串

数组和字符串算一类问题，因为字符串处理一般可以看作是执行某种类型的数组操作。

在谷歌面试中，你将遇到的几乎所有问题，其基础元素都包括数组数据结构（在 Python 这类语言中是列表）。

你应该深入理解数组结构的基础知识，理解从数组中存储、检索等操作的复杂性，才能快速将用这些知识来解决现实问题。

我们先从 50 个 面试问题指南 中挑一个问题来分析。来看第四道题，“查重”：

给定一个整数数组，其中每个值 1 <= x <= len(array)，编写一个函数来查找数组中的所有重复项。

例如：

复制代码 

dups([1,2,3]) = []
dups([1,2,2]) = [2]
dups([3,3,3]) = [3]
dups([2,1,2,1]) = [1,2]

欲了解本问题的细节点击 此处 。

如前所述，先从问题的 暴力解决方案 入手是不错的思路。虽说这种方案不是最好的，但起码能解决问题。当你盯着白板手足无措的时候，想出这样一个方案总比发呆要强。

那么这里该用什么暴力方案呢？ 想一下，你可以一次处理一个元素，同时检查剩下的元素，看看数组中的其它元素是否等于你正在处理的元素。

下面的代码就是一种思路：

复制代码 

def dups(A):
    dups = {}
   foriinrange(len(A)):
       num= A[i]
       forjinrange(i+1, len(A)):
           ifnum== A[j]:
                dups[num] =num
   returnlist(dups.keys())

这段代码中，我们让外部循环遍历数组，再让内部循环在我们遍历数组时遍历剩余元素。这就会生成一个 O(n^2) 算法。

方法很笨，但起码开了个头。下面我们可以利用 Python 内置的 set() 函数来改进这个方案。其它语言的算法也是类似的。

这里的改进思路是，我们可以创建一个 set 对象并遍历输入列表。如果我们迭代的元素不在集合中，则将其添加进来。否则就继续处理列表。

代码如下：

复制代码 

defdups(A):
    s = set()
   foriinA:
       ifinotins:
            s.add(i)
   returnlist(s)

这样我们的 O(n^2) 算法就改进成了 O(n) 算法。现在它还需要 O(n) 空间来在集合中存储元素。那么还能继续改进吗？

接下来我们可以改进空间需求，让它变成恒定值。

如果我们对输入数组排序，我们就可以遍历数组并检查我们正在处理的元素与数组中的下一个元素是否不同。如果两个元素是一样的就代表有重复项，我们就能对其做处理了。反之，我们就继续处理数组。

代码如下：

复制代码 

defdups(A):
    A= sorted(A)
    s =set()
   foriinrange(len(A)-1):
       ifA[i] == A[i+1]:
            s.add(A[i])
   returnlist(s)

这样我们就把空间需求优化到了 O(1)，但因为排序带来了 O(n log n) 的时间复杂度，所以花费的时间就会增加了。

到这一步我们找出了几个方法，它们在速度和存储需求方面各有优势。现在我们应该再看一下这个问题，看看它有什么特点可以用来做方案优化。

再看一遍后我们注意到了前提条件，那就是每个值都会 1 <= x <= len(array)。这里的“技巧”在于，既然已经有了一个不用额外数据结构的定值，那么能不能在空间复杂度不变的同时优化方案呢。

鉴于数组中所有数字的值域都介于 1 到数组长度之间，我们就可以把它编码到已有的数组数据结构中。这样，我们就能利用上给定的输入中已经分配给我们的空间了。

来看一个具体的输入示例，看看这个新方法的实现原理。假设输入的是列表 [2, 1, 2, 1]。重申一下，我们知道数组中的每个值都介于 1 和数组的总长度之间。

为了简化问题，我们从列表的值中减去一，这样条件就变成了每个值都是 0 <= x <= len(array) - 1。

另一个重要发现是，根据前提我们知道数组中的每个值都是正整数。

当我们遍历这个数组时，每个数字如果见过的话就把值对应的索引值正负号调转。这样如果发现了一个带有负号的值，就知道之前遇到过它了，并将该值添加到我们的重复集中。

具体来看 [2, 1, 2, 1] 这个例子。我们遍历这个列表的所有元素，遇到的第一个值是 2。我们现在想要记录下我们在数组中遇到 2 这件事，所以我们需要从值中减去一来计算索引，亦即：

index = 2 - 1 = 1

然后我们将对应索引 1 的索引值取负值，列表变为：

[2, -1, 2, 1]

继续处理列表，我们遇到了 -1，这里取绝对值来获取它的原始值并像之前一样计算索引：

index = 1 - 1 = 0

现在我们转到数组中的索引 0 并取其负值：

[-2, -1, 2, 1]

这个列表告诉我们，我们已经遇到了一个 1，因为我们取了索引 0 的负值；我们还遇到了一个 2，因为我们取了索引 1 的负值。继续这个算法，我们遇到了第二个 2，索引计算为

index = 2 - 1 = 1

现在检查数组中索引 1 处的值，但该值为负，表示我们已经在数组中遇到过这个值了。所以我们将此重复值添加到输出集中。

按照这套方法，我们的算法需要 O(n) 的时间并使用 O(1) 的空间。最终代码如下：

复制代码 

def dups(A):
    result_set =set()
   foriinrange(len(A)):
       # Translate the value into an index (1 <= x <= len(A))
       index=abs(A[i] -1)
       # If the value at that index is negative, then we've already seen
       # that value so it's a duplicate. Otherwise, negate the value at
       # that index so we know we've seen it.
       ifA[index] <0:
            result_set.add(abs(A[i]))
       else:
            A[index] = -A[index]
   # Return the array to its original state.
   foriinrange(len(A)):
        A[i] =abs(A[i])
   returnlist(result_set)

这篇 文章 有关于常见字符串和数组模式的更多内容。

递归和动态编程

递归 和 动态编程 是相辅相成的。用动态编程解决问题时通常要先找到问题的递归解决方案，然后找到存储和参考之前计算结果的方法来避免之后不必要的计算。

要掌握这这两块内容肯定要对递归有充分的了解。仅了解递归的概念是不够的，关键在于用简洁的方式将递归思维快速应用到解决方案上。

显然，前面提到的常见问题类型，包括树 / 图和数组 / 字符串问题通常也会用到递归。

例如，在字符串中查找大写字母、计算字符串长度或计算字符串中辅音数量等问题都可以归类为“字符串”的类型，但它们也都有非常简洁的递归方案。

解决需要递归的问题，关键在于制定识别、分析和解决递归问题的策略。

我们还探讨了如何使用 FAST 方法解决 动态编程问题 。

其它资源

应对谷歌面试所涉及的资源和材料是很多的，本文不可能一一详解。

决定你在谷歌面试中能否成功的关键因素在于你的编程熟练度，为此我们会介绍一些我们最喜欢的书籍和视频资源。

图书：

破解编程面试

作为练习材料，Gayle Laakmann McDowell 的破解编程面试，（Cracking the Coding Interview，CTCI）是最受欢迎的资源之一。除了提供一系列实践问题外，本书的引言还提供了有关谷歌如何做招聘的具体情报。

这部分内容只有简短的几页，但作者 Gayle 之前曾参与谷歌的面试流程，所以她的建议很有价值。这段 视频 是对 CTCI 的一个详解。

编程面试的要素

如果你想开个书单，这个 视频 提到了他为技术面试准备工作推荐的 5 本书，其中就有 CTCI。

我最喜欢的一本是 Adnan Aziz、Tsung-Hsien Lee 和 Amit Prakash 编写的 Python 编程面试要素（EPI）。

其中一位作者 Tsung-Hsien 是谷歌的现任员工，本书中提到的许多问题与 Glassdoor 数据总结出来的问题很接近，这可能并非巧合。CTCI 的习题太常见了，所以面试官不太喜欢问这类问题。

EPI 的解决方案非常简洁，写得很好，会逐步引导你的思维。每次看一个解决方案时，你可以看到一半开始自己动手，无需看完全文。

这种安排就很棒了，你自己动手时遇到问题了，还可以模拟从面试官获得提示的过程。虽然最好在没有任何明确提示的情况下独立解决问题，但这本书能有这个选项当然更好。

它的方案代码也很有 Python 风格。我发现就算我找出了正确的思路，再看一遍作者解决问题的简洁思路也有助于训练编写格式优雅的 Python 代码。

如果你认为 Python 不是最强的面试语言，那么本书也有 Java 和 C++ 版本，可能更适合你。这些版本的写作风格和内容也同样出色。

Byte-Byte 的 50 道编程面试问题

我们自己也制作了一组问题列表可以作为上述资源的良好补充。你可以 在此 下载免费指南。

如果你正在练习一个特定问题，并需要一些高级指导，那么这些补充材料非常有助于理解和解决问题。

视频资源：

根据你的时间表和学习习惯，观看视频内容可能是准备谷歌面试的首选方式。假设你的知识基础薄弱，那么可以看像 Coursera 和 Udacity 这样的网站提供的内容，这些网站专注于计算机科学、数据结构、算法等基础知识。

如果你在数据结构和算法方面有扎实的基础，那么观看谷歌面试中遇到的特定类型问题相关的视频内容做训练更好。

可以看看我们的 Youtube 频道。我们已经针对某些问题类型制作了视频列表，其中包括适合初学者的动态编程、图形、递归和数组教程。这些视频都放在了我们的编程面试问题 播放列表 里。

作者介绍

Vincent Russo 是 Byte by Byte 的撰稿人，也是一名全职开发者。他还运营着 LucidProgramming 这个 YouTube 频道，可以帮助开发者提升编程技能和个人价值。LucidProgramming 的内容以 Python 开发为主，其中涉及的主题包括数据结构、算法、Web 抓取、自然语言处理等等。

查看英文原文：

https://www.byte-by-byte.com/google-interview/


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK