從此我不再糾結于算法了

相當長一段時間之前我一直認為程式設計的基礎是有好的算法，可是到了現在我都沒有入門基礎的資料結構的知識和算法的必要性之類的知識，我是做web的，偶爾涉及一些仿真程式設計，但是我幾乎用不到什麼像樣的算法，我自己也不曾設計什麼算法，是以我看起來是幾乎沒有機會去參加這樣的面試了。

在這裡向那些算法高手們緻敬。

對了忘記說了，曾經也研究過一些 ACM的東西，到現在我都還感覺很反胃，原因就是我是個做web的，而不是某些計算機科學家一樣的人物。

===================================================================================================================================

一次谷歌面試趣事

投遞人 丕子 釋出于 2011-04-11 07:22 評論(50) 有4966人閱讀 原文連結 [收藏] « »

　　本文是從 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的方案在這種情況下仍然好用。)