前言
面試 IT 企業(yè)的研發(fā)崗位,數(shù)據(jù)結(jié)構(gòu)和算法顯然是必考的項(xiàng)目。俺只學(xué)過(guò)普通的數(shù)據(jù)結(jié)構(gòu)課程,沒讀過(guò) STL,也沒有過(guò) ACM 的訓(xùn)練和比賽經(jīng)歷,在一開始面對(duì)這樣類型題目的時(shí)候,心里還是十分忐忑的。大大小小幾十場(chǎng)面試下來(lái),自己在這方面總算有了一定的心得積累,在此拋磚引玉,以饗讀者。
在正式介紹題目和準(zhǔn)備方法之前,有兩點(diǎn)需要說(shuō)明,
●Google 和 Facebook 這類對(duì)算法有很高要求的公司的在線測(cè)試我沒有參加過(guò)(不過(guò)在牛人內(nèi)推幫助下有過(guò)面試體驗(yàn)……),這超出了我目前的編碼能力范圍,網(wǎng)上有不少拿到 Google、Facebook offer 的經(jīng)驗(yàn)總結(jié)文章,可以移步觀賞;
●前段時(shí)間在微博上又看到有人說(shuō)自己把 leetcode 刷了好幾遍,不過(guò)一些轉(zhuǎn)發(fā)評(píng)論者覺得, IT 公司面試中的算法考察沒有價(jià)值,一來(lái)工作里用不太上,二來(lái)把程序員素質(zhì)考察搞成了應(yīng)試教育,他們認(rèn)為更重要的是應(yīng)聘者的工程能力。遇到這樣的討論,我一般喜歡和一把稀泥。若干年前, Google、微軟的面試題讓大家眼前一亮,覺得能選拔出個(gè)性十足的聰明人來(lái),不過(guò)隨著大家對(duì)這類題目的適應(yīng),可能選拔出來(lái)的人也在趨同,至少很多人都會(huì)在面試前用心準(zhǔn)備,據(jù)報(bào)道 Google 最近也是放棄了這類面試題目。沒有什么一勞永逸、一成不變的考查方式,畢竟面試是人和人之間的動(dòng)態(tài)“較量”。不要貪戀算法的奇技淫巧,也不要因?yàn)轭}目篩選力度的衰減而否定考察初衷。面試不僅是考驗(yàn)求職者,也同樣在考驗(yàn)面試官,如果問(wèn)的都是老題兒,那本山大叔肯定都會(huì)搶答了。
言歸正傳,以下分?jǐn)?shù)據(jù)結(jié)構(gòu)題目、算法題目、開放題目三部分來(lái)介紹我在面試中碰到的問(wèn)題。
數(shù)據(jù)結(jié)構(gòu)題目
概述
雖然課本由簡(jiǎn)到繁、由難到易地介紹了諸多數(shù)據(jù)結(jié)構(gòu),我在面試中被問(wèn)到的卻還都是基本類型,比如堆棧、隊(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é)給出的評(píng)論,參考 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、兩棵樹相加——對(duì)應(yīng)位置兩棵樹都有值則相加,對(duì)應(yīng)位置只有一棵樹有值則取該值;
2、用速度不同的指針可以判斷鏈表中是否有環(huán),問(wèn)兩速度滿足怎樣的關(guān)系可以保證發(fā)現(xiàn)環(huán);
3、如何在語(yǔ)料中尋找頻繁出現(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ì)問(wèn)復(fù)雜度。
算法題目
概述
有過(guò)面試經(jīng)歷的企業(yè)(BAT、小米、宜信、猿題庫(kù)、FreeWheel等)當(dāng)中,還沒有誰(shuí)問(wèn)過(guò)我需要復(fù)雜算法(比方說(shuō) 此鏈接 中的很多知識(shí)點(diǎn))才能解決的問(wèn)題。我遇到的算法題目大致可以分為兩類:
●經(jīng)典算法實(shí)現(xiàn)題 快速排序、歸并排序、堆排序、KMP算法等都是重點(diǎn),重要的是代碼的正確性,其次是復(fù)雜度分析,當(dāng)然,人家也不都是直接問(wèn)你怎么實(shí)現(xiàn)這個(gè)具體算法,而是包裝到情境里;
●思維益智題 考察你分析問(wèn)題的能力,大部分可以歸結(jié)到二分、動(dòng)態(tài)規(guī)劃、遞歸上,重要的是思路,其次是盡量低的復(fù)雜度,再次是代碼的正確性。
下面具體介紹我遇到的兩種類型題目中的問(wèn)題。
分類討論
類型一:經(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 其中的幾對(duì)數(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、最長(zhǎng)公共子串(動(dòng)態(tài)規(guī)劃有關(guān));
9、最大子序列和,允許交換一次的最大子序列和;
10、給定數(shù)組,尋找 next big(堆排序有關(guān));
11、一維有序數(shù)組,經(jīng)過(guò)循環(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)無(wú)法連通的點(diǎn);
14、有序數(shù)組尋找和為某數(shù)的一對(duì)數(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),主要是考察求職者對(duì)于數(shù)據(jù)結(jié)構(gòu)的特性與使用場(chǎng)景的綜合理解,在面對(duì)具體應(yīng)用場(chǎng)景時(shí)能否運(yùn)用已有的數(shù)據(jù)結(jié)構(gòu)和算法知識(shí)提出合理的解決方案。一般來(lái)說(shuō)在這類問(wèn)題里哈希表的出場(chǎng)率會(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í)還是十分重要的,大部分題目的思路來(lái)源于此;
●訓(xùn)練自己算法復(fù)雜度的分析能力,有的時(shí)候?qū)?fù)雜度的分析會(huì)反過(guò)來(lái)會(huì)幫助你找到更好的算法;
●一定量的題目積累很重要,就好像準(zhǔn)備高考數(shù)學(xué)壓軸題一樣,見識(shí)的越多,思路來(lái)得越快,當(dāng)然,前提是你能夠不斷總結(jié)反思。
審核編輯 :李倩
-
算法
+關(guān)注
關(guān)注
23文章
4580瀏覽量
92361 -
數(shù)據(jù)結(jié)構(gòu)
+關(guān)注
關(guān)注
3文章
569瀏覽量
40063
原文標(biāo)題:面試經(jīng)驗(yàn)分享之?dāng)?shù)據(jù)結(jié)構(gòu)、算法題
文章出處:【微信號(hào):TheAlgorithm,微信公眾號(hào):算法與數(shù)據(jù)結(jié)構(gòu)】歡迎添加關(guān)注!文章轉(zhuǎn)載請(qǐng)注明出處。
發(fā)布評(píng)論請(qǐng)先 登錄
相關(guān)推薦
評(píng)論