英文原文：A Google Interviewing Story
很多年前我進入硅谷人才市場，當時是想找一份高級工程師的職位。如果你有一段時間沒有面試過，根據經驗，有個非常有用的提醒你應該接受，就是： 你往往會在前幾次面試中的什么地方犯一些錯誤。簡單而言就是，不要首先去你夢想的公司里面試。面試中有多如牛毛的應該注意的問題，你可能全部忘記了，所 以，先去幾個不太重要的公司里面試，它們會在這些方面對你起教育(再教育)作用。
我第一家面試的公司叫做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的方案在這種情況下仍然好用。)