我是如何為Google面試做準(zhǔn)備的

時(shí)間：2022-05-25 04:03:02 | 來(lái)源：網(wǎng)絡(luò)營(yíng)銷

時(shí)間：2022-05-25 04:03:02 來(lái)源：網(wǎng)絡(luò)營(yíng)銷

如果你有一段時(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ì)你起教育(再教育)作用。

很多年前，我初進(jìn)硅谷人才市場(chǎng)，當(dāng)時(shí)是想找一份高級(jí)工程師的職位，我第一家面試的公司叫做gofish，據(jù)我所知，gofish這家公司如今的情況跟我當(dāng)時(shí)面試時(shí)完全的不同，我?guī)缀跄艽虮Ｆ钡恼f(shuō)，當(dāng)時(shí)我在那遇到的那些人都已不再那工作了，雖說(shuō)這家公司的實(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ì)的。

他走到白板前說(shuō)道：“如果這樣呢——假設(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)有幫助我理解他（具體可查看億企邦《求職面試中最常見(jiàn)問(wèn)題的回答技巧及注意事項(xiàng)》的相關(guān)介紹）。

現(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，在跟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ù)墓健?br>
他們?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ú)聊的家伙，但可以留下（具體可查看億企邦《程序員跟人事部HR在簡(jiǎn)歷閱讀和打分上有什么不同》的相關(guān)介紹）。”

我等了一會(huì)，我讓這種焦灼的狀態(tài)持續(xù)的盡可能的長(zhǎng)，我可以發(fā)誓的說(shuō)，如果再耽擱一分鐘，我一定會(huì)憋出腦血栓、脫口說(shuō)出關(guān)于素?cái)?shù)的未解之謎。

我打破了沉默，說(shuō)道：“你知道嗎，還有另外一個(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ì)他那條皮褲子大笑不已。

最后，在這些陳年舊賬里發(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的方案在這種情況下仍然好用。

億企邦點(diǎn)評(píng)：

話說(shuō)回來(lái)，如果這個(gè)故事里有什么教育意義的話，那就是永遠(yuǎn)不要冒失的第一個(gè)去應(yīng)聘你夢(mèng)想的公司，應(yīng)先去應(yīng)聘那些你不看好的職位，你除了能從這些面試中獲得經(jīng)驗(yàn)外，你指不定能遇到某個(gè)能為你的更重要的面試鋪路的人呢，事實(shí)上，這個(gè)經(jīng)驗(yàn)在你生活中的很多其它事情上也適應(yīng)。