一道泄露並遭禁用的谷歌面試題，背後玄機全解析

作者 | Alex Golec

譯者 | 薛命燈

寫在前面

免責聲明：作為谷歌的工程師和面試官，面試候選人是我的職責之一。這篇文章僅代表我個人的經驗和觀點。請不要錯誤地將它與谷歌、Alphabet 或其他人或組織的任何形式的官方聲明聯繫在一起。

這是我在面試生涯中使用的第一個面試題，也是第一個被泄露和禁用的面試題。我很喜歡這個面試題，因為它有很多有趣的地方：

它很容易表述和理解。

它有很多解決方案，每個解決方案都要求不同程度的演算法和數據結構知識。

每個解決方案都可以通過相對較少的代碼行來實現，非常適合用在時間緊湊的面試場景中。

如果你是學生或正在申請技術工作，我希望你能夠懷著更好地了解面試題的期望來閱讀本文。如果你是面試官，我想分享我的思考過程和面試方法，並徵求反饋建議。

我將用 Python 編寫代碼。我喜歡 Python，因為它易學、緊湊，擁有龐大的標準庫。候選人也喜歡它：我們其實沒有在語言方面做出限制，但在我面試的候選人當中有 90％使用 Python。我也使用 Python 3 吧，畢竟是 2018 年了。

面試題

試想一下，你將騎士放在電話撥號盤上。騎士按照大寫「L」的形狀移動：水平兩步，然後是垂直一步，或者水平一步，然後垂直兩步：

假設你只按照騎士的步法來按鍵盤上的按鍵。每當騎士落在一個按鍵上，我們就按那個按鍵，然後繼續下一跳。起始位置被標記為已按過。

從某個特定的位置開始，在 N 跳內可以撥打多少個不同的號碼？

討 論

我的面試基本上分為兩部分：首先，我們會找到一個演算法解決方案，然後由候選人使用代碼實現。我之所以說是「我們」找到了一個解決方案，那是因為我不是一個閉著嘴巴的旁觀者：在最好的情況下，用 45 分鐘設計和實現一個演算法並不算長，這還沒有把面試的壓力考慮在內。我讓候選人來主導我們的討論，產生想法，解決問題，我也很樂意為他們提供一些提示。候選人越好，我提供的提示就越少，但我還沒有見過哪個候選人完全不需要我的提示。

有一點我需要強調，因為這很重要：作為一名面試官，我不會幹坐著看著候選人失敗。我想儘可能多地為候選人提供積極反饋，就好像在說：「我會給你一點提示，這樣你才能繼續向我展示你對問題其他部分的理解」。

在聽完面試題後，你的第一個反應是走到白板前面開始解決小規模問題。先不要急著寫代碼！通過解決小規模問題，你可以找到模式和邊界情況，而且有助你在腦子裡形成解決方案。例如，假設你從 6 開始，並且需要跳兩次。你的數字序列將是……

6–1–8

6–1–6

6–7–2

6–7–6

6–0–4

6–0–6

總共六個序列。你可以嘗試使用鉛筆和紙張寫出這些序列。可能在文章里不能很好地表達出來，但相信我，手動解決問題可以獲得更多的見解，而不只是盯著它看或靜靜地思考。

不管怎樣，你可能已經在腦海中形成了一個解決方案。但在那之前......

第 0 級：下一跳

當我開始使用這個面試題時，讓我感到吃驚的是候選人經常卡在如何計算從給定位置可以跳到的按鍵（也就是鄰居）這個問題上。我的建議是：如果有疑問，可以先放一個空的佔位符，並問面試官是否可以後面再回過頭來解決。這個問題的複雜性不在於計算鄰居，我在意的是候選人是如何計算出所有的號碼的。計算鄰居其實是在浪費時間。

我可以接受「讓我們假設有一個可以返回所有鄰居的函數」這樣的做法。當然，我可能會要求你稍後回來實現它，但前提是我們要有時間。你可以簡單地像這樣寫一個空函數，然後繼續：

如果你要求使用函數樁也沒問題，這樣並不會讓你失分太多：如果問題的複雜性在於其他地方，我會允許這樣做。否則的話，我會要求你實現它。我不介意候選人意識不到問題的複雜性在哪裡，因為在剛開始時，他們可能還沒有充分探究過問題。

至於返回所有鄰居的函數，我們假設它永遠不會發生改變，你可以簡單地創建一個 map 並返回適當的值：

第 1 級：遞歸生成號碼

現在回到解決方案上來。也許你已經注意到，這個問題可以通過枚舉所有可能的號碼並計算它們的個數來解決。你可以使用遞歸來生成這些值：

這麼做是可以的，候選人在面試中經常會這麼做。但請注意，我們生成了號碼，但並沒有使用它們。這個問題問的是號碼的個數，而不是號碼本身。在計算了號碼的個數後，我們就再也不會用到這些號碼。根據經驗，我建議你注意一下你的解決方案是否會計算用不到的東西。通常你可以使用更好的解決方案。

第 2 級：不通過計算個數得到號碼個數

我們如何在不生成電話號碼的情況下計算電話號碼的個數？我們可以做到，但需要額外的演算法。請注意，計算從給定起始位置在 N 跳之內生成號碼的個數等於它的每個鄰居在 N-1 跳內生成跳數的總和。通過數學的方式來表示這種遞歸關係看起來像這樣：

如果只考慮一跳，那麼就很直觀：6 有 3 個鄰居（1、7 和 0），在零跳時，每個鄰居只能達到一個數字，因此你只能撥打三個號碼。

你可能會問，這是怎麼想到的？如果你學過遞歸，那麼在白板上畫一畫你就會知道了。很多了解遞歸的候選人馬上就知道這個問題可以被分解為較小的子問題。如果我是在面試你，而你想不到這點，我通常會給出提示，直到候選人實在想不出來才徹底放棄。

在想到這個辦法之後，就可以繼續解決問題。有很多代碼實現都是基於這個想法，但我想從我在面試中最常見的那個開始——最初級的遞歸方法：

將這段代碼與計算鄰居的函數相結合，你就得到了可行的解決方案！這個時候，你應該給自己點個贊。如果你繼續深入進去，你會發現，我們仍然有很多需要解決的問題，但現在可以說是達到了一個里程碑。找到這個解決方案已經可以讓你脫穎而出了。

接下來的問題是：這個解決方案的 Big-O 複雜性是什麼？如果有人不知道 Big-O 是什麼，它是（非正式地說）演算法所需計算量隨輸入大小變化的速率的一種簡單的表示方式。對於這個面試題，輸入的大小就是跳數。

對於上面的實現，每次調用 count_sequences() 都會遞歸調用 count_sequences() 至少兩次，因為每個鍵至少有兩個鄰居。由於我們遞歸的次數等於所需的跳數，並且每次調用 count_sequences() 的次數至少翻倍，因此運行時複雜度至少是指數級的。

這樣的性能很糟糕。每增加一個跳數，運行複雜度至少會加倍。對於較少的跳數，比如從 1 到 20，尚可接受，但對於比較大的跳數就不行了。例如，如果跳數是 500，不知道要等到猴年馬月才能算完。

第 3 級：memoization

我們可以做得更好嗎？只使用上面的數學關係估計不行。不過，我之所以喜歡這個面試題，是因為它可以使用更多更有效的解決方案來解決。為了找到下一個解決方案，我們先把函數的調用結構畫出來。我們先考慮 count_sequences(6,4) 的情況。注意，我使用 C 表示函數名：

你可能會注意到一些奇怪的事情：C(6,2) 被調用了三次，每次執行的是相同的計算，並返回相同的值。所以這些函數調用是重複的，而且每次返回相同的值。在計算完一個結果後，應該是不需要重新再算一次的。

如果你想知道怎樣才會想到這一點，最簡單的辦法就是使用白板：光盯著問題看也是可以的，但我總是鼓勵候選人在白板上畫出樣本解決方案。像上面那樣畫出樹結構，你就會發現裡面有多個 C(6,2)，你肯定會注意到的。有時候，這足以讓候選人完全繞過解決方案 1 和 2，直接跳到這裡。在一個只有 45 分鐘的面試中，這無疑為你節省了大量的寶貴時間。

那麼，接下來我們該如何解決這個問題？我們可以使用 memoization（不是 memorization），這意味著我們需要記錄之前見過的函數調用結果，並重用它們，而不是重新計算結果。當我們在調用圖中遇到一個沒有必要重新計算整個子樹的位置時，立即返回之前已經計算過的結果。這是一種實現：

那麼現在的運行時複雜性（Big-O）是多少？這很難回答。對於之前的實現，計算運行時複雜度與計算遞歸函數被調用的次數一樣簡單，每個調用總是兩到三次。現在要計算次數比較複雜，因為遞歸調用受條件限制。從表面上看，沒有明確的方法可用於計算函數調用次數。

我們可以通過檢查緩存來解開這個謎團。每個函數調用的結果都保存在緩存中，並且它只被插入一次。於是，問題可以變成「緩存的大小如何隨輸入的大小增長？」因為緩存是由按鍵位置和跳數組成的，並且正好有十個按鍵位置，所以我們可以認為緩存增長與請求的跳數成正比。這遵循的是鴿子洞原理：對於每個按鍵位置和跳數的組合，如果在緩存中都有一個對應條目，那麼所有調用都會使用緩存而不是重新調用函數。

這是線性時間！不錯。添加一個簡單的緩存將演算法的運行複雜度從指數級變為線性的，這其實是非常棒的。在我的老款 MacBook Air 上，遞歸實現大約需要 45 秒才能運行 20 個跳數，而新的實現可以在大約 50 毫秒內處理 500 個跳數。一點也不差。

所以我們已經做到最好了嗎？還不是。這個解決方案有兩個缺點。一個是它是遞歸的。大多數語言都限制了調用棧的大小，這意味著每種實現可以支持的最大跳數都會有一個上限。在我的機器上，在執行大約 1000 個跳數時就失敗了。不過，任何遞歸都可以實現成迭代，但很麻煩。至於另一個缺點，它將導致下一個解決方案的出現……

第 4 級：動態規劃

如果你看一下之前的遞歸關係，你會發現遞歸記憶解決方案的缺點很明顯：

請注意，N 跳的結果只取決於 N-1 跳的調用次數。同時，緩存中包含了每種（非零）跳數。我認為這是一個小問題，因為它實際上不會導致任何實際問題，因為緩存只會隨跳數線性增長。不過，使用線性空間雖然不是導致世界末日，但仍然不是最高效的。

當你在白板上畫出函數調用結構時，結果就很清楚了。請注意，跳數從最大遞歸減到最小：

如果你將整個函數調用圖想像為一棵虛擬樹，你會發現，我們正在進行深度優先遍歷。這也是一個合適的解決方案，但它沒有利用上面指出的淺依賴。

是否可以使用廣度優先遍歷，從頂部開始，並只在調用過 N 跳數的函數之後才能調 N-1 跳數的函數？可惜的是，不行。非零跳數函數返回的值依賴較小跳數的值，因此，在到達零跳數層之前，將不會得到任何結果。

但是，你可以將順序顛倒過來：只在調用了 N-1 跳數的函數之後，才能調用 N 跳數的函數。那些學過或正在學習離散數學的人應該知道歸納法：我們知道，零跳數函數的值總是 1。我們還知道如何使用遞歸關係（歸納步驟）將 N-1 跳的值組合成 N 跳的值。我們可以從零跳數開始，並歸納所有大於零的值。這是一種實現：

那麼這個版本比遞歸深度優先解決方案更好嗎？不會好很多，但肯定會好一些。首先，它不是遞歸的，這意味著它可以運行非常大跳數而不會崩潰。其次，它使用固定的內存，因為它只需要兩個固定大小的數組，而不是像 memoization 那樣緩存會不斷增長。最後，它仍然是線性的：我可以在不到 20 秒的時間內計算 200,000 跳數。

評 價

所以該結束了，對吧？差不多。在面試中設計和實現線性時間、恆定空間的解決方案是一個非常好的結果。我總是會給那些能夠提供動態規劃解決方案的候選人一個很好的評價。

你可能會問，那麼其他解決方案呢？我只能說，我無法對抽象的候選人做出評價。面試不會按照你預想的那樣一成不變，候選人可能來晚了，他們可能會感到緊張，他們經常到了後面才想到解決方案，留給他們編寫代碼的時間就不多了。我還會關注候選人如何溝通他們的想法，並將想法和反饋結合起來。在建議是否讓候選人通過之前，我會考慮這些因素。

在評價演算法和數據結構時，我會說：「候選人探究了這個問題，並提出了可以解決所有邊界情況的解決方案，並在發現缺點時改進了解決方案。最後，他們得出了最佳的解決方案」。我還會說：」候選人為解決方案選擇了合適的數據結構，並正確解釋了運行時複雜度和空間複雜度」。

在評價候選人的編碼能力時，我的理想陳述應該是：「候選人快速而簡潔地將他們的想法轉化為代碼。代碼使用了標準的語言結構，可讀性強。所有邊界情況都考慮到了，候選人仔細檢查代碼，確保它的正確性」。對於入門級崗位，如果候選人提供了測試用例，我會給他們額外的獎勵分，但對於需要更多經驗的崗位，我會懲罰那些沒有列出相關測試用例的候選人。

關於面試進展的速度，我喜歡說：「候選人推動了解決問題的過程：他們給出了自己的解決方案，並且在我沒有幫忙指出的情況下識別出缺點，並加以改進。候選人只需要很少的提示就可以讓解決問題朝著正確的方向前進」。

總 結

這裡列出了這個面試題涵蓋的技能和你應該要去養成的習慣：

先手動解決小規模問題。對於這個面試題，當你手動畫出函數調用結構時，遞歸關係和重複的函數調用就變得更加明顯。

注意不要計算不需要用到的東西，例如那個初級解決方案生成號碼，但實際上用不到它們。減少不必要的計算通常可以提供更簡單的解決方案。

了解遞歸。遞歸在大多數生產代碼中幾乎是沒有用的，因為它可能會爆棧，但卻是一種非常強大的演算法設計策略。遞歸解決方案通常可以進行調整和改進：指數級複雜度解決方案與線性最優 memoization 解決方案之間的差異其實是最小的。

了解 Big-O！在面試過程中，你很有可能會在某個時間點被問到這個問題。

總是想方設法找到 memoization 解決方案。如果你的函數是確定性的，並且會使用相同的輸入多次調用它，那麼可能可以從 memoization 解決方案中受益。

查找並寫出遞歸關係。對於這個面試題，把遞歸關係寫出來，就可以發現 N 跳的計數只取決於 N-1 跳的計數。

但等等，事情還沒有結束！

事情似乎就這麼結束了，但事實證明，這個問題還有另外一個解決方案。在我所有的面試中，我從未見過有人提出這個解決方案。我甚至都不知道它的存在，直到我的一位同事面帶驚訝地回到他的辦公桌前，然後告訴我們，他剛剛面試了一個他認為是有史以來最好的候選人。

但我想先把這個對數級複雜度的解決方案留給讀者去想……

英文原文

https://medium.com/@alexgolec/google-interview-questions-deconstructed-the-knights-dialer-f780d516f029

今日薦文

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！