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

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

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

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

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

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

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

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

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

解題套路劃好了重點，再分享幾個解題的套路。

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

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

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

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

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

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

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

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

建議最后給大家分享幾點我個人的小建議，幫助大家少走點彎路。

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

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

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

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

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

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

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

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

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

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

責(zé)任編輯：haq