两个星期之前的一个周五下午，我正在家里寂寞的学着JS，一封突然到来的邮件打破了我宁静的生活——”Greeting from Google!“。眼看明年的工作还没着落，我欣然接受了邮件里的面试邀请。跟一个Google中国的HR用英文发邮件是件很奇怪的事儿，不过HR很给力，我的面试日期很快就定下来了。

Google面试的风格跟我面的其他公司很不一样，每次都会要求自我介绍——就是介绍自己的项目。各位有志于Google的童鞋最好先准备一下。顺便提一句，我每次说的项目都不一样哦。

一面是这样的，首先是自我介绍——blablabla说了点。然后是一道很无趣的遍历二叉树的题，面试官规定了我需要实现的函数的原型，让我先说说想法然后写代码。我说了一个做法，然后实现了另外一个（囧）。最后面试官给了一道题目：

求一个数字集合里最长的连续数字串的长度。例如{ 1 2 9 10 11 3 12 7}中的{ 9 10 11 12}

我的第一反应当然是排序了。面试官问有没有更好的解法，经过他的提示我想到了Hash。但是在估计复杂度的时候，面试官坚决不同意我“可以认为Hash中的冲突很少”的看法。所以我得到了O(N^2)的复杂度。事后我一想，不能认为Hash冲突很少我还用个毛Hash 啊！面试完的那个晚上我没有睡着，脑子里全是这个问题，但是没有找到更好的方法。请问各路大神，这题有没有更优的解法？

二面同样给我留下了深刻的印象。自我介绍，blablabla。面试官出的第一题是从一个数字串中找到最长的递增子串。很显然是O(N)的对吧，面试官问我有没有更优的。我嗯啊呀哈了五分钟之后，面试官说，如果要求递增的差为1，有没有更优的方法？我….扯了一个没有用的方法给他。第二题是二合一，首先面试官要求我求出一个线段集合里相交的线段。我先搞了一个naive的线段合并，可以判断出某线段是否和别的线段相交。之后面试官增加了要求：

输出线段集合中的相交线段的子集，如果线段A, B, C, D中，A, B, D两两相交，B和C相交，A和C不相交，输出集合{A B D}和{B C}。

我首先给出了离散化并查集的O(N^2)方法。有没有更优的？我当场怀疑这样的集合会有O(N)个，每个会有O(N)个元素。但是当时没有找到这样的例子，于是扯了一个Splay延迟标记维护的方法并号称是O(NlogN)的。事实证明，还是存在能让输出复杂度达到O(N^2)的例子的。我又花了一个晚上才想到的这个例子。

不管怎么样，我拿到了Onsite的资格（八成是考虑到竞争对手的Offer吧）。Onsite就靠谱多了，至少题目都是可以答的。

一面第一步照例是自我介绍，blablabla。第二步是个不太难的题目，跟线段相关的。题目不重要，重要的是面试官首先要求我详细的叙述我的想法，之后在纸上写伪代码，最后要求我翻译成代码，并且要用设计合理的函数完成这个程序。第三步是个加强版的题目，因为时间不多了我草草写了几笔。

中午跟面试官一起吃了饭，畅谈了一下人生理想。面试官建议我不要急着工作，先去旅旅游见见世面，还跟我分享了他当年单独去越南旅游的经历。我本来还想明年先来实习呢，但是现在觉得，玩儿命工作还是享受人生，这是个问题。顺便说一句，Google上海的自助餐厅大概只能容纳100人，借此可以估计一下Google上海的规模。另外，盛传Google中国没有什么技术类的活，其实不是的，他们还是负担着非常多的开发任务的。

二面的面试官是一个比较威严的工程师。他的题目也很有意思，都是比较偏向于数学的，每次除了描述想法之外，还要求有非形式化的证明。他在我证明的过程中要求我澄清几乎每个概念，力求严谨。猴神可能会比较喜欢这样的题目。两道这样的题目之后，面试官出了一道Design的题目，要求我设计一个关于指针的工具类，并独立做出各种决策。在考虑了N多问题之后，我卡在了拷贝的实现策略中，超时了。面试官安慰我说这样的题目是没有一个固定的答案的，讨论的过程更重要。

这样我的四次面试就结束了。虽然我自我感觉良好，但是我的表现实在不很完美。也许我应该等结果出来再来写这篇得瑟的博客。但是现在，我还是抓紧享受一下生活吧。