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