今天就和大家聊聊大公司的面試環(huán)節(jié)經(jīng)常涉及的算法題類型以及準(zhǔn)備策略。

問題難度首先大家比較關(guān)心的就是面試時(shí)候出現(xiàn)的算法題的難度，從我的個(gè)人經(jīng)驗(yàn)來看，除了有一次和同樣有acm獲獎(jiǎng)經(jīng)歷的面試官切磋了一次之外，基本上難度都沒有超過LeetCode的困難難度。并且這還是因?yàn)槲矣衋cm經(jīng)歷加成的情況下，大部分問題都只有LeetCode Medium的難度。

當(dāng)然LeetCode的中等難度這個(gè)范圍也是比較寬的，既有非常簡(jiǎn)單無聊的水題，也有比較棘手，值得深入思考的高價(jià)值問題。所以只是知道這一點(diǎn)一點(diǎn)用也沒有，想要知道對(duì)自己來說究竟有多難，還是需要自己親身體會(huì)一下。

但可以非常肯定地說，LeetCode中Medium難度下的問題所用到的算法，基本上都在大學(xué)算法課程的內(nèi)容里。幾乎沒有超綱的內(nèi)容，也不涉及比較復(fù)雜和困難的數(shù)據(jù)結(jié)構(gòu)，都是非常非常基礎(chǔ)的，甚至都遠(yuǎn)遠(yuǎn)達(dá)不到高中信息競(jìng)賽的水平。我一點(diǎn)沒和大家夸張，下面這張圖是我網(wǎng)盤里當(dāng)年高中競(jìng)賽的課件，大家可以感受一下難度。

但是算法這個(gè)東西，大家千萬不要被嚇到，主要是心理上唬人，實(shí)際的難度并沒有那么大。真正下定決心去練習(xí)，從入門到精通也不過是幾個(gè)月的事情。我當(dāng)年好幾個(gè)隊(duì)友都是大學(xué)才開始編程，短短半年時(shí)間已經(jīng)在賽場(chǎng)上獨(dú)當(dāng)一面了。

常見的題型面試或者白板編程，由于形式的限制，題目的選擇范圍其實(shí)并不大。并不難理解，畢竟面試的時(shí)間有限，也不能全拿來做題，而太困難太復(fù)雜的問題候選人一點(diǎn)思路也沒有，大部分人都做不上來，也完全起不到考察和篩選的意義。

所以拿來當(dāng)做面試和白板編程的問題，不會(huì)很復(fù)雜，至少會(huì)保證絕大多數(shù)的候選人都聽說過。就好像打游戲一樣，哪怕是玩家津津樂道的魂游戲，總要有過關(guān)的可能。如果上來就考察一個(gè)問題，結(jié)果你連正解用到的算法都沒聽說過，一開始就沒有做出來的可能，這種問題問了就只能浪費(fèi)時(shí)間。

根據(jù)我的經(jīng)驗(yàn)，面試當(dāng)中常問的問題基本上就這幾種：二分、遞歸、分治、排序、動(dòng)態(tài)規(guī)劃。

這幾種算法只要是科班出身，基本上都或多或少聽說過，理論上來說都應(yīng)該能做出來。并且這些算法除了比較基礎(chǔ)之外，它們的代碼量都不大，一般核心代碼都不會(huì)超過30行，確保編碼的時(shí)間不會(huì)太長。第二是比較考驗(yàn)思維，通過你對(duì)這幾個(gè)算法的理解深度，就足以看出來你的思維能力和算法能力了。

解題套路劃好了重點(diǎn)，再分享幾個(gè)解題的套路。

縮小問題規(guī)模有可能問題里問的是一個(gè)規(guī)模很大的問題，比如漢諾塔問題，要移動(dòng)64個(gè)圓盤，這太復(fù)雜了，我們根本無法思考。不妨把問題的規(guī)模縮小，比如縮小到3個(gè)圓盤，然后我們就可以列舉一下情況，找找規(guī)律和套路了。

即使是在acm賽場(chǎng)當(dāng)中，這個(gè)方法也非常管用。

確定復(fù)雜度在acm賽場(chǎng)上題目當(dāng)中都會(huì)標(biāo)明數(shù)據(jù)的大小范圍，除了起到限制作用之外也是一個(gè)很大的提示。我們可以根據(jù)數(shù)據(jù)的規(guī)模反推出正解的復(fù)雜度范圍，從而排除掉一些不可能的算法。

比如說要在個(gè)數(shù)當(dāng)中尋找某個(gè)數(shù)，由于計(jì)算機(jī)每秒的運(yùn)行次數(shù)在這個(gè)量級(jí)，這么大的規(guī)模遍歷一遍都有些扛不住，那么顯然正解的復(fù)雜度一定在及以下。這么一來，我們就可以根據(jù)算法的復(fù)雜度排除掉一大批達(dá)不到要求的算法，排除錯(cuò)誤的選項(xiàng)。

在面試的時(shí)候面試官往往不會(huì)明確給出數(shù)據(jù)的規(guī)模，我們可以自己結(jié)合實(shí)際情況分析，當(dāng)然直接提問也是一個(gè)不錯(cuò)的選擇。

優(yōu)化思路面試不是比賽，并不是一定要給出正解。有的時(shí)候，我們一時(shí)陷入誤區(qū)沒想到解法也是常有的。重要的并不是我們是否想出了解法，而是我們能否展現(xiàn)我們思維的能力，打動(dòng)面試官。

所以有的時(shí)候一下子沒有想到最優(yōu)解也沒有關(guān)系，我們可以先易后難，先把一些簡(jiǎn)單可行的解法說出來，然后再進(jìn)行優(yōu)化。

比如LeetCode第4題，尋找兩個(gè)有序數(shù)組的中位數(shù)。我們當(dāng)然很難一下子想出的正解，但是我們可以先從最簡(jiǎn)單的方法說起。比如重新排序直接尋找，這樣操作的復(fù)雜度是。說出這個(gè)方法之后，我們接著從不使用排序解決問題的角度繼續(xù)思考，如此一步步逐漸深入，即使最終沒能找到正解，也體現(xiàn)出了我們的思考是有章法的，并且思考和分析問題的能力是有的。

建議最后給大家分享幾點(diǎn)我個(gè)人的小建議，幫助大家少走點(diǎn)彎路。

貴精不貴多如果是為了準(zhǔn)備面試，就像我前面列舉的一樣，其實(shí)并不會(huì)涉及很多內(nèi)容。相比去研究很多高大上面試的時(shí)候用不到的高大上算法，倒不如好好把這幾個(gè)算法啃扎實(shí)。

就拿排序來說，想要全部搞明白就很不簡(jiǎn)單。我隨便寫幾個(gè)問題，大家不妨對(duì)照一下看看能不能回答上來。

冒泡排序和選擇排序有什么區(qū)別？

為什么說快速排序和歸并排序都基于分治算法，但它們的最差復(fù)雜度不同？

排序的穩(wěn)定性是什么？哪些算法是穩(wěn)定的，哪些不是？

關(guān)于快速排序算法的最差復(fù)雜度，有哪些優(yōu)化？

如果都能不僅僅滿足原理，而是可以深入到細(xì)節(jié)的方方面面去鉆研，那么即使只是準(zhǔn)備了幾個(gè)算法，應(yīng)付一般的面試都不在話下。

成體系化訓(xùn)練算法的學(xué)習(xí)過程是比較痛苦的，尤其是如果我們漫無目的地去訓(xùn)練和學(xué)習(xí)，進(jìn)展非常緩慢，非常勸退。很多同學(xué)都有刷題刷了一堆，但是水平好像沒什么提升的情況。

我個(gè)人感覺比較有效的方法是成體系化的訓(xùn)練，不要按照題目順序刷題，而是以算法劃分專題，按照專題刷題。一個(gè)算法一個(gè)算法的硬啃，一個(gè)算法吃透再吃下一個(gè)。這樣訓(xùn)練下來印象會(huì)非常深刻，對(duì)于算法的理解也會(huì)深刻得多，也不容易忘記。要比題目刷了一堆， 算法也用了一堆， 看起用得多，但也忘得多要好得多。

篇幅有限，今天就和大家聊到這里，感謝閱讀和支持。

責(zé)任編輯：haq