我在谷歌的一次有趣的面試經(jīng)歷
很多年前我進(jìn)入硅谷人才市場，當(dāng)時是想找一份高級工程師的職位。
如果你有一段時間沒有面試過，根據(jù)經(jīng)驗，有個非常有用的提醒你應(yīng)該接受，就是：你往往會在前幾次面試中的什么地方犯一些錯誤。簡單而言就是，不要首先去你夢想的公司里面試。
面試中有多如牛毛的應(yīng)該注意的問題，你可能全部忘記了，所以，先去幾個不太重要的公司里面試，它們會在這些方面對你起教育(再教育)作用。
我***家面試的公司叫做gofish.com，據(jù)我所知，gofish這家公司如今的情況跟我當(dāng)時面試時完全的不同。我?guī)缀跄艽虮Ｆ钡恼f，當(dāng)時我在那遇到的那些人都已不再那工作了，這家公司的實際情況跟我們這個故事并不是很相關(guān)。但在其中的面試卻是十分相關(guān)的。對我進(jìn)行技術(shù)性面試的人是一個叫做Guy的家伙。
Guy穿了一條皮褲子。眾所周知，穿皮褲子的面試官通常是讓人“格外”恐怖的。而Guy也沒有任何讓人失望的意思。他同樣也是一個技術(shù)難題終結(jié)者。而且是一個穿皮褲子的技術(shù)難題終結(jié)者 —— 真的，我做不到他那樣。
我永遠(yuǎn)不會忘記他問我的一個問題。事實上，這個問題是非常的普通 —— 在當(dāng)時也是硅谷里標(biāo)準(zhǔn)的面試題。
問題是這樣的：假設(shè)這有一個各種字母組成的字符串，假設(shè)這還有另外一個字符串，而且這個字符串里的字母數(shù)相對少一些。從算法是講，什么方法能最快的查出所有小字符串里的字母在大字符串里都有？
比如，如果是下面兩個字符串：
String 1: ABCDEFGHLMNOPQRS
String 2: DCGSRQPOM
答案是true，所有在string2里的字母string1也都有。如果是下面兩個字符串：
String 1: ABCDEFGHLMNOPQRS
String 2: DCGSRQPOZ
答案是false，因為第二個字符串里的Z字母不在***個字符串里。
當(dāng)他問題這個問題時，不夸張的說，我?guī)缀跻摽诙?。事實上，對這個問題我很有信心。(提示：我提供的答案對他來說顯然是最糟糕的一種，從面試中他大量的各種細(xì)微表現(xiàn)中可以看出來)。
對于這種操作一種幼稚的做法是輪詢第二個字符串里的每個字母，看它是否同在***個字符串里。從算法上講，這需要O(n*m)次操作，其中n是string1的長度，m是string2的長度。就拿上面的例子來說，最壞的情況下將會有16*8 = 128次操作。
一個稍微好一點的方案是先對這兩個字符串的字母進(jìn)行排序，然后同時對兩個字串依次輪詢。兩個字串的排序需要(常規(guī)情況)O(m log m) + O(n log n)次操作，之后的線性掃描需要O(m+n)次操作。同樣拿上面的字串做例子，將會需要16*4 + 8*3 = 88加上對兩個字串線性掃描的16 + 8 = 24的操作。(隨著字串長度的增長，你會發(fā)現(xiàn)這個算法的效果會越來越好)
最終，我告訴了他一個***的算法，只需要O(n+m)次操作。方法就是，對***個字串進(jìn)行輪詢，把其中的每個字母都放入一個Hashtable里(成本是O(n)或16次操作)。然后輪詢第二個字串，在Hashtable里查詢每個字母，看能否找到。如果找不到，說明沒有匹配成功。這將消耗掉8次操作 —— 這樣兩項操作加起來一共只有24次。不錯吧，比前面兩種方案都要好。
Guy沒有被打動。他把他的皮褲子弄的沙沙響作為回應(yīng)。“還有沒有更好的？”他問道。
我的天？這個家伙究竟想要什么？我看看白板，然后轉(zhuǎn)向他。“沒有了，O(n+m)是你能得到的***的結(jié)果了 —— 我是說，你至少要對每個字母至少訪問一次才能完成這項操作 —— 而這個方案是剛好是對每個字母只訪問一次。”我越想越確信我是對的。
他走到白板前，“如果這樣呢 —— 假設(shè)我們有一個一定個數(shù)的字母組成字串 —— 我給每個字母分配一個素數(shù)，從2開始，往后類推。這樣A將會是2，B將會是3，C將會是5，等等?，F(xiàn)在我遍歷***個字串，把每個字母代表的素數(shù)相乘。你最終會得到一個很大的整數(shù)，對吧？然后 —— 輪詢第二個字符串，用每個字母除它。如果除的結(jié)果有余數(shù)，這說明有不匹配的字母。如果整個過程中沒有余數(shù)，你應(yīng)該知道它是***個字串恰好的子集了。這樣不行嗎？”
每當(dāng)這個時候 —— 當(dāng)某個人的奇思異想超出了你的思維模式時，你真的需要一段時間來跟上他的思路。現(xiàn)在他站在那里，他的皮褲子并沒有幫助我理解他。
現(xiàn)在我想告訴你 —— Guy的方案(不消說，我并不認(rèn)為Guy是***個想出這招的人)在算法上并不能說就比我的好。而且在實際操作中，你很可能仍會使用我的方案，因為它更通用，無需跟麻煩的大型數(shù)字打交道。但從巧妙水平上講，Guy提供的是一種更、更、更有趣的方案。
我沒有得到這份職位。也許是因為我拒絕了他們提供給我的一些討厭的工作內(nèi)容和其它一些東西，但這都無所謂了。我還有更大更好的目標(biāo)呢。
接著，我應(yīng)聘了become.com。在跟CTO的電話面試中，他給我布置了一道“編程作業(yè)”。這個作業(yè)有點荒唐 —— 現(xiàn)在回想起來，大概用了我3天的時間去完成。我得到了面試，得到了那份工作 —— 但對于我來說，***的收獲是這道編程作業(yè)強(qiáng)迫我去鉆研并有所獲。我需要去開發(fā)一個網(wǎng)頁爬蟲，一個拼寫檢查/糾正器，還有一些其它的功能。不錯的東西。然而，最終，我拒絕了這份工作。
終于，我來到了Google面試。我曾說過Google的面試過程跟外面宣傳的很一致。冗長 —— 嚴(yán)格，但誠實的說，相當(dāng)?shù)墓?。他們在各種面試過程中盡***的努力去了解你、你的能力。并不是說他們在對你做科學(xué)研究，但我確信他們是努力這樣做。
我在Google的第四場面試是一個女工程師，老實話，是一場很無聊的面試。在前面幾場面試中我表現(xiàn)的很好，感覺到我的機(jī)會非常的大。我相信如果不做出什么荒唐事情來，十拿九穩(wěn)我能得到這份工作。
她問了我一些關(guān)于排序或設(shè)計方面的非常簡單的問題，我記不清了。但就在45分鐘的面試快要結(jié)束時，她對我說“我還有一個問題。假設(shè)你有一個一定長度的由字母組成的字符串。你還有另外一個，短些。你如何才能知道所有的在較短的字符串里的字母在長字符串里也有？”
哇塞。Guy附身了。
現(xiàn)在，我完全可以馬上結(jié)束這場面試。我可以對她說“哈哈，幾個星期前我就知道答案啦！”，這是事實。但就是在幾個星期前被問到這個問題時 —— 我給出的也是正確的答案。這是我本來就知道答案的問題?？雌饋砭秃孟袷荊uy為我的這次面試溫習(xí)過功課一樣。而且，可惡，人們通常是通過上網(wǎng)來搜集面試問題 —— 而我，我可以毫不客氣的說，對于這些問題，我不需要任何“作弊”。我自己知道這些答案！
現(xiàn)在你們可能認(rèn)為——就在她問出了問題之后，在我準(zhǔn)備開始說出在腦海里構(gòu)思完成的***的演講之前——你們可能會想，我應(yīng)該是，當(dāng)然該，從情理上講，鎮(zhèn)定的回答出這個問題，并且獲得贊賞。可糟糕的是，事實并不是這樣。打個比喻，就像是她問出來問題后，我在鬧子里立即舉起了手，并大叫著“我！嗨！嗨！我知道！讓我來回答吧！”我的大腦試圖奪走我對嘴巴的控制權(quán)(這事經(jīng)常發(fā)生)，幸虧我堅強(qiáng)的毅力讓我鎮(zhèn)定下來。
于是我開始回答。平靜的。帶著不可思議的沉著和優(yōu)雅。帶著一種故意表現(xiàn)出來的 —— 帶著一種，我認(rèn)為，只有那種完全的淵博到對古今中外、不分巨細(xì)的知識都精通的人才能表現(xiàn)出來的自信。
我輕描淡寫的說出來那種很幼稚的方案，就好象是這種方案毫無價值。我提到了給它們排序，就好像是在給早期的《星際迷航》中的一個場景中的人物穿上紅T恤似的。***，平淡的，就好像是我決定了所有事情的好壞、算法上的效率，我說出了O(n+m)一次性方案。
我要告訴你——盡管我表明上的平靜——這整個過程我卻在做激烈的掙扎，內(nèi)心里我在對自己尖著——“你個笨蛋，趕緊告訴她素數(shù)方案！”
當(dāng)我完成了對一次性算法的解釋后，她完全不出意外的認(rèn)可的點了下頭，并開始在筆記本上記錄。這個問題她以前也許問過了一百次，我想大部分的人都能回答上來。她也許寫的是“回答正確。無聊的面試。正確的回答了無聊的字符串問題。沒有驚喜。無聊的家伙，但可以留下。”
我等了一會。我讓這種焦灼的狀態(tài)持續(xù)的盡可能的長。我可以發(fā)誓的說，如果再耽擱一分鐘，我一定會憋出腦血栓、脫口說出關(guān)于素數(shù)的未解之謎。
我打破了沉默。“你知道嗎，還有另外一個，可能是更聰明的算法。”
她二目空空的抬頭看了一眼，僅在瞬間閃現(xiàn)過一絲希望。
“假設(shè)我們有一定長度的字符串。我們可以給每個字母分配一個素數(shù)，從2開始。然后我們把大字串中的每個字母代表的素數(shù)相乘得出一個數(shù)，用小字串中的每個字母代表的素數(shù)去除它。如果除的過程中沒有產(chǎn)生余數(shù)，則小字串是大字串的一個子集。”
在此時，我猜，她看起來就像是Guy當(dāng)時把相同的話說給我聽時我表現(xiàn)出來的樣子。而我演講時泰然自若的表情沒了，眼睛瞪大，說話時稍微帶出來一些唾沫星子。
一會兒后，她不得不說了，“可是…等一下，有可能…是的，可以這樣！可是如何…如果…噢，噢，可行！簡潔！”
我得意洋洋的吸了一口氣。我在我的面試記錄里寫下了“她給了我一個‘簡潔’的評語！”在她提出這個問題之前我就確信能得到這份工作，現(xiàn)在我更加確信了。還有一點我十分確信的是，我(更準(zhǔn)確的說是Guy)給了她今天的好心情。
我在Google干了3年，生活的十分愉快。我在2008年辭職去到一個小公司里做CTO，之后又開辦了一個自己的公司。大概是一年前，我偶然的在一個創(chuàng)業(yè)論壇會上遇到了Guy，他記不得我了，當(dāng)我向他細(xì)述這段往事時，他對他那條皮褲子大笑不已。
話說回來，如果這個故事里有什么教育意義的話——永遠(yuǎn)不要冒失的首先去應(yīng)聘你夢想的公司，應(yīng)先去應(yīng)聘那些你不看好的職位。你除了能從這些面試中獲得經(jīng)驗外，你指不定能遇到某個能為你的更重要的面試鋪路的人呢。事實上，這個經(jīng)驗在你生活中的很多其它事情上也適應(yīng)。
說正經(jīng)的，如果你有機(jī)會想找一個解決問題的高手——雇傭Guy比誰都強(qiáng)。那個家伙很厲害。在這些陳年舊賬里發(fā)現(xiàn)的一點技術(shù)瑕疵：字母有可能重復(fù)而字符串可能會很長，所以必須要有統(tǒng)計。用那個最幼稚的解決方案時，當(dāng)在大字符串里找到一個字符后就把它刪掉，當(dāng)這樣仍然是 O(n*m)次。在Hashtable里我們會有一個key->value的計數(shù)。Guy的方案在這種情況下仍然好用。
