今天就和大家聊聊大公司的面試環節經常涉及的算法題類型以及準備策略。

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

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

但可以非常肯定地說，LeetCode中Medium難度下的問題所用到的算法，基本上都在大學算法課程的內容里。幾乎沒有超綱的內容，也不涉及比較復雜和困難的數據結構，都是非常非常基礎的，甚至都遠遠達不到高中信息競賽的水平。我一點沒和大家夸張，下面這張圖是我網盤里當年高中競賽的課件，大家可以感受一下難度。

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

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

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

根據我的經驗，面試當中常問的問題基本上就這幾種：二分、遞歸、分治、排序、動態規劃。

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

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

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

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

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

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

在面試的時候面試官往往不會明確給出數據的規模，我們可以自己結合實際情況分析，當然直接提問也是一個不錯的選擇。

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

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

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

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

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

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

冒泡排序和選擇排序有什么區別？

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

排序的穩定性是什么？哪些算法是穩定的，哪些不是？

關于快速排序算法的最差復雜度，有哪些優化？

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

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

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

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

責任編輯：haq