面試經(jīng)驗(yàn)分享之?dāng)?shù)據(jù)結(jié)構(gòu)、算法題

前言

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

在正式介紹題目和準(zhǔn)備方法之前，有兩點(diǎn)需要說明，

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

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

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

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

概述

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

分類討論

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

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

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

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

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

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

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

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

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

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

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

6、二叉樹的文件存儲(chǔ)。

準(zhǔn)備建議

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

算法題目

概述

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

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

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

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

分類討論

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

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

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

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

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

類型二：思維益智題

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

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

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

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

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

●實(shí)現(xiàn)查找；

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

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

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

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

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

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

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

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

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

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

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

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

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

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

15、墻里能裝多少水；

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

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

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

準(zhǔn)備建議

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

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

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

開放題目

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

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

2、設(shè)計(jì) cache 系統(tǒng)

●設(shè)計(jì) cache 的接口；

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

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

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

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

3、設(shè)計(jì)爬蟲；

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

總結(jié)

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

●訓(xùn)練自己算法復(fù)雜度的分析能力，有的時(shí)候?qū)?fù)雜度的分析會(huì)反過來會(huì)幫助你找到更好的算法；

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

審核編輯 ：李倩