一次谷歌面试趣事

清疚 2022-08-07 06:51 234阅读 0赞

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

我第一家面试的公司叫做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的方案在这种情况下仍然好用。)

修改：11/30/10 —— 本文中提到的Guy看到了这篇文章，并在评论中做了澄清。值得一读。

### A Google Interviewing Story ###

A few years ago I was entering the Silicon Valley job market and at that time looking for senior engineering positions. A good rule of thumb about interviewing if you haven't done it in awhile is to at least somewhat accept that you'll probably make a few mistakes on your first few tries. Simply, don't go for your dream job first. There are a million nuances to interviewing that you've forgotten, and a few up-front, not-so-important interviews first will educate (or re-educate) about them.  
  
One of the first places I interviewed was a company called gofish.com. As far as I know - gofish is an utterly different company now than when I interviewed there. I'm almost sure that everyone I met there no longer works there, so the actual company isn't terribly relevant to the story. But the interviewer is. My technical interview there was with a guy named Guy.  
  
Guy wore leather pants. Its a well-known fact that interviewers in leather pants are "extra" scary. And Guy was by no means a let down. He was also a technical crack-shot. And he was a technical crack-shot in leather pants - seriously, I didn't have a chance.  
  
One question he asked me I'll never forget. In truth, its a pretty innocuous question - but it's also pretty standard fare for silicon valley interviewing questions at that time.  
  
Here it is:  
  
Say you have one string of alphabetic characters, and say you have another, guaranteed smaller string of alphabetic characters. Algorithmically speaking, what's the fastest way to find out if all the characters in the smaller string are in the larger string?  
  
For example, if the two strings were:  
  
  
String 1: ABCDEFGHLMNOPQRS  
String 2: DCGSRQPOM  
  
  
You'd get true as every character in string2 is in string1. If the two strings were:  
  
  
String 1: ABCDEFGHLMNOPQRS  
String 2: DCGSRQPOZ  
  
  
you'd get false as Z isn't in the first string.  
  
When he asked the question I literally jumped to my feet. Finally, a question I could answer with some confidence. (Note my answer to him was solely considering the worst cases as there are plenty enough nuances there for an interview question).  
  
The naive way to do this operation would be to iterate over the 2nd string once for each character in the 1st string. That'd be O(n\*m) in algorithm parlance where n is the length of string1 and m is the length of string2. Given the strings in our above example, thats 16\*8 = 128 operations in the worst case.  
  
A slightly better way would be to sort each string and then do a stepwise iteration of both sorted strings simultaneously. Sorting both strings would be (in the general case) O(m log m) + O(n log n) and the linear scan after that is O(m+n). Again for our strings above, that would be 16\*4 + 8\*3 = 88 plus a linear scan of both strings at a cost of 16 + 8 = 24. Thats 88 + 24 = 112 total operations. Slightly better. (As the size of the strings grow, this method would start to look better and better)  
  
Finally, I told him the best method would simply be O(n+m). That is, iterate through the first string and put each character in a hashtable (cost of O(n) or 16). Then iterate the 2nd string and query the hashtable for each character you find. If its not found, you don't have a match. That would cost 8 operations - so both operations together is a total of 24 operations. Not bad and way better than the other solutions.  
  
Guy wasn't impressed. He showed it by rustling his leather pants a bit. "Can you do better?" he asked.  
  
What the heck? What did this guy want? I looked at the whiteboard and turned back to him. "No, O(n+m) is the best you have - I mean, you can't do this without looking at each character at least once - and this solution is looking at each character precisely once". The more I thought about it, the more I knew I was right.  
  
He stepped up to the whiteboard, "What if - given that we have a limited range of possible characters - I assigned each character of the alphabet to a prime number starting with 2 and going up from there. So A would be 2, and B would be 3, and C would be 5, etc. And then I went through the first string and 'multiplied' each character's prime number together. You'd end up with some big number right? And then - what if I iterated through the 2nd string and 'divided' by every character in there. If any division gave a remainder - you knew you didn't have a match. If there was no remainders through the whole process, you knew you had a subset. Would that work?"  
  
Every once in awhile - someone thinks so fantastically far out of your box you really need a minute to catch up. And now that he was standing, his leather pants weren't helping with this.  
  
Now mind you - Guy's solution (and of course, needless to say I doubt Guy was the first to ever think of this) was algorithmically speaking no better than mine. Even practically, you'd still probably use mine as it was more general and didn't make you deal with messy big integers. But on the "clever scale", Guy's was way, way, (way) more fun.  
  
I didn't get the job. Or I think they offered me some trial position or something that I refused, but it didn't matter. I was on to bigger and better things.  
  
Next, I interviewed at become.com. After a phone interview with the CTO he sent me a "programming assignment". It was a bit over the top - but in retrospect, worth the 3 days it took me to complete. I got an interview and a job offer - but the biggest value was what the programming assignment forced me to go out and learn. I had to build a web-crawler, a spellchecker/fixer, and a few other things. Good stuff. In the end however, I turned down the offer.  
  
Finally, I had an interview at Google. I've written before that the Google interviewing process does tend to live up to the hype. Its long - its rigorous and in all honesty, pretty darn fair. They do as best they can to learn about you and your abilities in an interview setting. By no means is that an exact science, but I'm convinced they give it a good try.  
  
My 4th technical interview at Google was with a woman engineer that honestly seemed a bit bored of interviewing. I had done well in all my previous interviews there and was feeling pretty good about my chances. I was confident that if I did nothing ridiculously silly - I'd get the job.  
  
She asked me a few softball questions about sorting or design, I'm not sure. But towards the end of our 45 minutes she told me "I have one more question. Let's say you have a string of alphabetic characters of some length. And you have another, shorter string of characters. How would you go about finding if all the characters in the smaller string are in the larger string?"  
  
Woah. Deja-Guy.  
  
Now, I could have probably stopped the interview right there. I could have said "Ahee! I just got this question a few weeks ago!" which was true. But when I was asked it a few weeks previous - I did get it right. It truly was a question I knew the answer to. Almost as if Guy had been one of my study partners for this very interview. And heck, people study interview questions on the internet all the time - by me non-chalantly answering the question I wouldn't be "lying" in any way. I did know the answer on my own!  
  
Now you might think, that in the instant after her asking, and before the moment of time that I began speaking that the entire last paragraph sequenced through my thought process rationalizing that I was, indeed, morally in the right to calmly answer the question and take credit for the answer. But sadly, that wasn't the case. Metaphorically, it was more like she asked the question and my brain immediately raised its hand and started shouting "Me! ooh! ooh! ooh me! I know! ask me!" My brain kept trying to wrestle mouth-control away from me (which happens plenty) but only by stalwart resolve was I able to retain composure.  
  
So I answered. Calmly. With almost unearthly grace and poise. And with a purposeful demeanor - with, I think, a confidence that only someone with complete and encyclopedic knowledge of this timeless and subtle problem would hold.  
  
I breezed over the naive solution as if it were unworthy. I mentioned the sorting solution as if it were wearing a red-shirt on an early episode of Star Trek. And finally, nonchalantly, almost as if I had invented all things good and algorithmically efficient, mentioned the O(n+m) linear solution.  
  
Now mind you - despite my apparent poise - the entire time I was fighting my brain who, internally, was screaming at me -- "TELL HER THE PRIME NUMBER SOLUTION YOU DIMWIT !"  
  
I ignored his pitiful pleas.  
  
As I finished the linear solution explanation, her head dutifully sank with complete non-surprise and she started writing in her notes. She had probably asked that question a hundred times before and I'd guess most people got it right. She probably wrote "yep. boring interview. got boring string question right. no surprise. boring guy but probable hire"  
  
I waited a moment. I let the suspense build as long as possible. I am truly convinced that even a moment longer would have resulted in my brain throwing itself fully into an embolism resulting in me blurting out unintelligible mis-facts about prime numbers.  
  
I broke the calm. "You know, there is another, somewhat cleverer solution"  
  
She lethargically looked up with only a glimmer of hope.  
  
"Given that our range of characters is limited. We could assign each character to a prime number starting at 2. After that we could 'multiply' each character of the large string and then 'divide' by each character of the small string. If the division operation left no remainder, we'd know we have a subset."  
  
I'm guessing that at this point, she looked pretty much as I did when Guy had said the same thing to me. General loss of composure, one pupil was dilated, slight spitting while talking.  
  
After a moment, she blurted "But.. wait that wouldn'... yes it would! But how.. what if.. wow. wow. that works! Neat!"  
  
I sniffed triumphantly. I wrote down "She gave me a 'Neat!'" in my interviewing notes. I'm pretty sure I was getting the job before that question, but it was pretty clear that I was in for sure now. What's more, I'm pretty confident that I (or more precisely, Guy) had just made her day.  
  
I spent 3 years working at Google and had a great time. I quit in 2008 to CTO a new startup and have subsequently started another of my own after that. About a year ago I randomly met Guy at a start-up party who had no idea who I was but when I recounted this story he nearly peed his leather pants laughing.  
  
Again, if there is a moral here - it's to never chase your dream job before you chase a few you're willing to fail at. Apart from the interviewing experience you'll gain, you never know who might just get you ready for that big interview. In fact, that rule just might work for a lot of things in life.  
  
And seriously, if you get the chance and you're looking to hire a crackshot engineer - you could do far worse than hiring Guy. That dude knows things.  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
*(a bit of nitpicky technical detail for the fusty: characters may repeat so strings can be very long and thus counts must be kept. The naive solution can remove a character when it finds it from the large string to do that but its remains O(n\*m). The hashtable solution can keep a count as the value of the key->value. Guy's solution still works just fine)*  
  
  
Edit: 11/30/10 - Guy from the story has found this post and gave some clarification in the comments. Worth the read.