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

下面這個問題，是我面試生涯中第一個問題；也是第一個被泄漏出來，以及第一個被禁掉的問題。我喜歡這個問題，因為它有以下優(yōu)點：

問題很容易表述清楚，也容易理解。

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

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

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

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

問題把你的手機撥號頁想象成一個棋盤。棋子走只能走“L”形狀，橫著兩步，豎著一步；或者豎著兩步，橫著一步。

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

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

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

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

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

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

第1階：遞歸

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

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

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

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

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

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

那么，我們能做的更好么？使用上面的方法，并不能。我喜歡這個問題，也是因為他能一層一層帶出大家的智慧，找到更高效的方法。為了找到更好的方法，讓我們看下這個函數(shù)是怎么調(diào)用的，以count_sequences(6, 4)為例。注意這里用C作為函數(shù)名簡化。

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

第4階：動態(tài)設(shè)計

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

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

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

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

評估

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

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

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

一定要手動來，從最小的問題開始解決。

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

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

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