想要去谷歌、Facebook、蘋果這樣的公司工作嗎?很多時候它們的面試會讓人望而卻步。不用害怕，我們已經(jīng)掌握了它們的常規(guī)面試題。近日，麻省理工學(xué)院(MIT)計算機科學(xué)和人工智能實驗室(CSAIL)的新版「程序員面試課程」資料已被公開。無論你是初級程序員還是經(jīng)驗豐富的專家，這門課程都適合你。

課程鏈接：http://courses.csail.mit.edu/iap/interview/index.php

本課程重點介紹科技公司在面試時經(jīng)常出現(xiàn)的計算機科學(xué)問題，其中包括時間復(fù)雜度、哈希表、二進(jìn)制樹搜索，以及 MIT「算法設(shè)計與分析」(MIT 6.046)課程中會出現(xiàn)的內(nèi)容。但是，大部分時間都會專注于你不會在課堂上學(xué)到的內(nèi)容，例如刁鉆的按位邏輯和解決問題的技巧。

面試錦囊

被問到一個問題時，要和面試官展開對話，讓對方知道你在思考。例如，你可能會提供一個較慢或能解決部分問題的方案(讓他們知道這個方案并不***)，提到一些關(guān)于這個問題的觀察結(jié)果，或者說一下任何有可能對解決問題有幫助的想法。如果你卡住了，面試官通常會給你點提示。

面試期間，你通常會被要求寫一個程序。出于某種原因，面試官通常讓人在黑板或紙上寫，而不是給你一臺電腦。所以，有必要在面試之前練一下在板子上寫代碼，以備不時之需。

以下是編程面試中的一些注意事項：

這些事要做：

• 如果對問題有哪里不理解或有歧義，一定要問清楚;
• 讓面試官知道你在想什么;
• 針對問題提出多個解決方案;
• 與面試官交流想法(如關(guān)于數(shù)據(jù)結(jié)構(gòu)和算法的想法)
• 如果你卡住了，不要害怕讓他們知道，可以禮貌地尋求提示。

這些事不要做：

• 不要放棄!放棄對你展示自己的問題解決技巧沒有任何幫助;
• 思考期間不要只是安靜地坐在那里。面試官要在有限的時間內(nèi)盡可能多地了解你，不和他們交流無法向他們傳遞任何信息;
• 如果你已經(jīng)知道問題的答案，不要脫口而出!不然他們會覺得你提前看過這個問題并記下了答案。至少要在給出答案之前假裝思考一陣兒。

好了，如果你對自己的備考情況很有信心，以下是其中的一些經(jīng)典問題：

問題 1：硬幣難題

假設(shè)你有 8 枚大小相同的硬幣，但其中 1 枚硬幣要比其他 7 枚稍重一點(但你不知道具體是哪一枚)。同時，你還有一個老式天平可以稱重，從而得出哪枚硬幣稍重(或是否重量相同)。那么，最少要稱多少次才能找出那枚稍輕的硬幣?

優(yōu)秀答案：從 8 枚硬幣中取出 6 枚，天平左右盤各放 3 枚。結(jié)果會出現(xiàn)三種情況：天平左盤 3 枚硬幣重于右盤，則較重的 1 枚在左盤;天平右盤的 3 枚硬幣重于左盤，則較重的 1 枚在右盤;天平左右盤重量相等，則稱剩下的 2 枚硬幣，得出稍重的這枚硬幣。

不太好的答案：分別取 4 枚硬幣放置于天平左右盤，找出較輕的一組(4 枚)，將該組硬幣繼續(xù)分為兩組放入天平左右盤，找出較輕的一組(2 枚)，再次重復(fù)此步驟找到最輕的一枚。

問題 2：在數(shù)組中進(jìn)行查找

給定一個已排序的整數(shù)數(shù)組，如何找出特定整數(shù) x 的位置?

優(yōu)秀答案：使用二分搜索法。將數(shù)組中間的數(shù)字與 x 進(jìn)行比較。如果相同，則找出了 x。如果數(shù)組中的數(shù)字較大，則需要查看數(shù)組后半部分。如果數(shù)字較小，則需要查看數(shù)組前半部分。通過比較數(shù)組中間元素和 x，我們可以重復(fù)搜索該數(shù)組的前后部分，從而再次將搜索范圍縮小 2 倍。我們重復(fù)這一過程直至找出 x。這種算法花費的時間為 O(log n)。

不太好的答案：按順序查看數(shù)組的每個數(shù)字，與 x 進(jìn)行比較。這種算法花費的時間為 O(n)。

問題 3：A to I

編寫一個函數(shù)將字符串轉(zhuǎn)換為整數(shù)(這個函數(shù)被稱為 A to I 或者 atoi())，因為我們要將一個 ASCII 字符串轉(zhuǎn)換為整數(shù)。

優(yōu)秀答案：從頭到尾查看整個字符串。如果***字符為負(fù)號，記下來。從 0 開始進(jìn)行累計求和。每得到一個新數(shù)字，總數(shù)乘以 10 并加上這個新數(shù)字。當(dāng)計算結(jié)束時，返回當(dāng)前總數(shù)，或者如果出現(xiàn)負(fù)號，返回該數(shù)字的倒數(shù)。

湊合的答案：另一種方法也是從頭到尾查看整個字符串，再次進(jìn)行累計求和。記住表示當(dāng)前你所在數(shù)字的數(shù)字 x，x 最開始為 1。針對每個字符，將當(dāng)前數(shù)字乘以 x 并添加到累計總數(shù)中，同時將 x 乘以 10。當(dāng)你到達(dá)字符串起點時，返回當(dāng)前總數(shù)，或者如果出現(xiàn)負(fù)號，返回該數(shù)字的倒數(shù)。

注意：面試官可能會詢問你自身方法的局限性。你應(yīng)該回答：只有字符串在每個數(shù)字前都包含可選負(fù)號時，該方法才能生效。同時，你還應(yīng)提到：如果數(shù)字太大，則結(jié)果會因為溢值原因而不正確。

問題 4：顛倒字符串中的單詞順序

編寫一個函數(shù)將字符串中的單詞順序進(jìn)行顛倒。

答案：交換***個與倒數(shù)***個、第二個與倒數(shù)第二個字符的順序，以此類推，顛倒整個字符串。之后，查看整個字符串，找出空格，這樣就可以發(fā)現(xiàn)每個單詞的位置。再次交換***個與倒數(shù)***個、第二個與倒數(shù)第二個單詞的順序，以此類推，顛倒你所遇到的每個單詞的順序。

問題 5：最近鄰

假設(shè)你有一個包含 n 個人信息的數(shù)組。每個人分別用一個字符串(他們的名字)和一個數(shù)字(他們在數(shù)軸上的位置)表示。每個人有三個朋友，即數(shù)字和他本人最接近的三個人。請寫出一個可以找出每個人的三個朋友的算法。

優(yōu)秀答案：按每個人數(shù)字的升序?qū)?shù)組進(jìn)行排列。查看每個人前后緊鄰的三個人，他們的朋友將出現(xiàn)在這六個人當(dāng)中。這一算法花費的時間為 O(n log n)，因為將人進(jìn)行分類也會花費那么多時間。

問題 6：洗牌問題

給定一組不同的整數(shù)數(shù)組，給出一個算法對這些整數(shù)進(jìn)行隨機排序，使每個重排序方法的可能性相等。換句話說，給定一副牌，你要如何洗牌才能確保牌的每種排列方法有相同的可能?

優(yōu)秀答案：按順序排列這些元素，用數(shù)組中不先于某個元素出現(xiàn)的隨機元素與該元素進(jìn)行交換。需要的時間為 O(n)。

注意，這個問題有多個可能的答案，也有幾種看似不錯但實際上并不正確的答案。例如，對上面的算法做一個小小的修改，即，將每個元素與數(shù)組中的任意一個元素交換并不能確保每種重排順序等概率出現(xiàn)。這里給出的答案(在作者看來)是***答案。如果想了解其他答案，可以在維基百科上搜一下「Shuffling」。

問題 7：單鏈表中的循環(huán)

如何確定單鏈表是否有循環(huán)?

優(yōu)秀答案：跟蹤鏈表中的兩個指針，并在鏈表的開始處啟動它們。在算法的每輪迭代中，將***個指針往前移一個節(jié)點，把第二個指針往前移兩個節(jié)點。如果兩個指針始終相同(不是在算法起點處)，那么就有一個循環(huán)。如果指針在兩個指針相同之前就達(dá)到鏈表的末端，鏈表中就沒有循環(huán)。其實，指針不需要一次移動一到兩個節(jié)點;指針也不需要以不同的速率移動。這個過程需要的時間為 O(n)。這是一個巧妙的回答，面試官會莫名喜歡。

湊合的回答 1：對于你在逐一瀏覽鏈表時遇到的每個節(jié)點，將指向該節(jié)點的指針放入 O(1) 中——查找時間數(shù)據(jù)結(jié)構(gòu)，如散列集。接下來，當(dāng)你遇到一個新的節(jié)點時，要看看指向那個節(jié)點的指針是否已經(jīng)存在于你的散列集中。這一過程花費的時間為 O(n)，但占用的空間也是 O(n)。

湊合的回答 2：瀏覽鏈表中的元素?！窶ark」你到達(dá)的每個節(jié)點。如果在抵達(dá)末端之前你到達(dá)了一個 mark 過的節(jié)點，列表中就有循環(huán)，否則就沒有循環(huán)。這一過程花費的時間也是 O(n)。

注意，這個問題在技術(shù)上是不恰當(dāng)?shù)?。一個普通的鏈表不會有循環(huán)。他們的意思是讓你決定能否從一個圖中的節(jié)點到達(dá)循環(huán)，該圖包含最多有一條輸出邊的節(jié)點。

問題 8：計算 2^x

如何快速計算 2^x?

優(yōu)秀答案：1 << x (1 left‐shifted by x)

問題 9：二叉搜索樹

二叉搜索樹是一種排序保存項目的數(shù)據(jù)結(jié)構(gòu)，它由二叉樹組成。每個節(jié)點都有一個指向兩個子節(jié)點的指針(可能為 null)，一個指向其父節(jié)點的可選指針(也可以為 null)，以及一個存儲在樹中的元素(可能是一個字符串或一個整數(shù))。要使二叉搜索樹有效，每個節(jié)點的元素必須大于其左子樹中的每個元素，并且小于其右子樹中的每個元素。例如，二叉樹可能如下所示：

要檢查元素是否出現(xiàn)在二叉搜索樹中，只需要遵循父對子之間的相應(yīng)連接。例如，如果我們想在上面的樹中搜索 15，我們從最上方的 17 開始。由于 15<17，我們移動到左邊的節(jié)點 6。由于 15> 6，我們移動到右邊的節(jié)點 12;由于 15>12，我們再次移動到正確的節(jié)點 15，最終找到了需要的數(shù)字。

要將元素加入二叉搜索樹，我們就要像搜索元素一樣，遵循從父節(jié)點到子節(jié)點的正確連接。當(dāng)所需的子項為 null 時，我們將該元素添加為新的子節(jié)點。例如，如果我們要在上面的樹中添加 14，我們就需要不斷往下尋找添加的位置。當(dāng)我們到達(dá) 15，就會看到該節(jié)點沒有左子節(jié)點，因此我們將 14 添加為左子節(jié)點。

要從二叉搜索樹中刪除一個元素，我們首先要找出包含該元素的節(jié)點。如果該節(jié)點沒有子節(jié)點，直接刪除即可。如果該節(jié)點有一個子節(jié)點，則用這個子節(jié)點替代它。如果該節(jié)點有兩個子節(jié)點，我們通過一種算法確定樹中下一個更小或下一個更大的元素。為簡單起見，這里就不贅述所使用的算法了。我們將節(jié)點中存儲的元素設(shè)定為該值。之后，我們從樹中拼接包含該值的節(jié)點。這個過程相對較容易，因為節(jié)點最多有一個子節(jié)點。例如，為了從樹中刪除 6，我們首先將節(jié)點值更改為 3。之后，我們刪除原本值為 3 的節(jié)點，并將原本值為 6 的節(jié)點的左子節(jié)點值設(shè)定為 1。

在二叉搜索樹上做小小的修改，就可以使用它將鍵與值關(guān)聯(lián)起來，就像在散列表中一樣。我們不需要在每個節(jié)點上存儲單個值，而是存儲一個鍵值對。該樹將根據(jù)節(jié)點的鍵進(jìn)行排序。

面試官有時會問到二叉搜索樹的問題。此外，二叉搜索樹往往在回答面試問題時也很有用。需要記住的重要一點是，插入、刪除和查找需要的時間為 O(log n)，其中 n 是樹中的元素數(shù)量，因為一個平衡良好的二叉搜索樹的高度是 O(log n)。盡管在最糟糕的情況下，一個二叉搜索樹的高度可能為 O(n)，「自平衡」二叉搜索樹可以周期性地重組一個 BST 來確保其高度為 O(log n)。許多自平衡 BST 保證這些操作花費的時間為 O(log n)。

問題 10：排除 bug

描述一種從程序中找出 bug 的方法。

答案：這個問題有多個可能的答案，也是面試官經(jīng)常會問的開放性問題。優(yōu)秀答案可能包括：根據(jù)程序的行為判斷可能出現(xiàn) bug 的部分;使用斷點和 stepper 逐步執(zhí)行程序。任何試圖找到 bug 源頭和縮小 bug 搜索范圍的方法都是好答案。

以上是谷歌程序員面試時可能出現(xiàn)的編程題及解題技巧。當(dāng)然，只是其中很小的一部分。

• 想要了解更多問題和答案請點擊：http://courses.csail.mit.edu/iap/interview/materials.phpMIT《算法設(shè)計與分析》課程資料：
• https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-design-and-analysis-of-algorithms-spring-2015/

【本文是51CTO專欄機構(gòu)“機器之心”的原創(chuàng)譯文，微信公眾號“機器之心( id: almosthuman2014)”】 

戳這里，看該作者更多好文