记一次 Google 面试经历

这是我上周去面试的地方。很顺利，我觉得——至少我认为我已经尽我所能，并且无论发生什么事情对我都是有帮助的。

由于我签署了保密协议，所以我不能把他们问我的问题写出来。但是，我可以写我大概的面试过程，以及我做了哪些准备。

首先，这是谷歌——所以我当然不会让我在那里工作的朋友不推荐我。我没有经过电话采访，因为我是“本地”的，所以我被直接邀请到公司面试。我个人认为，面对面绝对比电话面试好，我很幸运。

首先，我和招聘人员很简短地聊了一下，他告诉我我需要使用白板和进程，然后是两个软件工程师分别对我进行了45分钟一对一的两场面试。然后我很惊讶自己居然发现了面试的乐趣！通常情况下我在面试时感受到的只有压力，但是Google的面试真的很棒，因为没有笨蛋的参与，不会有对牛弹琴的尴尬。超酷！第一场面试的问题相当容易，而第二场则有点难，但也不算太糟糕。可能最困难的是在白板（而非计算机！）上写代码——在白板上很难做TDD！他们告诉你没有必要盛装出席，因此绝对不要装扮仪表——因为你需要坐在地板上写代码，而且不是一时半会就可以在白板上写完的，还会写得满手都是油墨。想象一下如果你穿着裙子会怎么样！

他们发给我了一系列很有帮助的面试准备。由于我坚实的学习基础，所以在一定程度上我都有所涉猎。此外平时我还会做这些事情——及时了解最新的行业新闻，广泛使用Google产品，写博客，以及思考技术如何改变我们的生活（是的，最后两件事情很有帮助）。我会深刻理解和使用Java 5的新产品，例如Generics，Enums，for-each等。

下面是我准备的内容（所有的图书链接均链接到Amazon）：

• 阅读《Effective Java》（第2版）——不带任何夸大之词，这本书助我成为了一名合格的Java程序员。
• 阅读《Programming Interviews Exposed（编程面试攻略）》，并通过所有练习——概述和复习基本的数据结构，如列表和树。递归部分没有我自己学到的那么强大（因为我有着函数背景），它反而主张编写迭代方法，不过除此之外，这的确是一本既非常好又有用的书。
• 阅读《Coders at Work》——这本书中谈到了很多的谷歌人，表达了作者对文化的观点。它还介绍了很多我不知道的却又非常有趣的编程历史，以及关于这些历史伟人如何解决问题的见解，以及对于API、可扩展性等的讨论。
• 《Combinatorial Algorithms: Generation, Enumeration, and Search》（我几乎看过整本书，并上过一门关于组合算法（Combinatorial Algorithms）的课程）——说实话，我不是这本书的狂热爱好者。我觉得这本书的数学符号气息太重。因为我们是程序员，而不是数学家，所以使用实际代码来解决问题可能更有帮助，并且维基百科几乎可以肯定更具可读性。
• 研究《Java Puzzlers》——有助于培养钻研代码，研究问题的心态。虽然并没有人要求我这么去做，但我确实需要批判性地看待自己的代码。IBM的面试中就提到了关于EB手机屏幕的问题，而且谷歌也用了那一类的问题。
• 复习并发问题——死锁、活锁、 互斥锁、内核锁、信号量等。什么时候在Java中使用synchronized关键字？如何避免死锁？如何避免活锁？
• 复习树的遍历——前序，中序，后序。深度优先搜索vs.广度优先搜索。 A *，Dijkstra算法等。
• 复习平衡二叉树——红黑树、AVL树、伸展树。
• 复习图表。表示图，最小生成树，搜索等。
• 运行时分析。
• 6种排序算法编码——包括关键的时间复杂度为n log n的算法——TDD风格（测试驱动开发——关于我的测试案例请看这个帖子）。
• 哈希表编码，只使用数组。包括：泛型，动态数组，延迟初始化。此外还有测试先行。
• 做一做所有手头可以获取的实践问题——搜索“谷歌面试问题”，但不要浪费时间在什么面试预测或井盖问题上，要找类似问题——有时，我在Eclipse中编码，但有时在Google文档中。我喜欢和朋友一起工作，他会审查我的代码，并提出问题。
• 和已经在那里工作多年的朋友交谈。问很多问题。他真的很赞，帮我做了很多的准备工作。不仅如此，了解他为什么认为我会是一个不错的求职者，以及他为什么会相信我可以做好，有助于我知道自己为什么要在那里工作（这是一个老生常谈的问题，虽然这家公司是Google，但正如我的一个导师说的那样，你想为他们工作的热切程度得和他们想要你的程度差不多）。

我的Google朋友说我做了“疯狂的准备”，甚至可以说我做了充分的准备——那么，除此之外，我还做了什么呢？

• 更多地运行时分析——尽可能多找到代码进行分析。
• 计算总和。例如，如何计算1至n的和？事实证明是有用的。第二次面试中就涉及到了回放运行时分析，因为我有一些东西看起来是这样的：（n-1）（n-2）+（n-2）（n-3）+ … +（3）（2）+（2 ）（1）。当然，我并没有在当时创建它，所以它的时间复杂度上限为O（n³）。
• 复习Java库的数据结构。有一回，我说了这样的话，“我知道一个不重复的数据结构，但我现在一时想不起它的名字”。后来在当天下午我想起来了。
• 复习库方法，复习一些关键的东西——数组和字符串将会很有帮助。
• 在白板或纸上练习编码。也许你理所当然地认为插入行或重构很简单，事实上，当你在白板上写代码的时候，肯定没有在计算机上趁手。而且我们很容易忘记返回语句——Eclipse中不需要我们这么做。因此我倾向于先写声明和返回语句，然后再在中间补上代码——当然，在白板上可不能这么做！

接下来要说的是？

Waiting。
Waiting。
Waiting！

无论发生什么，我都希望能得到一些反馈。

编码面试问题（以及测试用例！）

完成《Java Puzzlers》。

充分利用时间——我花了很多时间来做好诸多准备工作。

调查其他公司。特别是——与IBM员工见面，看看有没有什么东西适合用于Google。

听取导师的意见。