前Google工程師總結的算法面試指南
[導讀]為什么要學習算法和數據結構？盡管原因有很多，比如鍛煉邏輯思維能力、編碼能力、閱讀源碼的能力等等，但我想對于大多數人來說，最務實、最簡單的原因是應付算法面試?，F(xiàn)在，隨著IT就業(yè)人員越來越多，內卷越來越嚴重，公司的招聘門檻也越來越高。之前很多公司的面試重視框架、語言、項目經歷等層面的...
為什么要學習算法和數據結構？盡管原因有很多，比如鍛煉邏輯思維能力、編碼能力、閱讀源碼的能力等等，但我想對于大多數人來說，最務實、最簡單的原因是應付算法面試。
現(xiàn)在，隨著IT就業(yè)人員越來越多，內卷越來越嚴重，公司的招聘門檻也越來越高。之前很多公司的面試重視框架、語言、項目經歷等層面的考察，現(xiàn)在，為了拔高招聘門檻，很多公司開始越來越重視基本功的考察，特別是數據結構和算法。
除此之外，對于很多人心儀的大廠，比如BAT、今日頭條、拼多多，算法更是面試中的必考項目。不僅如此，近兩年，一些二三線公司、優(yōu)質創(chuàng)業(yè)公司，也都開始重視算法面試。所以，不管是校招還是社招，只要是應聘一線開發(fā)，不管是工程師、架構師，還是開發(fā)Leader，都很難逃過算法面試這一環(huán)。
能輕松應對算法面試，并不是件臨時抱佛腳就能搞定的事情，需要長期的學習和積累。不過，本篇文章不打算細致入微的講解如何學習算法，而是只針對算法面試這一點，就我自己面試和被面試的經歷，給你指明應對算法面試的一個大的努力方向和學習框架，讓你可以有章可循，事半功倍。
01—
為什么大廠都喜歡考算法呢？僅僅是為了拔高招聘門檻嗎？當然不是。面試是為了過濾、選拔具有優(yōu)秀開發(fā)能力的人才，所有面試題目的設計都圍繞著這個目的。了解了算法面試的目的，你才能更加“投其所好”地表現(xiàn)。
通過算法面試，我們可以很好的了解候選人對數據結構和算法的掌握程度、邏輯思維是否清晰、代碼編寫是否規(guī)范，甚至可以考察出候選人的學習能力、理解能力、知識遷移能力、舉一反三能力、溝通能力等等，而上面列舉到的這些所有能力，都會直接體現(xiàn)到候選人在今后工作中的表現(xiàn)。
不管你工作多久，三年、五年，還是十年，如果在面試中被要求寫一段代碼，千萬別以為面試官只是考察你會不會寫代碼而已。比如有一道經典的算法面試題目是求平方根問題，你可能會說，這個題目直接調用Math.sqrt()函數不就解決了嗎？為啥還要多此一舉自己實現(xiàn)？顯然面試官要考察的并不是問題本身。實際上，寫代碼只是一個考察形式，面試官希望你展示的是寫出好代碼背后所需要具備的能力。
算法面試題目一般分為兩類，一類是偏實戰(zhàn)的題目，另一類是偏編碼的題目。
對于偏實戰(zhàn)的題目，一般面試官會給你一個接近真實項目場景的問題，然后讓你結合具體的場景，思考解決方案。這類題目往往比較開放，需要你做需求的挖掘、分析、假設，合理恰當地應用數據結構和算法是答題的關鍵。這類問題一般代碼實現(xiàn)都比較繁瑣，所以，不需要你寫代碼實現(xiàn)，只需要給出思路即可。
對于偏編碼的題目，一般面試官會給你一個類似筆試一樣的題目，有確切的問題描述、輸入和輸出格式，讓你給出算法思路并且編碼實現(xiàn)，這就有點類似做LeetCode上的題目。這類題目的編碼實現(xiàn)也是考察的重點，不過，一般代碼都不會很長，10行~30行的樣子，最多也不會超過50行。
一般來講，偏實戰(zhàn)的算法面試題目，相對來說要少一些，因為要貼近實戰(zhàn)，所以不好出題。而偏編碼的算法面試題目，相對來說就是算法面試的主要形式。一場時長1個小時左右的面試，一般會有兩道題目。第一道題目會比較簡單，相當于一個暖場和摸底，緩和候選人的緊張情緒，試探一下候選人的水平。第二道題目就是“正餐”了，一般會比第一道題目難不少。不過，整體上來說，算法面試并不是競賽，考察的是基本功，所以，難度一般只相當于在LeetCode上“簡單”、“中等”題目的難度。
02—
首先，我們需要全面掌握經典的數據結構和算法。對于經典的數據結構和算法，我們又分為基礎的和高級的兩類。
基礎的數據結構有數組、鏈表、棧、隊列、散列表、二叉樹、堆、圖的定義等，基礎的算法有：排序、二分查找、二叉樹上的操作（遍歷、查找、插入、刪除等）、圖的深度廣度優(yōu)先搜索、字符串樸素匹配算法，以及遞歸、分治、貪心、回溯、動態(tài)規(guī)劃等基礎算法思想。
高級的數據結構和算法有跳表、并查集、線段樹、樹狀數組、BM算法、KMP算法、AC自動機、紅黑樹、B 樹、圖的一些高級算法（比如最大流、二分匹配、Dijkstra、Floyd算法）等。
對于基礎的數據結構和算法，我們需要掌握原理、熟練代碼實現(xiàn)、復雜度分析等，畢竟它們是很多算法問題解決的基礎，需要掌握牢固。比如經典的求平方根問題，實際上就可以轉化成簡單的二分查找，再比如經典的求逆序對個數問題，實際上就是歸并排序算法的改進。如果你連二分查找、歸并排序都沒有寫熟練，對于這些問題的解答，顯然就已經輸在了起跑線上。
對于高級的數據結構和算法，我們只需要理解算法原理、掌握應用場景，對于代碼實現(xiàn)，基本上不做要求，更不需要像對待基礎數據結構和算法那樣，要牢記原理和實現(xiàn)。學了之后忘記了，也沒有關系。
其次，光學不練也不行，我們還需要進行刻意的刷題訓練。畢竟算法面試一般不會直接問你二分查找如何來寫、堆如何來實現(xiàn)，所以，除了要掌握理論知識之外，還要鍛煉將知識應用來解題的能力，這就包括知識遷移能力、舉一反三的能力、抽象建模能力、組合數據結構和算法解決問題的能力等等，而這些能力完全可以通過刷題來鍛煉。而且，在類似LeetCode這樣的網站上刷題，也算是比較接近真實面試的一種模擬演練。
所以，在基本掌握了經典的數據結構和算法之后，你還要用比較長的一段時間（比如半年）來刷題強化訓練。目前，最著名的刷題網站非LeetCode莫屬了。其中，網站對題目有難易程度和類型的分類，你可以針對每種類型，選擇一些題目刻意訓練。特別是對于比較高頻的一些問題，比如鏈表、二叉樹、動態(tài)規(guī)劃、遞歸回溯相關的問題，以及一些經典的問題，比如歸并求逆序對、借助快排求TOP K等問題，要反復練習。畢竟常用的算法和解題套路都是有限的，大部分面試題目也都是基于現(xiàn)有的題目的改造、變形或組合，又或者換一個新的問題背景重新來問，所以，高頻題、經典題要多練習，做到看到題目腦袋里能立刻反應出解決方法，并且能熟練寫出沒有bug的代碼實現(xiàn)。
長期的積累和刷題很重要，但也不能忽略短期的突擊。在面試前，我們需要重新回顧一遍所有的數據結構和算法，并且從網上找一些目標公司的面試題，真刀真槍地模擬演練一把，熱熱身。不僅如此，根據網上的面經，我們還能了解目標公司面試題的難易程度和面試官的喜好，有針對性的準備。比如有的公司喜歡面試動態(tài)規(guī)劃，面試前就去多刷下這類題目，有的公司的算法面試比較簡單，就不要花太多時間刷難題了。
除此之外，我們平時都是在IDE中寫代碼。IDE本身有自動提示功能，并且可以隨意刪刪改改，而算法面試一般要求手寫代碼，對整潔度的要求就要高很多，如果寫得亂七八糟，面試官會覺得你思路混亂。所以，在面試前，你一定要在紙上多練習一下，做到腦袋里想好算法之后，能一氣呵成地寫出代碼?？傊?，要讓平時的訓練無比接近真實的面試場景，這樣才能在面試中不會因為環(huán)境的改變而緊張，才能像平時訓練一樣正常發(fā)揮。
03—
實際上，算法面試也有固定的答題套路。
首先，跟面試官溝通確認問題，包括數據規(guī)模、輸入輸出要求，以及其他一些不清楚的地方，一定要確認沒有理解誤差之后，再進行答題。
答題的過程，先思考最簡單的解決方案，說給面試官聽，然后再行優(yōu)化，思考更加好的解決方案。這樣做的目的是，一方面能緩和自己緊張的心情，不至于大腦放空、卡殼，另一方面，一開始就思考最優(yōu)解法，可能要悶頭想很久，面試官很難知道你的思考進度，也無法基于你現(xiàn)有的思考進度做提示。
不管題目的難易，建議每個題目的思考時間都不要超過10分鐘。10分鐘還想不出解法，更多的時間可能也無濟于事了，而且10分鐘是面試官可以忍受的沉默時間的極限。所以，如果10分鐘還沒有思路，建議跟面試官溝通，以求給與提示。
在想到最優(yōu)解決思路之后，也不要著急寫代碼，先要跟面試官溝通，看是否滿足面試官的要求。在得到面試官的肯定之后，再進行編碼實現(xiàn)，以免進入思維誤區(qū)，想出來的解決辦法有漏洞，并非正確或最優(yōu)解，急匆匆地寫代碼，寫完才發(fā)現(xiàn)有問題，最后也沒有時間去改正或優(yōu)化了。
編碼也是一個非常重要的環(huán)節(jié)。很多算法問題，即便有了解決思路，編碼實現(xiàn)也并不簡單。比如在O(1)空間復雜度內判斷存儲在鏈表中的字符串是否是回文串這樣一個題目，實際上，它就是反轉鏈表和鏈表求中間結點這兩個問題的組合，算法并不難，但要正確、快速地用代碼實現(xiàn)，并不簡單，需要處理很多細節(jié)，稍有不慎就會引入bug，非?？简灪蜻x人的編碼能力。
除此之外，在編寫代碼的過程中，一定要注意編碼規(guī)范，保證代碼整潔、可讀，切記使用i、j、k這樣的字母來命名重要的變量。一目了然的命名，清晰的代碼結構，會反映出候選人良好的編程習慣，從而贏得面試官的好感。
在寫完代碼之后，一定要進行單元測試。列舉完備的測試用例，特別是一些極端測試用例，比如輸入為0、null等，看程序是否運行正確。一方面能驗證自己寫的代碼的正確性，另一方面還能發(fā)現(xiàn)一些邊界條件處理不到位的情況，再者還能讓面試官覺得你思考問題比較全面、細心。
一般情況下，面試官會自己閱讀你的代碼來判斷是否編寫正確，但也有些面試官會要求候選人逐行解釋代碼。為了方面解釋，特別是針對鏈表或樹相關的一些復雜問題，我們可以通過具體的例子或者畫圖來輔助講解。
算法面試并非筆試，并不只看最終答案，考察的重點是候選人在面試的過程中體現(xiàn)出來的溝通能力、邏輯思維能力、分析問題能力、優(yōu)秀的編碼開發(fā)能力等等。所以，有的時候即便你沒有給出最優(yōu)解決思路，也有可能會被錄用，而有的時候，你覺得回答的很不錯，給出了最優(yōu)解，也未必會被錄用。
現(xiàn)在，隨著IT就業(yè)人員越來越多，內卷越來越嚴重，公司的招聘門檻也越來越高。之前很多公司的面試重視框架、語言、項目經歷等層面的考察，現(xiàn)在，為了拔高招聘門檻，很多公司開始越來越重視基本功的考察，特別是數據結構和算法。
除此之外，對于很多人心儀的大廠，比如BAT、今日頭條、拼多多，算法更是面試中的必考項目。不僅如此，近兩年，一些二三線公司、優(yōu)質創(chuàng)業(yè)公司，也都開始重視算法面試。所以，不管是校招還是社招，只要是應聘一線開發(fā)，不管是工程師、架構師，還是開發(fā)Leader，都很難逃過算法面試這一環(huán)。
能輕松應對算法面試，并不是件臨時抱佛腳就能搞定的事情，需要長期的學習和積累。不過，本篇文章不打算細致入微的講解如何學習算法，而是只針對算法面試這一點，就我自己面試和被面試的經歷，給你指明應對算法面試的一個大的努力方向和學習框架，讓你可以有章可循，事半功倍。
01—
算法面試的目的和題型
為什么大廠都喜歡考算法呢？僅僅是為了拔高招聘門檻嗎？當然不是。面試是為了過濾、選拔具有優(yōu)秀開發(fā)能力的人才，所有面試題目的設計都圍繞著這個目的。了解了算法面試的目的，你才能更加“投其所好”地表現(xiàn)。
通過算法面試，我們可以很好的了解候選人對數據結構和算法的掌握程度、邏輯思維是否清晰、代碼編寫是否規(guī)范，甚至可以考察出候選人的學習能力、理解能力、知識遷移能力、舉一反三能力、溝通能力等等，而上面列舉到的這些所有能力，都會直接體現(xiàn)到候選人在今后工作中的表現(xiàn)。
不管你工作多久，三年、五年，還是十年，如果在面試中被要求寫一段代碼，千萬別以為面試官只是考察你會不會寫代碼而已。比如有一道經典的算法面試題目是求平方根問題，你可能會說，這個題目直接調用Math.sqrt()函數不就解決了嗎？為啥還要多此一舉自己實現(xiàn)？顯然面試官要考察的并不是問題本身。實際上，寫代碼只是一個考察形式，面試官希望你展示的是寫出好代碼背后所需要具備的能力。
算法面試題目一般分為兩類，一類是偏實戰(zhàn)的題目，另一類是偏編碼的題目。
對于偏實戰(zhàn)的題目，一般面試官會給你一個接近真實項目場景的問題，然后讓你結合具體的場景，思考解決方案。這類題目往往比較開放，需要你做需求的挖掘、分析、假設，合理恰當地應用數據結構和算法是答題的關鍵。這類問題一般代碼實現(xiàn)都比較繁瑣，所以，不需要你寫代碼實現(xiàn)，只需要給出思路即可。
對于偏編碼的題目，一般面試官會給你一個類似筆試一樣的題目，有確切的問題描述、輸入和輸出格式，讓你給出算法思路并且編碼實現(xiàn)，這就有點類似做LeetCode上的題目。這類題目的編碼實現(xiàn)也是考察的重點，不過，一般代碼都不會很長，10行~30行的樣子，最多也不會超過50行。
一般來講，偏實戰(zhàn)的算法面試題目，相對來說要少一些，因為要貼近實戰(zhàn)，所以不好出題。而偏編碼的算法面試題目，相對來說就是算法面試的主要形式。一場時長1個小時左右的面試，一般會有兩道題目。第一道題目會比較簡單，相當于一個暖場和摸底，緩和候選人的緊張情緒，試探一下候選人的水平。第二道題目就是“正餐”了，一般會比第一道題目難不少。不過，整體上來說，算法面試并不是競賽，考察的是基本功，所以，難度一般只相當于在LeetCode上“簡單”、“中等”題目的難度。
02—
算法面試前的準備工作
首先，我們需要全面掌握經典的數據結構和算法。對于經典的數據結構和算法，我們又分為基礎的和高級的兩類。
基礎的數據結構有數組、鏈表、棧、隊列、散列表、二叉樹、堆、圖的定義等，基礎的算法有：排序、二分查找、二叉樹上的操作（遍歷、查找、插入、刪除等）、圖的深度廣度優(yōu)先搜索、字符串樸素匹配算法，以及遞歸、分治、貪心、回溯、動態(tài)規(guī)劃等基礎算法思想。
高級的數據結構和算法有跳表、并查集、線段樹、樹狀數組、BM算法、KMP算法、AC自動機、紅黑樹、B 樹、圖的一些高級算法（比如最大流、二分匹配、Dijkstra、Floyd算法）等。
對于基礎的數據結構和算法，我們需要掌握原理、熟練代碼實現(xiàn)、復雜度分析等，畢竟它們是很多算法問題解決的基礎，需要掌握牢固。比如經典的求平方根問題，實際上就可以轉化成簡單的二分查找，再比如經典的求逆序對個數問題，實際上就是歸并排序算法的改進。如果你連二分查找、歸并排序都沒有寫熟練，對于這些問題的解答，顯然就已經輸在了起跑線上。
對于高級的數據結構和算法，我們只需要理解算法原理、掌握應用場景，對于代碼實現(xiàn)，基本上不做要求，更不需要像對待基礎數據結構和算法那樣，要牢記原理和實現(xiàn)。學了之后忘記了，也沒有關系。
其次，光學不練也不行，我們還需要進行刻意的刷題訓練。畢竟算法面試一般不會直接問你二分查找如何來寫、堆如何來實現(xiàn)，所以，除了要掌握理論知識之外，還要鍛煉將知識應用來解題的能力，這就包括知識遷移能力、舉一反三的能力、抽象建模能力、組合數據結構和算法解決問題的能力等等，而這些能力完全可以通過刷題來鍛煉。而且，在類似LeetCode這樣的網站上刷題，也算是比較接近真實面試的一種模擬演練。
所以，在基本掌握了經典的數據結構和算法之后，你還要用比較長的一段時間（比如半年）來刷題強化訓練。目前，最著名的刷題網站非LeetCode莫屬了。其中，網站對題目有難易程度和類型的分類，你可以針對每種類型，選擇一些題目刻意訓練。特別是對于比較高頻的一些問題，比如鏈表、二叉樹、動態(tài)規(guī)劃、遞歸回溯相關的問題，以及一些經典的問題，比如歸并求逆序對、借助快排求TOP K等問題，要反復練習。畢竟常用的算法和解題套路都是有限的，大部分面試題目也都是基于現(xiàn)有的題目的改造、變形或組合，又或者換一個新的問題背景重新來問，所以，高頻題、經典題要多練習，做到看到題目腦袋里能立刻反應出解決方法，并且能熟練寫出沒有bug的代碼實現(xiàn)。
長期的積累和刷題很重要，但也不能忽略短期的突擊。在面試前，我們需要重新回顧一遍所有的數據結構和算法，并且從網上找一些目標公司的面試題，真刀真槍地模擬演練一把，熱熱身。不僅如此，根據網上的面經，我們還能了解目標公司面試題的難易程度和面試官的喜好，有針對性的準備。比如有的公司喜歡面試動態(tài)規(guī)劃，面試前就去多刷下這類題目，有的公司的算法面試比較簡單，就不要花太多時間刷難題了。
除此之外，我們平時都是在IDE中寫代碼。IDE本身有自動提示功能，并且可以隨意刪刪改改，而算法面試一般要求手寫代碼，對整潔度的要求就要高很多，如果寫得亂七八糟，面試官會覺得你思路混亂。所以，在面試前，你一定要在紙上多練習一下，做到腦袋里想好算法之后，能一氣呵成地寫出代碼?？傊?，要讓平時的訓練無比接近真實的面試場景，這樣才能在面試中不會因為環(huán)境的改變而緊張，才能像平時訓練一樣正常發(fā)揮。
03—
算法面試中的解題技巧
實際上，算法面試也有固定的答題套路。
首先，跟面試官溝通確認問題，包括數據規(guī)模、輸入輸出要求，以及其他一些不清楚的地方，一定要確認沒有理解誤差之后，再進行答題。
答題的過程，先思考最簡單的解決方案，說給面試官聽，然后再行優(yōu)化，思考更加好的解決方案。這樣做的目的是，一方面能緩和自己緊張的心情，不至于大腦放空、卡殼，另一方面，一開始就思考最優(yōu)解法，可能要悶頭想很久，面試官很難知道你的思考進度，也無法基于你現(xiàn)有的思考進度做提示。
不管題目的難易，建議每個題目的思考時間都不要超過10分鐘。10分鐘還想不出解法，更多的時間可能也無濟于事了，而且10分鐘是面試官可以忍受的沉默時間的極限。所以，如果10分鐘還沒有思路，建議跟面試官溝通，以求給與提示。
在想到最優(yōu)解決思路之后，也不要著急寫代碼，先要跟面試官溝通，看是否滿足面試官的要求。在得到面試官的肯定之后，再進行編碼實現(xiàn)，以免進入思維誤區(qū)，想出來的解決辦法有漏洞，并非正確或最優(yōu)解，急匆匆地寫代碼，寫完才發(fā)現(xiàn)有問題，最后也沒有時間去改正或優(yōu)化了。
編碼也是一個非常重要的環(huán)節(jié)。很多算法問題，即便有了解決思路，編碼實現(xiàn)也并不簡單。比如在O(1)空間復雜度內判斷存儲在鏈表中的字符串是否是回文串這樣一個題目，實際上，它就是反轉鏈表和鏈表求中間結點這兩個問題的組合，算法并不難，但要正確、快速地用代碼實現(xiàn)，并不簡單，需要處理很多細節(jié)，稍有不慎就會引入bug，非?？简灪蜻x人的編碼能力。
除此之外，在編寫代碼的過程中，一定要注意編碼規(guī)范，保證代碼整潔、可讀，切記使用i、j、k這樣的字母來命名重要的變量。一目了然的命名，清晰的代碼結構，會反映出候選人良好的編程習慣，從而贏得面試官的好感。
在寫完代碼之后，一定要進行單元測試。列舉完備的測試用例，特別是一些極端測試用例，比如輸入為0、null等，看程序是否運行正確。一方面能驗證自己寫的代碼的正確性，另一方面還能發(fā)現(xiàn)一些邊界條件處理不到位的情況，再者還能讓面試官覺得你思考問題比較全面、細心。
一般情況下，面試官會自己閱讀你的代碼來判斷是否編寫正確，但也有些面試官會要求候選人逐行解釋代碼。為了方面解釋，特別是針對鏈表或樹相關的一些復雜問題，我們可以通過具體的例子或者畫圖來輔助講解。
算法面試并非筆試，并不只看最終答案，考察的重點是候選人在面試的過程中體現(xiàn)出來的溝通能力、邏輯思維能力、分析問題能力、優(yōu)秀的編碼開發(fā)能力等等。所以，有的時候即便你沒有給出最優(yōu)解決思路，也有可能會被錄用，而有的時候，你覺得回答的很不錯，給出了最優(yōu)解，也未必會被錄用。
下載文檔
