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

[[347644]]

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

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

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

想象一個(gè)電話撥號(hào)盤，從某個(gè)位置開始只能以大寫字母 「L」的形狀移動(dòng): 水平移動(dòng)兩步，垂直移動(dòng)一步，或水平移動(dòng)一步，垂直移動(dòng)兩步:

假設(shè)您在鍵盤上只能使用這種方式來撥號(hào)，撥下一個(gè)鍵并進(jìn)行下一跳。起始位置計(jì)算為正在撥號(hào)的鍵。

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

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

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

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

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

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

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

話雖如此，作者希望面試者聽到這個(gè)問題后的第一個(gè)行動(dòng)應(yīng)該是走到白板前，手工解決這個(gè)問題的一些小實(shí)例。

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

舉個(gè)例子，假設(shè)起始位置從6開始，你有兩跳的機(jī)會(huì)。則序列將會(huì)是：

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

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

Level 1：到達(dá)下一跳

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

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

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

通?？梢约僭O(shè)有一個(gè)函數(shù)會(huì)傳給鄰居值，如下圖所示：

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

而且，如果問題的復(fù)雜性在其他地方的話，面試者通常不會(huì)因?yàn)橐笫褂每蘸瘮?shù)而被留下壞印象，面試官通常都會(huì)同意這種做法。

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

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

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

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

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

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

鉆石方案：高級(jí)一些的想法

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

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

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

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

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

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

接下來通常的做法就是解決時(shí)間復(fù)雜度太高的問題。

Level 4：降低復(fù)雜度

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

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

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

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

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

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

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

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

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

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

首先，不是遞歸的意味著可以運(yùn)行非常大的值而不會(huì)崩潰。

其次，使用常量?jī)?nèi)存，因?yàn)橹恍枰獌蓚€(gè)固定大小的數(shù)組，而不需要不斷增長(zhǎng)的制表解決方案的緩存。

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

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

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

1.始終從手推一個(gè)小實(shí)例開始。

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

3.清楚地使用遞歸。

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

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

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