前 Google 工程師總結的算法面試指南

作者 | 小爭哥

出品 | 小爭哥 （ID：xiaozhengge0822）

爲什麼要學習算法和數據結構？儘管原因有很多，比如鍛鍊邏輯思維能力、編碼能力、閱讀源碼的能力等等，但我想對於大多數人來說，最務實、最簡單的原因是應付算法面試。

現在，隨着 IT 就業人員越來越多，內卷越來越嚴重，公司的招聘門檻也越來越高。之前很多公司的面試重視框架、語言、項目經歷等層面的考察，現在，爲了拔高招聘門檻，很多公司開始越來越重視基本功的考察，特別是數據結構和算法。

除此之外，對於很多人心儀的大廠，比如 BAT、今日頭條、拼多多，算法更是面試中的必考項目。不僅如此，近兩年，一些二三線公司、優質創業公司，也都開始重視算法面試。所以，不管是校招還是社招，只要是應聘一線開發，不管是工程師、架構師，還是開發 Leader，都很難逃過算法面試這一環。

能輕鬆應對算法面試，並不是件臨時抱佛腳就能搞定的事情，需要長期的學習和積累。不過，本篇文章不打算細緻入微的講解如何學習算法，而是隻針對算法面試這一點，就我自己面試和被面試的經歷，給你指明應對算法面試的一個大的努力方向和學習框架，讓你可以有章可循，事半功倍。

- 1 -

算法面試的目的和題型

爲什麼大廠都喜歡考算法呢？僅僅是爲了拔高招聘門檻嗎？當然不是。面試是爲了過濾、選拔具有優秀開發能力的人才，所有面試題目的設計都圍繞着這個目的。瞭解了算法面試的目的，你才能更加 “投其所好” 地表現。

通過算法面試，我們可以很好的瞭解候選人對數據結構和算法的掌握程度、邏輯思維是否清晰、代碼編寫是否規範，甚至可以考察出候選人的學習能力、理解能力、知識遷移能力、舉一反三能力、溝通能力等等，而上面列舉到的這些所有能力，都會直接體現到候選人在今後工作中的表現。

不管你工作多久，三年、五年，還是十年，如果在面試中被要求寫一段代碼，千萬別以爲面試官只是考察你會不會寫代碼而已。比如有一道經典的算法面試題目是求平方根問題，你可能會說，這個題目直接調用 Math.sqrt() 函數不就解決了嗎？爲啥還要多此一舉自己實現？顯然面試官要考察的並不是問題本身。實際上，寫代碼只是一個考察形式，面試官希望你展示的是寫出好代碼背後所需要具備的能力。

算法面試題目一般分爲兩類，一類是偏實戰的題目，另一類是偏編碼的題目。

對於偏實戰的題目，一般面試官會給你一個接近真實項目場景的問題，然後讓你結合具體的場景，思考解決方案。這類題目往往比較開放，需要你做需求的挖掘、分析、假設，合理恰當地應用數據結構和算法是答題的關鍵。這類問題一般代碼實現都比較繁瑣，所以，不需要你寫代碼實現，只需要給出思路即可。

對於偏編碼的題目，一般面試官會給你一個類似筆試一樣的題目，有確切的問題描述、輸入和輸出格式，讓你給出算法思路並且編碼實現，這就有點類似做 LeetCode 上的題目。這類題目的編碼實現也是考察的重點，不過，一般代碼都不會很長，10 行~ 30 行的樣子，最多也不會超過 50 行。

一般來講，偏實戰的算法面試題目，相對來說要少一些，因爲要貼近實戰，所以不好出題。而偏編碼的算法面試題目，相對來說就是算法面試的主要形式。一場時長 1 個小時左右的面試，一般會有兩道題目。第一道題目會比較簡單，相當於一個暖場和摸底，緩和候選人的緊張情緒，試探一下候選人的水平。第二道題目就是 “正餐” 了，一般會比第一道題目難不少。不過，整體上來說，算法面試並不是競賽，考察的是基本功，所以，難度一般只相當於在 LeetCode 上 “簡單”、“中等” 題目的難度。

- 2 -

算法面試前的準備工作

首先，我們需要全面掌握經典的數據結構和算法。對於經典的數據結構和算法，我們又分爲基礎的和高級的兩類。

基礎的數據結構有數組、鏈表、棧、隊列、散列表、二叉樹、堆、圖的定義等，基礎的算法有：排序、二分查找、二叉樹上的操作（遍歷、查找、插入、刪除等）、圖的深度廣度優先搜索、字符串樸素匹配算法，以及遞歸、分治、貪心、回溯、動態規劃等基礎算法思想。

高級的數據結構和算法有跳錶、並查集、線段樹、樹狀數組、BM 算法、KMP 算法、AC 自動機、紅黑樹、B + 樹、圖的一些高級算法（比如最大流、二分匹配、Dijkstra、Floyd 算法）等。

對於基礎的數據結構和算法，我們需要掌握原理、熟練代碼實現、複雜度分析等，畢竟它們是很多算法問題解決的基礎，需要掌握牢固。比如經典的求平方根問題，實際上就可以轉化成簡單的二分查找，再比如經典的求逆序對個數問題，實際上就是歸併排序算法的改進。如果你連二分查找、歸併排序都沒有寫熟練，對於這些問題的解答，顯然就已經輸在了起跑線上。

對於高級的數據結構和算法，我們只需要理解算法原理、掌握應用場景，對於代碼實現，基本上不做要求，更不需要像對待基礎數據結構和算法那樣，要牢記原理和實現。學了之後忘記了，也沒有關係。

其次，光學不練也不行，我們還需要進行刻意的刷題訓練。畢竟算法面試一般不會直接問你二分查找如何來寫、堆如何來實現，所以，除了要掌握理論知識之外，還要鍛鍊將知識應用來解題的能力，這就包括知識遷移能力、舉一反三的能力、抽象建模能力、組合數據結構和算法解決問題的能力等等，而這些能力完全可以通過刷題來鍛鍊。而且，在類似 LeetCode 這樣的網站上刷題，也算是比較接近真實面試的一種模擬演練。

所以，在基本掌握了經典的數據結構和算法之後，你還要用比較長的一段時間（比如半年）來刷題強化訓練。目前，最著名的刷題網站非 LeetCode 莫屬了。其中，網站對題目有難易程度和類型的分類，你可以針對每種類型，選擇一些題目刻意訓練。特別是對於比較高頻的一些問題，比如鏈表、二叉樹、動態規劃、遞歸回溯相關的問題，以及一些經典的問題，比如歸併求逆序對、藉助快排求 TOP K 等問題，要反覆練習。畢竟常用的算法和解題套路都是有限的，大部分面試題目也都是基於現有的題目的改造、變形或組合，又或者換一個新的問題背景重新來問，所以，高頻題、經典題要多練習，做到看到題目腦袋裏能立刻反應出解決方法，並且能熟練寫出沒有 bug 的代碼實現。

長期的積累和刷題很重要，但也不能忽略短期的突擊。在面試前，我們需要重新回顧一遍所有的數據結構和算法，並且從網上找一些目標公司的面試題，真刀真槍地模擬演練一把，熱熱身。不僅如此，根據網上的面經，我們還能瞭解目標公司面試題的難易程度和麪試官的喜好，有針對性的準備。比如有的公司喜歡面試動態規劃，面試前就去多刷下這類題目，有的公司的算法面試比較簡單，就不要花太多時間刷難題了。

除此之外，我們平時都是在 IDE 中寫代碼。IDE 本身有自動提示功能，並且可以隨意刪刪改改，而算法面試一般要求手寫代碼，對整潔度的要求就要高很多，如果寫得亂七八糟，面試官會覺得你思路混亂。所以，在面試前，你一定要在紙上多練習一下，做到腦袋裏想好算法之後，能一氣呵成地寫出代碼。總之，要讓平時的訓練無比接近真實的面試場景，這樣才能在面試中不會因爲環境的改變而緊張，才能像平時訓練一樣正常發揮。

- 3 -

算法面試中的解題技巧

實際上，算法面試也有固定的答題套路。

首先，跟面試官溝通確認問題，包括數據規模、輸入輸出要求，以及其他一些不清楚的地方，一定要確認沒有理解誤差之後，再進行答題。

答題的過程，先思考最簡單的解決方案，說給面試官聽，然後再行優化，思考更加好的解決方案。這樣做的目的是，一方面能緩和自己緊張的心情，不至於大腦放空、卡殼，另一方面，一開始就思考最優解法，可能要悶頭想很久，面試官很難知道你的思考進度，也無法基於你現有的思考進度做提示。

不管題目的難易，建議每個題目的思考時間都不要超過 10 分鐘。10 分鐘還想不出解法，更多的時間可能也無濟於事了，而且 10 分鐘是面試官可以忍受的沉默時間的極限。所以，如果 10 分鐘還沒有思路，建議跟面試官溝通，以求給與提示。

在想到最優解決思路之後，也不要着急寫代碼，先要跟面試官溝通，看是否滿足面試官的要求。在得到面試官的肯定之後，再進行編碼實現，以免進入思維誤區，想出來的解決辦法有漏洞，並非正確或最優解，急匆匆地寫代碼，寫完才發現有問題，最後也沒有時間去改正或優化了。

編碼也是一個非常重要的環節。很多算法問題，即便有了解決思路，編碼實現也並不簡單。比如在 O(1) 空間複雜度內判斷存儲在鏈表中的字符串是否是迴文串這樣一個題目，實際上，它就是反轉鏈表和鏈表求中間結點這兩個問題的組合，算法並不難，但要正確、快速地用代碼實現，並不簡單，需要處理很多細節，稍有不慎就會引入 bug，非常考驗候選人的編碼能力。

除此之外，在編寫代碼的過程中，一定要注意編碼規範，保證代碼整潔、可讀，切記使用 i、j、k 這樣的字母來命名重要的變量。一目瞭然的命名，清晰的代碼結構，會反映出候選人良好的編程習慣，從而贏得面試官的好感。

在寫完代碼之後，一定要進行單元測試。列舉完備的測試用例，特別是一些極端測試用例，比如輸入爲 0、null 等，看程序是否運行正確。一方面能驗證自己寫的代碼的正確性，另一方面還能發現一些邊界條件處理不到位的情況，再者還能讓面試官覺得你思考問題比較全面、細心。

一般情況下，面試官會自己閱讀你的代碼來判斷是否編寫正確，但也有些面試官會要求候選人逐行解釋代碼。爲了方面解釋，特別是針對鏈表或樹相關的一些複雜問題，我們可以通過具體的例子或者畫圖來輔助講解。

算法面試並非筆試，並不只看最終答案，考察的重點是候選人在面試的過程中體現出來的溝通能力、邏輯思維能力、分析問題能力、優秀的編碼開發能力等等。所以，有的時候即便你沒有給出最優解決思路，也有可能會被錄用，而有的時候，你覺得回答的很不錯，給出了最優解，也未必會被錄用。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/XmD8mnyIMCpizKRk3foR3w