作為一名Google的工程師和面試官，今天是我第二次發(fā)文分享科技公司面試建議了。這里先聲明：本文僅代表我個(gè)人的觀察、意見和建議。請(qǐng)勿當(dāng)作來(lái)自Google或Alphabet的官方建議或聲明。

下面這個(gè)問(wèn)題，是我面試生涯中第一個(gè)問(wèn)題；也是第一個(gè)被泄漏出來(lái)，以及第一個(gè)被禁掉的問(wèn)題。我喜歡這個(gè)問(wèn)題，因?yàn)樗幸韵聝?yōu)點(diǎn)：

問(wèn)題很容易表述清楚，也容易理解。

這個(gè)問(wèn)題有多個(gè)解。每個(gè)解都需要不同程度的算法和數(shù)據(jù)結(jié)構(gòu)知識(shí)。而且，還需要一點(diǎn)點(diǎn)遠(yuǎn)見。

每個(gè)解都可以簡(jiǎn)單幾行代碼實(shí)現(xiàn)，非常適合有時(shí)間限制的面試。

如果你是學(xué)生，或者求職者，我希望你通過(guò)本文能夠了解到，面試問(wèn)題一般會(huì)是怎么樣的。如果你也是面試官，我很樂(lè)意分享自己在面試中的風(fēng)格和想法，如何更好地傳達(dá)信息、征求意見。

注意，我將使用Python寫代碼；我喜歡Python因?yàn)樗讓W(xué)，簡(jiǎn)潔，而且有海量的標(biāo)準(zhǔn)庫(kù)。我遇到的很多面試者也很喜歡，盡管我們推行“不限定語(yǔ)言”的政策，我面試90%的人都用Python。而且，我用的Python 3因?yàn)?，拜托，這都2018年了。

問(wèn)題把你的手機(jī)撥號(hào)頁(yè)想象成一個(gè)棋盤。棋子走只能走“L”形狀，橫著兩步，豎著一步；或者豎著兩步，橫著一步。

現(xiàn)在，假設(shè)你撥號(hào)只能像棋子一樣走“L”形狀。每走完一個(gè)“L”形撥一次號(hào)，起始位置也算撥號(hào)一次。問(wèn)題：從某點(diǎn)開始，在N步內(nèi)，你可以撥到多少不同的數(shù)字？討論

每次面試，我基本都會(huì)分成兩個(gè)部分：首先我們找出算法方案，然后讓面試者在代碼中實(shí)現(xiàn)。我說(shuō)“我們找出算法方案”，因?yàn)檫@個(gè)過(guò)程我不是沉默的獨(dú)裁者。在這樣高壓下，設(shè)計(jì)并實(shí)現(xiàn)一種算法，45分鐘時(shí)間并不算充足。

我通常會(huì)讓面試者主導(dǎo)討論，讓他們?nèi)ギa(chǎn)生想法，我嘛，就在旁邊，時(shí)不時(shí)地泄漏一點(diǎn)點(diǎn)“天機(jī)”。面試者們能力越強(qiáng)，我需要泄漏的“天機(jī)”就越少；但是目前為止，我還沒(méi)遇到一點(diǎn)都不需要我提示的面試者。有一點(diǎn)我想強(qiáng)調(diào)一下，重要的很：作為面試官，我的職責(zé)可不是坐那看著大家失敗搞砸。我想要給大家正面的反饋，給大家機(jī)會(huì)去展現(xiàn)大家最擅長(zhǎng)的點(diǎn)。給他們提示，就像是在說(shuō)：吶，這一步路我給你鋪上，但這只是為了讓你展示給我，你在后面的路上能走的更遠(yuǎn)。

當(dāng)聽完面試官的問(wèn)題，你應(yīng)該做什么？切記不要立刻就去寫代碼，而是在黑板上試著一步一步去分解問(wèn)題。分解問(wèn)題能夠幫助你尋找到規(guī)律，特例等等，逐漸在大腦中形成解決方案。比如，你現(xiàn)在從數(shù)字6開始走，能走2步，會(huì)有如下組合： 6–1–8 6–1–6 6–7–2 6–7–6 6–0–4 6–0–6一共有6種組合。你可以試著用鉛筆在紙上畫，相信我，有時(shí)候動(dòng)手去解決問(wèn)題會(huì)發(fā)生意想不到的事，比你盯著在腦袋里想更神奇。怎么樣？你腦海里有方案了嗎？第0階：到達(dá)下一步

使用這個(gè)問(wèn)題面試，最讓我驚訝的是，太多人都卡在了計(jì)算從某個(gè)特定點(diǎn)跳出時(shí)，一共有多少種可能，即鄰Neighbors。我的建議是：當(dāng)你不確定時(shí)，先寫個(gè)占位符，然后請(qǐng)求面試官能否晚點(diǎn)實(shí)現(xiàn)這一部分。這個(gè)問(wèn)題的復(fù)雜性并不在Neighbors的計(jì)算；我在意的是你如何計(jì)算出總數(shù)。所有花費(fèi)在計(jì)算Neighbors上的時(shí)間其實(shí)都是浪費(fèi)。我會(huì)接受“讓我們假設(shè)有一個(gè)函數(shù)能給出我Neighbors”。當(dāng)然，我也可能會(huì)讓你后面有時(shí)間再去實(shí)現(xiàn)這一步，你只需要這樣寫，然后繼續(xù)。

而且，如果一個(gè)問(wèn)題的復(fù)雜性不在這里，你也可以問(wèn)我能不能先略過(guò)，一般我都是允許的。我倒是不介意面試者不知道問(wèn)題的復(fù)雜性在哪里，尤其剛開始他們還沒(méi)有全面了解問(wèn)題的時(shí)候。至于Neighbors函數(shù)，因?yàn)閿?shù)字永遠(yuǎn)不變，你可以直接寫一個(gè)Map然后返回符合的值。

第1階：遞歸

聰明的你可能注意到了，這個(gè)問(wèn)題可以通過(guò)枚舉出所有符合條件的數(shù)字，然后計(jì)算。這里可以使用遞歸產(chǎn)生這些值：

這個(gè)方法可以，而且是在面試中最普遍的方法。但是請(qǐng)注意，我們產(chǎn)生了這么多數(shù)字卻并沒(méi)有使用他們，我們計(jì)算完他們的個(gè)數(shù)后，就再也不去碰了。所以我建議大家遇到這種情況，盡量去想一下看有沒(méi)有更好的方案。第2階：數(shù)不數(shù)數(shù)

怎么在不產(chǎn)生這些數(shù)字的情況下計(jì)算出個(gè)數(shù)？可以做到，但需要一點(diǎn)點(diǎn)機(jī)智。注意從特定點(diǎn)跳出N次能夠撥到的數(shù)字個(gè)數(shù)，等于從它所有臨近的點(diǎn)跳出N-1次能夠撥到的數(shù)字個(gè)數(shù)的總和。我們可以表達(dá)為這樣的遞歸關(guān)系：

如果你這樣想，就會(huì)很直觀了，跳一次時(shí)：6有3個(gè)neighbors（1，7和0），當(dāng)跳0次時(shí)每個(gè)數(shù)字本身算一次，因此每次你只能撥到3個(gè)數(shù)字。

怎么會(huì)產(chǎn)生這樣機(jī)智的想法？其實(shí)，如果你學(xué)了遞歸，并且在黑板上好好研究，這一點(diǎn)就會(huì)變得顯而易見。這樣你就能繼續(xù)去解決這個(gè)問(wèn)題，實(shí)際上就這一點(diǎn)就有多種實(shí)現(xiàn)方法，下面這個(gè)便是面試中最常見的：

就是這樣，結(jié)合這個(gè)函數(shù)計(jì)算出neighbors 就可以了。這時(shí)候，你就可以捏捏肩膀休息下了，因?yàn)榈竭@里，你已經(jīng)刷掉很多人了。接下來(lái)這個(gè)問(wèn)題我經(jīng)常問(wèn)：這個(gè)方案的算法理論速度如何？在這個(gè)實(shí)現(xiàn)中，每次調(diào)用count_sequences()都會(huì)遞歸地調(diào)用count_sequences()至少2次，因?yàn)槊總€(gè)數(shù)字至少有2個(gè)neighbors。這樣會(huì)導(dǎo)致runtime成指數(shù)增長(zhǎng)。對(duì)于跳1次到20次這樣的次數(shù)還可以，但是到更大的數(shù)字，我們就要碰壁。500次可能就需要整個(gè)宇宙的熱量來(lái)完成運(yùn)算。第3階：記憶

那么，我們能做的更好么？使用上面的方法，并不能。我喜歡這個(gè)問(wèn)題，也是因?yàn)樗芤粚右粚訋С龃蠹业闹腔?，找到更高效的方法。為了找到更好的方法，讓我們看下這個(gè)函數(shù)是怎么調(diào)用的，以count_sequences(6, 4)為例。注意這里用C作為函數(shù)名簡(jiǎn)化。

你可能注意到了，C(6, 2)運(yùn)行了3次，每次都是同樣的運(yùn)算并返回同樣的值。這里最關(guān)鍵的點(diǎn)在于這些重復(fù)的運(yùn)算，每次你使用過(guò)他們的值之后，就沒(méi)有必要再次計(jì)算。怎么解決這個(gè)問(wèn)題？記憶。我們那些相同的函數(shù)調(diào)用和結(jié)果，而不是讓他們重復(fù)。這樣，在后面我們就可以直接給出之前的結(jié)果。實(shí)現(xiàn)方法如下：

第4階：動(dòng)態(tài)設(shè)計(jì)

如果你再看看前面的遞歸關(guān)系，就會(huì)發(fā)現(xiàn)遞歸記憶的方案也有一點(diǎn)局限性：

注意跳N次的結(jié)果僅僅取決于跳N-1次后調(diào)用的結(jié)果。同時(shí)，緩存中包含著每個(gè)次數(shù)的所有結(jié)果。我之所以說(shuō)這是個(gè)小局限，因?yàn)榇_實(shí)不會(huì)造成真的問(wèn)題，當(dāng)跳的次數(shù)增長(zhǎng)時(shí)，緩存也只是線性增長(zhǎng)。但是，畢竟，這還是不夠高效。怎么辦？讓我們?cè)賮?lái)看一看方案和代碼。注意，代碼中是從最大的次數(shù)開始，然后直接遞歸到最小的次數(shù)：

如果你把整個(gè)的函數(shù)調(diào)用圖想象成某種虛擬的樹，你就會(huì)發(fā)現(xiàn)我們?cè)趫?zhí)行深度優(yōu)先策略。這并沒(méi)有什么問(wèn)題，但是它沒(méi)有利用到淺依賴這個(gè)屬性。如何實(shí)現(xiàn)廣度優(yōu)先策略？這里就是一種實(shí)現(xiàn)方法：

這個(gè)版本比前面遞歸版好在哪里？其實(shí)并沒(méi)有好很多，但是這個(gè)不是遞歸的，因此即使處理超大數(shù)據(jù)也很難崩潰。其次，它使用的是常量?jī)?nèi)存；最后，它仍舊是線性增長(zhǎng)，即便處理200000次跳也只用不到20秒。

評(píng)估

到這里，基本就算完了。設(shè)計(jì)并實(shí)現(xiàn)一個(gè)線性時(shí)的、產(chǎn)量?jī)?nèi)存的方案，在面試中是非常好的結(jié)果。在我的面試中，如果有面試者寫出動(dòng)態(tài)編程設(shè)計(jì)，我通常會(huì)給他一個(gè)極高的評(píng)價(jià)：excellent！

當(dāng)評(píng)估算法和數(shù)據(jù)結(jié)構(gòu)的時(shí)候，我經(jīng)常會(huì)說(shuō)：面試者對(duì)問(wèn)題認(rèn)識(shí)清晰，并且考慮到各方面的可能，當(dāng)指出不足時(shí)他也能迅速改進(jìn)并提高；最終，實(shí)現(xiàn)了一個(gè)不錯(cuò)的解決方案。當(dāng)評(píng)估代碼的時(shí)候，我最理想的說(shuō)法是：面試者迅速并精確地把想法轉(zhuǎn)化為了代碼；代碼結(jié)構(gòu)嚴(yán)謹(jǐn)，容易閱讀。所有特殊情況都有概括，并且認(rèn)真檢查測(cè)試了代碼，確保了沒(méi)有Bug?？偨Y(jié)

我知道，這個(gè)面試問(wèn)題看上去似乎有點(diǎn)嚇人，尤其整個(gè)解釋下來(lái)非常繁瑣。但本文的目的和面試中完全不一樣。最后，一點(diǎn)面試相關(guān)的技巧，以及一些好的習(xí)慣，分享給大家：

一定要手動(dòng)來(lái)，從最小的問(wèn)題開始解決。

當(dāng)你的程序在做無(wú)用的運(yùn)算時(shí)，一定要注意去優(yōu)化。減少不必要的運(yùn)算能夠讓你的解決方案更加簡(jiǎn)潔，說(shuō)不定能因此發(fā)現(xiàn)更高效的方案。

了解你的遞歸函數(shù)。在實(shí)際生產(chǎn)中，遞歸常常很容易出問(wèn)題，但它仍舊是非常強(qiáng)大的算法設(shè)計(jì)和策略。遞歸方案也總是有優(yōu)化和提高的余地。

要常常去尋找記憶的機(jī)會(huì)。如果你的函數(shù)是目的性的，并且會(huì)多次調(diào)用相同的值，那么就試著去存儲(chǔ)起來(lái)。