一次谷歌面试趣事
我第一家面試的公司叫做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 theO(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.
總結
- 上一篇： 岚图卖不动，到底谁的锅？
- 下一篇： 十进制转化为16进制