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

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

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

面試錦囊

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

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

以下是編程面試中的一些注意事項(xiàng)：

這些事要做：

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

這些事不要做：

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

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

問題 1：硬幣難題

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

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

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

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

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

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

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

問題 3：A to I

編寫一個(gè)函數(shù)將字符串轉(zhuǎn)換為整數(shù)(這個(gè)函數(shù)被稱為 A to I 或者 atoi())，因?yàn)槲覀円獙⒁粋€(gè) ASCII 字符串轉(zhuǎn)換為整數(shù)。

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

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

注意：面試官可能會(huì)詢問你自身方法的局限性。你應(yīng)該回答：只有字符串在每個(gè)數(shù)字前都包含可選負(fù)號(hào)時(shí)，該方法才能生效。同時(shí)，你還應(yīng)提到：如果數(shù)字太大，則結(jié)果會(huì)因?yàn)橐缰翟蚨徽_。

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

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

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

問題 5：最近鄰

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

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

問題 6：洗牌問題

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

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

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

問題 7：?jiǎn)捂湵碇械难h(huán)

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

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

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

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

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

問題 8：計(jì)算 2^x

如何快速計(jì)算 2^x?

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

問題 9：二叉搜索樹

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

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

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

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

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

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

問題 10：排除 bug

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

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

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

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

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

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