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