前言

面試 IT 企業的研發崗位，數據結構和算法顯然是必考的項目。俺只學過普通的數據結構課程，沒讀過 STL，也沒有過 ACM 的訓練和比賽經歷，在一開始面對這樣類型題目的時候，心里還是十分忐忑的。大大小小幾十場面試下來，自己在這方面總算有了一定的心得積累，在此拋磚引玉，以饗讀者。

在正式介紹題目和準備方法之前，有兩點需要說明，

●Google 和 Facebook 這類對算法有很高要求的公司的在線測試我沒有參加過（不過在牛人內推幫助下有過面試體驗……），這超出了我目前的編碼能力范圍，網上有不少拿到 Google、Facebook offer 的經驗總結文章，可以移步觀賞；

●前段時間在微博上又看到有人說自己把 leetcode 刷了好幾遍，不過一些轉發評論者覺得， IT 公司面試中的算法考察沒有價值，一來工作里用不太上，二來把程序員素質考察搞成了應試教育，他們認為更重要的是應聘者的工程能力。遇到這樣的討論，我一般喜歡和一把稀泥。若干年前， Google、微軟的面試題讓大家眼前一亮，覺得能選拔出個性十足的聰明人來，不過隨著大家對這類題目的適應，可能選拔出來的人也在趨同，至少很多人都會在面試前用心準備，據報道 Google 最近也是放棄了這類面試題目。沒有什么一勞永逸、一成不變的考查方式，畢竟面試是人和人之間的動態“較量”。不要貪戀算法的奇技淫巧，也不要因為題目篩選力度的衰減而否定考察初衷。面試不僅是考驗求職者，也同樣在考驗面試官，如果問的都是老題兒，那本山大叔肯定都會搶答了。

言歸正傳，以下分數據結構題目、算法題目、開放題目三部分來介紹我在面試中碰到的問題。

數據結構題目

概述

雖然課本由簡到繁、由難到易地介紹了諸多數據結構，我在面試中被問到的卻還都是基本類型，比如堆棧、隊列、鏈表、二叉樹。題目主要有兩類，數據結構實現和具體情境下數據結構的應用。

分類討論

類型一：數據結構實現

1、實現 java.util.List 中的基礎功能；

2、實現棧，使得 添加、刪除、max 操作的復雜度為 O(1)（我腳著好像是不可實現的，想到最好的是添加、刪除 O(log)， max 是 O(1)），實現見 正在努力減肥的胖子 同學給出的評論，參考 leetcode 中的這道題目，慚愧；

3、選取任意數據結構實現添加、刪除、隨機返回三個功能，分析復雜度；

4、用數組實現隊列，各操作的復雜度分析。

類型二：數據結構應用

1、兩棵樹相加——對應位置兩棵樹都有值則相加，對應位置只有一棵樹有值則取該值；

2、用速度不同的指針可以判斷鏈表中是否有環，問兩速度滿足怎樣的關系可以保證發現環；

3、如何在語料中尋找頻繁出現的字串，分析復雜度（tire樹）；

4、中綴表達式轉逆波蘭表達式，逆波蘭表達式求值；

5、數據解壓縮，3(a4(ab)) -> aababababaababababaabababab；

6、二叉樹的文件存儲。

準備建議

上上之選當然是看《算法導論》，書 和 公開課 都算。時間精力不足又想臨時抱佛腳，清華大學計算機系鄧俊輝老師的 教材 是好選擇，也可以看 公開課。注意熟記不同數據結構的不同操作的不同實現方式（比如 哈希表的插入刪除查找）的復雜度分析，不管面試官給你出的題目是難是易，妥妥兒的會問復雜度。

算法題目

概述

有過面試經歷的企業（BAT、小米、宜信、猿題庫、FreeWheel等）當中，還沒有誰問過我需要復雜算法（比方說 此鏈接 中的很多知識點）才能解決的問題。我遇到的算法題目大致可以分為兩類：

●經典算法實現題 快速排序、歸并排序、堆排序、KMP算法等都是重點，重要的是代碼的正確性，其次是復雜度分析，當然，人家也不都是直接問你怎么實現這個具體算法，而是包裝到情境里；

●思維益智題 考察你分析問題的能力，大部分可以歸結到二分、動態規劃、遞歸上，重要的是思路，其次是盡量低的復雜度，再次是代碼的正確性。

下面具體介紹我遇到的兩種類型題目中的問題。

分類討論

類型一：經典算法實現題

1、實現快速排序、歸并排序、堆排序，各排序算法復雜度分析；

2、實現KMP，解釋原理；

3、迷宮的深度搜索、廣度搜索；

4、寫 find 函數，在目標串中匹配模式串（要考慮中文字符的情況）。

類型二：思維益智題

1、數列中找第 k 大的數字（與快排或堆排序有關）；

2、兩個有序數組，尋找歸并排序后數組的中位數/第 k 大數字（與二分有關）；

3、一維數組，swap 其中的幾對數字（每個數字只屬于一次 swap 操作），實現查找（與二分有關）；

4、一個有序數組，其中一個數字發生變異，但不知道變異后會不會影響整體序，如何實現查找；

5、二維數組，每行遞增，每列遞增

●實現查找；

●二維數組，每行遞增，每列遞增，求第 k 大的數；

●任意交換其中的兩數，發現并恢復；

6、尋找字符串中第一個只出現一次的字符；

7、統計數列中的逆序對（歸并排序有關）；

8、最長公共子串（動態規劃有關）；

9、最大子序列和，允許交換一次的最大子序列和；

10、給定數組，尋找 next big（堆排序有關）；

11、一維有序數組，經過循環位移后，最小的數出現在數列中間

●如果原數組嚴格遞增，如何找這個最小數；

●如果原數組嚴格遞增或遞減，如何找這個最小數；

●如果原數組非嚴格遞增或遞減，如何找這個最小數；

12、數組可能是遞增、遞減、遞減后遞增、遞增后遞減四種情況，遞增遞減都是非嚴格的，如果有轉折點，返回轉折點的值，否則返回-1；

13、單向網絡，起點和終點唯一且連通，尋找那些一旦被刪除將導致起點終點無法連通的點；

14、有序數組尋找和為某數的一對數字；

15、墻里能裝多少水；

16、打印螺旋數組；

17、打印組合數；

18、字符數組，統計指定區間內的回文串個數。

準備建議

●不要糾結于是否是最佳思路，要保證能在 10-15 分鐘內給出一個解決方案，并分析復雜度；

●基礎的可以讀讀 @研究者July 的這本 電子書，更深入的可以閱讀 CSDN 等博客中大牛們寫的 ACM 解題報告；

●hihocoder、topcoder、leetcode、codility、POJ 等網站擇一練手。

開放題目

這類開放題目讓你自主選擇數據結構，主要是考察求職者對于數據結構的特性與使用場景的綜合理解，在面對具體應用場景時能否運用已有的數據結構和算法知識提出合理的解決方案。一般來說在這類問題里哈希表的出場率會比較高……例題如下

1、大數據量的 url log，怎么去重且統計每個 url 的出現次數，復雜度分析；

2、設計 cache 系統

●設計 cache 的接口；

●可以用什么數據結構實現；

●如何實現可伸縮的容量；

●cache 的空間管理策略，比如 cache 哪些條目，何時清理；

●cache 系統啟動時分配多大的空間，之后按照怎樣的策略增大；

3、設計爬蟲；

4、流媒體播放客戶端從多個完全相同的發送方接收視頻包，同一發送方的包會按序到達，不同發送方的包則不一定，有可能會丟包，但還是要保證播放流暢度，設計播放客戶端的算法。

總結

●數據結構和算法的基礎知識還是十分重要的，大部分題目的思路來源于此；

●訓練自己算法復雜度的分析能力，有的時候對復雜度的分析會反過來會幫助你找到更好的算法；

●一定量的題目積累很重要，就好像準備高考數學壓軸題一樣，見識的越多，思路來得越快，當然，前提是你能夠不斷總結反思。

審核編輯 ：李倩