有位外國小哥在自己的博客上通過解答一道面試題，發(fā)布了自己在谷歌擔任工程師和面試官的經(jīng)驗，分享了對于科技公司面試者的一些建議。

[[347644]]

「金九銀十」的求職季也只剩下了一個尾巴，不知道正在求職的你結(jié)果如何呢？

如果你是一名學生或者正在申請技術(shù)類的工作，希望你在讀完這篇文章之后能夠更好地應對即將到來的面試。

面試「腦筋急轉(zhuǎn)彎」，你怎么答？

想象一個電話撥號盤，從某個位置開始只能以大寫字母 「L」的形狀移動: 水平移動兩步，垂直移動一步，或水平移動一步，垂直移動兩步:

假設您在鍵盤上只能使用這種方式來撥號，撥下一個鍵并進行下一跳。起始位置計算為正在撥號的鍵。

那么，從一個特定的起始位置開始，能以 N 跳的方式撥多少個不同的號碼？

回答的套路：由淺至深的討論

面試基本上分為兩部分: 首先找到一個該問題的算法解決方案，然后面試者用代碼來實現(xiàn)它。

在面試的整個過程中，面試官通常不是一個沉默的旁觀者: 在松弛的環(huán)境中花45分鐘設計和實現(xiàn)任何東西時間都不充足，更不用說在有壓力的情況下了。

面試官通常會讓面試者在討論中發(fā)揮帶頭作用，產(chǎn)生想法，提出解決問題的實例等，但作者有時也非常樂意在正確的方向上給予對方推動。

面試者的水平越高，他傾向于給出的暗示就越少，但是作者還沒有看到過一個候選人完全不需要他的參與。

作為一個面試官，通常不會坐視別人失敗，「我想寫盡可能多的積極的反饋，我會盡量給你機會讓我寫關(guān)于你的好東西，提示是我說：好吧，我給你一點提示」，只有這樣才能讓一些面試者繼續(xù)前進，看看他們對問題的其他部分有什么看法。

話雖如此，作者希望面試者聽到這個問題后的第一個行動應該是走到白板前，手工解決這個問題的一些小實例。

「永遠不要一頭扎進代碼里！解決小的實例可以讓你發(fā)現(xiàn)模式，觀察和邊緣情況，也有助于在你的頭腦中明確解決方案」。

舉個例子，假設起始位置從6開始，你有兩跳的機會。則序列將會是：

以上總共有六個序列。如果試著用鉛筆和紙來推導這些，總比只是盯著它靜靜地思考，會帶來更好的結(jié)果。 

黃銅答案：初級面試者通常給出的方案

Level 1：到達下一跳

作者作為面試官經(jīng)常會感到驚訝的是，求職者經(jīng)常會陷入計算鍵值的困境，其實恰恰可以從一個給定的位置跳到這個鍵值，也就是我們所說的鄰居（neighbors）。

作者的建議是: 當有疑問的時候，可以寫一個空的占位符，然后問面試官是否可以稍后實現(xiàn)它。

這個問題的復雜性不在于鄰居的計算，而是如何很好地計算完整的數(shù)字，任何花費在鄰居計算上的時間都被浪費掉了。

通常可以假設有一個函數(shù)會傳給鄰居值，如下圖所示：

當然，這個空函數(shù)功能最終也是需要被實現(xiàn)的，但前提是面試剩余的時間還足夠。

而且，如果問題的復雜性在其他地方的話，面試者通常不會因為要求使用空函數(shù)而被留下壞印象，面試官通常都會同意這種做法。

如果沒有別的復雜問題，面試官還會要求面試者實際執(zhí)行它。

至于這里的鄰居函數(shù)，考慮到它從不改變，可以簡單地創(chuàng)建一個 map 并返回相應的值:

Level 2：遞歸生成數(shù)字

不管怎樣，我們來看看解決方案。也許你已經(jīng)注意到這個問題可以通過列舉所有可能的數(shù)字并計算它們來解決，可以使用遞歸來生成這些值:

這是一種非常普遍的想法。然而，生成的數(shù)字并沒有真正的使用它們。這個問題要求的是數(shù)字計數(shù)，而不是數(shù)字本身。

一旦計算了一個數(shù)字，就再也不會重訪它了。作為一般的經(jīng)驗法則，作者建議注意當解決方案計算一些不使用的東西時，在通常情況下可以把它刪除，然后得到一個更好的解決方案。

鉆石方案：高級一些的想法

Level 3：「不計數(shù)的計數(shù)」

怎樣才能在不產(chǎn)生電話號碼的情況下計算電話號碼呢？請注意，從 n 跳中給定的起始位置生成的數(shù)字計數(shù)等于從 n 跳中的每個相鄰位置生成的數(shù)字計數(shù)之和。

從數(shù)學角度來說，它是一個遞推關(guān)系式，看起來像這樣:

有很多實現(xiàn)使用了這個公式的思想，但是讓我們從我在面試中最常見的一個開始: 「樸素的遞歸方法」:

接下來這個問題會經(jīng)常從面試中聽到: 「這個解決方案的復雜度是多少」。對于那些不知道的人來說，O(N)復雜度是一種速率，一個解決方案所需的計算量隨著函數(shù)輸入大小的變化而增長。對于這個問題，輸入的大小是跳數(shù)。

對于這種實現(xiàn)，每次遞歸調(diào)用 count _ sequences ( ) 至少兩次，因為每個鍵至少有兩個鄰居。由于我們遞歸的次數(shù)等于所需的跳數(shù)，并且每次調(diào)用時計算 _ sequences ()的調(diào)用數(shù)量至少翻了一番，因此運行時的復雜度至少為指數(shù)級。

接下來通常的做法就是解決時間復雜度太高的問題。

Level 4：降低復雜度

為了找到下一個函數(shù)，讓我們把這個函數(shù)調(diào)用的函數(shù)映射出來。讓我們考慮 count _ sequences (6,4)的情況。注意: 為了簡潔起見，使用 c 作為函數(shù)名:

注意這里 c (6,2)調(diào)用執(zhí)行了三次，每次執(zhí)行相同的計算并返回相同的值。這里關(guān)鍵的一點是，這些函數(shù)調(diào)用會重復調(diào)用，每次都返回相同的值。一旦你計算了他們的結(jié)果，就不需要重新計算了。

使用制表法可以解決這個問題 ，這基本上意味著我們可以記錄之前看到的函數(shù)調(diào)用的結(jié)果，并使用這些結(jié)果來代替重復工作。

這樣，當我們在調(diào)用圖中遇到不必要地重新計算整個子樹的位置時，可以立即返回已經(jīng)計算的結(jié)果。下面是一個實現(xiàn):

經(jīng)過這樣的處理，復雜度就已經(jīng)降到了線性的結(jié)果。

這個解決方案依舊有一些不足之處，主要的缺點是它是遞歸的。大多數(shù)語言都對其調(diào)用堆棧的最大大小進行限制，這意味著總是需要考慮可以支持最大的跳數(shù)。

Level 5：動態(tài)規(guī)劃

請注意，n 跳的結(jié)果僅依賴于 n-1 跳調(diào)用的結(jié)果。同時，緩存包含每個(非零)跳數(shù)的條目。

學過歸納法的人都知道，可以使用遞推關(guān)系式歸納步驟，可以從零跳數(shù)的基本情況開始，并歸納推導出所有大于零的值。下面是它的一個實現(xiàn):

還有沒有比遞歸的深度優(yōu)先解決方案更好的版本呢？不是很多，但也有一些。

首先，不是遞歸的意味著可以運行非常大的值而不會崩潰。

其次，使用常量內(nèi)存，因為只需要兩個固定大小的數(shù)組，而不需要不斷增長的制表解決方案的緩存。

最后，仍然是線性時間復雜度: 可以在20秒內(nèi)計算200,000跳。

在求職面試中設計和實現(xiàn)一個線性時間、常數(shù)空間的解決方案通常都會得到一個很好的結(jié)果。當作者使用這個問題進行面試時，經(jīng)常給那些使用動態(tài)規(guī)劃方案的面試者一個很好的反饋。

最后，作者還列出了為了準備面試和今后的工作你應該養(yǎng)成的習慣:

1.始終從手推一個小實例開始。

2.注意你的解決方案做的哪些計算是不必要的。

3.清楚地使用遞歸。

4.知道你解決方案的O（N）。

5.總是尋找機會來回憶，如：編寫一個空函數(shù)。

現(xiàn)在正值「金九銀十」和校招季，希望大家都能找到自己心儀的工作！