一次谷歌面试趣事

『算法有时候很有趣，万物皆是数！此文属于转载，目的是保存一份在这里。』

 

很 多年前我进入硅谷人才市场，当时是想找一份高级工程师的职位。如果你有一段时间没有面试过，根据经验，有个非常有用的提醒你应该接受，就是：你往往会在前 几次面试中的什么地方犯一些错误。简单而言就是，不要首先去你梦想的公司里面试。面试中有多如牛毛的应该注意的问题，你可能全部忘记了，所以，先去几个不 太重要的公司里面试，它们会在这些方面对你起教育(再教育)作用。

我 第一家面试的公司叫做gofish.com，据我所知，gofish这家公司如今的情况跟我当时面试时完全的不同。我几乎能打保票的说，当时我在那遇到的 那些人都已不再那工作了，这家公司的实际情况跟我们这个故事并不是很相关。但在其中的面试却是十分相关的。对我进行技术性面试的人是一个叫做Guy的家 伙。

Guy穿了一条皮裤子。众所周知，穿皮裤子的面试官通常是让人“格外”恐怖的。而Guy也没有任何让人失望的意思。他同样也是一个技术难题终结者。而且是一个穿皮裤子的技术难题终结者 —— 真的，我做不到他那样。

我永远不会忘记他问我的一个问题。事实上，这个问题是非常的普通 —— 在当时也是硅谷里标准的面试题。

问题是这样的：

假设这有一个各种字母组成的字符串，假设这还有另外一个字符串，而且这个字符串里的字母数相对少一些。从算法是讲，什么方法能最快的查出所有小字符串里的字母在大字符串里都有？

比如，如果是下面两个字符串：

String 1: ABCDEFGHLMNOPQRS

String 2: DCGSRQPOM

答案是true，所有在string2里的字母string1也都有。如果是下面两个字符串：

String 1: ABCDEFGHLMNOPQRS

String 2: DCGSRQPOZ

答案是false，因为第二个字符串里的Z字母不在第一个字符串里。

当他问题这个问题时，不夸张的说，我几乎要脱口而出。事实上，对这个问题我很有信心。(提示：我提供的答案对他来说显然是最糟糕的一种，从面试中他大量的各种细微表现中可以看出来)。

对于这种操作一种幼稚的做法是轮询第二个字符串里的每个字母，看它是否同在第一个字符串里。从算法上讲，这需要O(n*m) 次操作，其中n是string1的长度，m是string2的长度。就拿上面的例子来说，最坏的情况下将会有16*8 = 128次操作。

一个稍微好一点的方案是先对这两个字符串的字母进行排序，然后同时对两个字串依次轮询。两个字串的排序需要(常规情况)O(m log m) + O(n log n) 次操作，之后的线性扫描需要O(m+n) 次操作。同样拿上面的字串做例子，将会需要16*4 + 8*3 = 88加上对两个字串线性扫描的16 + 8 = 24的操作。(随着字串长度的增长，你会发现这个算法的效果会越来越好)

最终，我告诉了他一个最佳的算法，只需要O(n+m) 次 操作。方法就是，对第一个字串进行轮询，把其中的每个字母都放入一个Hashtable里(成本是O(n)或16次操作)。然后轮询第二个字串，在 Hashtable里查询每个字母，看能否找到。如果找不到，说明没有匹配成功。这将消耗掉8次操作 —— 这样两项操作加起来一共只有24次。不错吧，比前面两种方案都要好。

Guy没有被打动。他把他的皮裤子弄的沙沙响作为回应。”还有没有更好的？“他问道。

我的天？这个家伙究竟想要什么？我看看白板，然后转向他。”没有了，O(n+m)是你能得到的最好的结果了 —— 我是说，你至少要对每个字母至少访问一次才能完成这项操作 —— 而这个方案是刚好是对每个字母只访问一次“。我越想越确信我是对的。

他 走到白板前，”如果这样呢 —— 假设我们有一个一定个数的字母组成字串 —— 我给每个字母分配一个素数，从2开始，往后类推。这样A将会是2，B将会是3，C将会是5，等等。现在我遍历第一个字串，把每个字母代表的素数相乘。你最 终会得到一个很大的整数，对吧？然后 —— 轮询第二个字符串，用每个字母除它。如果除的结果有余数，这说明有不匹配的字母。如果整个过程中没有余数，你应该知道它是第一个字串恰好的子集了。这样不 行吗？“

每当这个时候 —— 当某个人的奇思异想超出了你的思维模式时，你真的需要一段时间来跟上他的思路。现在他站在那里，他的皮裤子并没有帮助我理解他。

现 在我想告诉你 —— Guy的方案(不消说，我并不认为Guy是第一个想出这招的人)在算法上并不能说就比我的好。而且在实际操作中，你很可能仍会使用我的方案，因为它更通 用，无需跟麻烦的大型数字打交道。但从”巧妙水平“上讲，Guy提供的是一种更、更、更有趣的方案。

我没有得到这份职位。也许是因为我拒绝了他们提供给我的一些讨厌的工作内容和其它一些东西，但这都无所谓了。我还有更大更好的目标呢。

接 着，我应聘了become.com。在跟CTO的电话面试中，他给我布置了一道”编程作业“。这个作业有点荒唐 —— 现在回想起来，大概用了我3天的时间去完成。我得到了面试，得到了那份工作 —— 但对于我来说，最大的收获是这道编程作业强迫我去钻研并有所获。我需要去开发一个网页爬虫，一个拼写检查/纠正器，还有一些其它的功能。不错的东西。然 而，最终，我拒绝了这份工作。

终于，我来到了Google面试。我曾说过Google的面试过程跟外面宣传的很一致。冗长 —— 严格，但诚实的说，相当的公平。他们在各种面试过程中尽最大的努力去了解你、你的能力。并不是说他们在对你做科学研究，但我确信他们是努力这样做。

我在Google的第四场面试是一个女工程师，老实话，是一场很无聊的面试。在前面几场面试中我表现的很好，感觉到我的机会非常的大。我相信如果不做出什么荒唐事情来，十拿九稳我能得到这份工作。

她问了我一些关于排序或设计方面的非常简单的问题，我记不清了。但就在45分钟的面试快要结束时，她对我说”我还有一个问题。假设你有一个一定长度的由字母组成的字符串。你还有另外一个，短些。你如何才能知道所有的在较短的字符串里的字母在长字符串里也有？“

哇塞。Guy附身了。

现 在，我完全可以马上结束这场面试。我可以对她说“哈哈，几个星期前我就知道答案啦！”，这是事实。但就是在几个星期前被问到这个问题时 —— 我给出的也是正确的答案。这是我本来就知道答案的问题。看起来就好像是Guy为我的这次面试温习过功课一样。而且，可恶，人们通常是通过上网来搜集面试问 题 —— 而我，我可以毫不客气的说，对于这些问题，我不需要任何“作*弊”。我自己知道这些答案！

现 在你们可能认为——就在她问出了问题之后，在我准备开始说出在脑海里构思完成的最后的演讲之前——你们可能会想，我应该是，当然该，从情理上讲，镇定的回 答出这个问题，并且获得赞赏。可糟糕的是，事实并不是这样。打个比喻，就像是她问出来问题后，我在闹子里立即举起了手，并大叫着“我！嗨！嗨！我知道！让 我来回答吧！”我的大脑试图夺走我对嘴巴的控制权(这事经常发生)，幸亏我坚强的毅力让我镇定下来。

于是我开始回答。平静的。带着不可思议的沉着和优雅。带着一种故意表现出来的 —— 带着一种，我认为，只有那种完全的渊博到对古今中外、不分巨细的知识都精通的人才能表现出来的自信。

我轻描淡写的说出来那种很幼稚的方案，就好象是这种方案毫无价值。我提到了给它们排序，就好像是在给早期的《星际迷航》中的一个场景中的人物穿上红T恤似的。最后，平淡的，就好像是我决定了所有事情的好坏、算法上的效率，我说出了O(n+m) 一次性方案。

我要告诉你——尽管我表明上的平静——这整个过程我却在做激烈的挣扎，内心里我在对自己尖着——“你个笨蛋，赶紧告诉她素数方案！”

当我完成了对一次性算法的解释后，她完全不出意外的认可的点了下头，并开始在笔记本上记录。这个问题她以前也许问过了一百次，我想大部分的人都能回答上来。她也许写的是“回答正确。无聊的面试。正确的回答了无聊的字符串问题。没有惊喜。无聊的家伙，但可以留下。”

我等了一会。我让这种焦灼的状态持续的尽可能的长。我可以发誓的说，如果再耽搁一分钟，我一定会憋出脑血栓、脱口说出关于素数的未解之谜。

我打破了沉默。“你知道吗，还有另外一个，可能是更聪明的算法。”

她二目空空的抬头看了一眼，仅在瞬间闪现过一丝希望。

“假设我们有一定长度的字符串。我们可以给每个字母分配一个素数，从2开始。然后我们把大字串中的每个字母代表的素数相乘得出一个数，用小字串中的每个字母代表的素数去除它。如果除的过程中没有产生余数，则小字串是大字串的一个子集。”

在此时，我猜，她看起来就像是Guy当时把相同的话说给我听时我表现出来的样子。而我演讲时泰然自若的表情没了，眼睛瞪大，说话时稍微带出来一些唾沫星子。

一会儿后，她不得不说了，“可是…等一下，有可能…是的，可以这样！可是如何…如果…噢，噢，可行！简洁！”

我得意洋洋的吸了一口气。我在我的面试记录里写下了“她给了我一个‘简洁’的评语！”在她提出这个问题之前我就确信能得到这份工作，现在我更加确信了。还有一点我十分确信的是，我(更准确的说是Guy)给了她今天的好心情。

我在Google干了3年，生活的十分愉快。我在2008年辞职去到一个小公司里做CTO，之后又开办了一个自己的公司。大概是一年前，我偶然的在一个创业论坛会上遇到了Guy，他记不得我了，当我向他细述这段往事时，他对他那条皮裤子大笑不已。

话说回来，如果这个故事里有什么教育意义的话——永远不要冒失的首先去应聘你梦想的公司，应先去应聘那些你不看好的职位。你除了能从这些面试中获得经验外，你指不定能遇到某个能为你的更重要的面试铺路的人呢。事实上，这个经验在你生活中的很多其它事情上也适应。

说正经的，如果你有机会想找一个解决问题的高手——雇佣Guy比谁都强。那个家伙很厉害。

(在 这些陈年旧账里发现的一点技术瑕疵：字母有可能重复而字符串可能会很长，所以必须要有统计。用那个最幼稚的解决方案时，当在大字符串里找到一个字符后就把 它删掉，当这样仍然是 O(n*m)次。在Hashtable里我们会有一个key->value的计数。Guy的方案在这种情况下仍然好用。)

注，英文链接http://paultyma.blogspot.com/2010/11/google-interviewing-story.html

评论

1 楼 saieuler 2012-09-18  

我一字不漏的看完了。永远不要冒失的首先去应聘你梦想的公司！