前言

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

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

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

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

言歸正傳，以下分數(shù)據(jù)結(jié)構(gòu)題目、算法題目、開放題目三部分來介紹我在面試中碰到的問題。

數(shù)據(jù)結(jié)構(gòu)題目

概述

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

分類討論

類型一：數(shù)據(jù)結(jié)構(gòu)實現(xiàn)

1、實現(xiàn) java.util.List 中的基礎(chǔ)功能；

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

3、選取任意數(shù)據(jù)結(jié)構(gòu)實現(xiàn)添加、刪除、隨機返回三個功能，分析復雜度；

4、用數(shù)組實現(xiàn)隊列，各操作的復雜度分析。

類型二：數(shù)據(jù)結(jié)構(gòu)應用

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

2、用速度不同的指針可以判斷鏈表中是否有環(huán)，問兩速度滿足怎樣的關(guān)系可以保證發(fā)現(xiàn)環(huán)；

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

4、中綴表達式轉(zhuǎn)逆波蘭表達式，逆波蘭表達式求值；

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

6、二叉樹的文件存儲。

準備建議

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

算法題目

概述

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

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

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

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

分類討論

類型一：經(jīng)典算法實現(xiàn)題

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

2、實現(xiàn)KMP，解釋原理；

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

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

類型二：思維益智題

1、數(shù)列中找第 k 大的數(shù)字（與快排或堆排序有關(guān)）；

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

3、一維數(shù)組，swap 其中的幾對數(shù)字（每個數(shù)字只屬于一次 swap 操作），實現(xiàn)查找（與二分有關(guān)）；

4、一個有序數(shù)組，其中一個數(shù)字發(fā)生變異，但不知道變異后會不會影響整體序，如何實現(xiàn)查找；

5、二維數(shù)組，每行遞增，每列遞增

●實現(xiàn)查找；

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

●任意交換其中的兩數(shù)，發(fā)現(xiàn)并恢復；

6、尋找字符串中第一個只出現(xiàn)一次的字符；

7、統(tǒng)計數(shù)列中的逆序?qū)Γw并排序有關(guān)）；

8、最長公共子串（動態(tài)規(guī)劃有關(guān)）；

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

10、給定數(shù)組，尋找 next big（堆排序有關(guān)）；

11、一維有序數(shù)組，經(jīng)過循環(huán)位移后，最小的數(shù)出現(xiàn)在數(shù)列中間

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

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

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

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

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

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

15、墻里能裝多少水；

16、打印螺旋數(shù)組；

17、打印組合數(shù)；

18、字符數(shù)組，統(tǒng)計指定區(qū)間內(nèi)的回文串個數(shù)。

準備建議

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

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

●hihocoder、topcoder、leetcode、codility、POJ 等網(wǎng)站擇一練手。

開放題目

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

1、大數(shù)據(jù)量的 url log，怎么去重且統(tǒng)計每個 url 的出現(xiàn)次數(shù)，復雜度分析；

2、設計 cache 系統(tǒng)

●設計 cache 的接口；

●可以用什么數(shù)據(jù)結(jié)構(gòu)實現(xiàn)；

●如何實現(xiàn)可伸縮的容量；

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

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

3、設計爬蟲；

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

總結(jié)

●數(shù)據(jù)結(jié)構(gòu)和算法的基礎(chǔ)知識還是十分重要的，大部分題目的思路來源于此；

●訓練自己算法復雜度的分析能力，有的時候?qū)碗s度的分析會反過來會幫助你找到更好的算法；

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

審核編輯 ：李倩