互聯(lián)網(wǎng)公司最常見的面試算法題有哪些？

所謂知己知彼，百戰(zhàn)不殆，今天就和大家聊聊互聯(lián)網(wǎng)公司那些最常見的面試算法題。

清點(diǎn)面試算法題之前我們先要明確面試官考察的目的，比如有一道經(jīng)典考題是“怎么用3升和5升的桶量出4升的水？”其實(shí)這道題的答案并不難，但是對(duì)于面試官，可以通過這道題考察的內(nèi)容就比較豐富了。

一、概括一下面試算法的目的

1、基礎(chǔ)知識(shí)儲(chǔ)備量

考察知識(shí)儲(chǔ)量是面試算法最基本的目的，但是直接考察算法基礎(chǔ)已經(jīng)很少出現(xiàn)在實(shí)際面試中了，需要快速篩選面試者的時(shí)候才會(huì)用到。

2、思考方向

有的算法可能有兩個(gè)甚至多個(gè)答案，這時(shí)面試官就不是單純的考察面試者的知識(shí)儲(chǔ)備量了，通過面試者的答案可以看出面試者的思考方向，符合公司的日常工作需求才是“有緣人”。

3、解決問題能力

能不能解出答案是次要的，分析和解決問題的思路才是面試官考察的根本所在。

4、輔助能力

算法是整個(gè)計(jì)算機(jī)領(lǐng)域里最基礎(chǔ)的學(xué)科，其余大部分的學(xué)科和技能都是在算法的基礎(chǔ)上展開的，所以這類考察實(shí)則是考察面試者能否快速融入工作當(dāng)中。

總的來說，算法題是綜合考察面試者思維邏輯和基礎(chǔ)知識(shí)的好辦法。

二、算法面試題的類型

雖然面試算法題層出不窮，但從算法的類型來看，互聯(lián)網(wǎng)公司最常見的面試算法題分以下幾種。

1、基礎(chǔ)算法

基礎(chǔ)算法主要有大數(shù)據(jù)查找、快排、哈希算法解決沖突等。以針對(duì)搜索來講，可能設(shè)計(jì)一個(gè)數(shù)據(jù)庫表內(nèi)包含名字、課程、分?jǐn)?shù)3列，求所有課程最低分不小于80分的名單，如果要求用SQL表達(dá)，就是對(duì)于基礎(chǔ)知識(shí)點(diǎn)和基本功的考察。另外可能還會(huì)涉及一些計(jì)算機(jī)網(wǎng)絡(luò)的TCP三次握手協(xié)議等基礎(chǔ)的算法考察。

例如2017京東校招的排序題目：

對(duì)關(guān)鍵字{10,20,8,25,35,6,18,30,5,15,28}序列進(jìn)行希爾排序，取增量d =5時(shí)，排序結(jié)果為（ ）

A. {6,18,8,5,15,10,20,30,25,35,28}

B. {10,18,8,5,15,6,20,30,25,35,28}

C. {10,20,8,5,15,6,18,30,25,35,28}

D. {10,20,30,5,8,6,15,18,25,28,35}

1) 用簡(jiǎn)單取巧的方式，標(biāo)記原始關(guān)鍵字為abcdeabcdea，那么a對(duì)應(yīng)的數(shù)字就是10,6,28，排序后就是6,10,28，所以答案就是A。

2) 當(dāng)然也可以用代碼去實(shí)現(xiàn)，更考驗(yàn)技術(shù)含量，就像下面的JAVA實(shí)現(xiàn)。

public class ShellSort { public static void main(String [] args) { int[]a={49,38,65,97,76,13,27,49,78,34,12,64,1}; System.out.println("排序之前："); for(int i=0;i<a.length;i++) { System.out.print(a[i]+" "); } //希爾排序 int d=a.length; while(true){ for(int i=0;i<d;i++){ for(int j=i;j+d<a.length;j+=d){ int temp; if(a[j]>a[j+d]){ temp=a[j]; a[j]=a[j+d]; a[j+d]=temp; } } } if(d==1){break;} d--; } System.out.println(); System.out.println("排序之后："); for(int i=0;i<a.length;i++) { System.out.print(a[i]+" "); } } }

2、數(shù)據(jù)結(jié)構(gòu)

基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)更多的出現(xiàn)在應(yīng)屆生校招和筆試環(huán)節(jié)中，這類面試題涉及到鏈表、堆、棧、隊(duì)列、圖、二叉樹等。

比如2018年科大訊飛的筆試題：

下面關(guān)于二叉排序樹的說法錯(cuò)誤的是（ ）

A. 在二叉排序樹中，完全二叉樹的查找效率最低

B. 對(duì)二叉排序樹進(jìn)行中序遍歷，必定得到節(jié)點(diǎn)關(guān)鍵字的有序序列

C. 二叉排序樹的平均查找長(zhǎng)度是O(log2n)

D. 二叉排序樹的查找效率與二叉樹的樹形有關(guān)

通過二叉排序樹，可以發(fā)現(xiàn)完全二叉樹的查找效率最高，故答案選A。

3、靈活解決問題的算法

靈活解決問題的算法在面試中占據(jù)了相當(dāng)重要的地位，這類題不告訴面試者具體需要用什么算法，而是虛構(gòu)一個(gè)問題，讓你找出具體的解決方案。

比如騰訊優(yōu)圖的面試題：

給你8顆小石頭和一架天平，其中7顆石頭重量是一樣的，另外一個(gè)比這7顆略重。請(qǐng)問在最壞的情況下，最少要稱量幾次，才能把這顆最終的石頭找出來？

最簡(jiǎn)單的方法是挑出兩顆，把剩下6顆分成兩份稱重，如果一樣重，則再稱一下挑出的那兩顆即可，如果不一樣重，排除較輕的三顆，剩下3顆挑一顆出來，稱其余兩顆。如果一樣重，則挑出的那顆便是，如果不一樣重，重的那顆便是。所以答案是兩次。

淘寶的面試題：

假設(shè)淘寶一天有5億條成交數(shù)據(jù)，求出銷量最高的100個(gè)商品并給出算法的時(shí)間復(fù)雜度。

看似是考察查找算法的，但是因?yàn)樵儐柫藭r(shí)間復(fù)雜度，所以要多想一步，如何優(yōu)化？針對(duì)具體問題，可以把5億條數(shù)據(jù)分組來存放，這樣就可以分別在每個(gè)文件的1000000個(gè)數(shù)據(jù)中，用哈希以及堆來統(tǒng)計(jì)每個(gè)區(qū)域內(nèi)前100個(gè)頻率最高的商品，最后求出所有記錄中出現(xiàn)頻率最高的前100個(gè)商品。

4、崗位需要的具體算法

這一類型的考察比較深入，以自然語言處理（NLP）崗位為例，在算法考察的過程中肯定不會(huì)簡(jiǎn)單的考察搜索等問題，可能直接考察word2vec的huffman tree 和negative sampling的目的是什么，另外還有機(jī)器學(xué)習(xí)領(lǐng)域的AUC曲線、PRF值能衡量什么等問題。

比如阿里巴巴機(jī)器學(xué)習(xí)算法面試：

學(xué)習(xí)過程中出現(xiàn)過擬合現(xiàn)象該怎么辦？

1）重新清洗數(shù)據(jù)，有可能是因?yàn)閿?shù)據(jù)不純導(dǎo)致的過擬合。

2）增大數(shù)據(jù)的訓(xùn)練量，用于訓(xùn)練的數(shù)據(jù)量可能太小。

3）采用正則化方法，包括L0正則、L1正則和L2正則，在機(jī)器學(xué)習(xí)中一般使用L2正則。

4）采用dropout，這個(gè)方法在神經(jīng)網(wǎng)絡(luò)里面很常用，通俗一點(diǎn)講就是在訓(xùn)練的時(shí)候讓神經(jīng)元以一定的概率不工作。

當(dāng)然不同的應(yīng)聘簡(jiǎn)歷、不同的面試官都會(huì)導(dǎo)致問題的側(cè)重有所區(qū)別，但萬變不離其宗，尤其是前兩種最常見的算法，一定不可以大意。

三、應(yīng)對(duì)算法面試的解決方案

總結(jié)一下方法論，面試之前可以參考下面幾個(gè)方式來提高面試成功的概率。

1、書本知識(shí)儲(chǔ)備

在備戰(zhàn)算法面試的過程中，首先還是要打牢基礎(chǔ)，現(xiàn)在市面上有大量的針對(duì)面試算法的書籍，像《算法導(dǎo)論》、《編程珠璣》、《編程之美》都是不錯(cuò)的經(jīng)典教材，在這里推薦一本面試經(jīng)典算法題集錦——《劍指 offer》，這是一本實(shí)戰(zhàn)類的講解書，很貼近實(shí)際，很實(shí)用很接地氣，其次像《程序員面試寶典》上面也都是常見的面試題目。

2、視頻手把手教學(xué)

很多技巧性的東西是書本上難以描述清楚的，但通過視頻學(xué)習(xí)可以準(zhǔn)確領(lǐng)悟老師的思想，比如慕課網(wǎng)上應(yīng)對(duì)面試算法題的課程視頻就有很多，“玩轉(zhuǎn)算法面試 leetcode題庫分門別類詳細(xì)解析”、“程序猿的內(nèi)功修煉，學(xué)好算法與數(shù)據(jù)結(jié)構(gòu)”以及“看的見的算法 7個(gè)經(jīng)典應(yīng)用詮釋算法精髓”，一線老師手把手為你揭秘算法面試的訣竅，這比自己領(lǐng)悟要來的快得多。

3、日常練習(xí)實(shí)踐

紙上得來終覺淺，絕知此事要躬行。平時(shí)有時(shí)間一定要多刷一刷 leetcode、hihocoder，這這兩個(gè)算法習(xí)題網(wǎng)站上很多題目思考起來還是很有意思的，也非常有代表性，因?yàn)樵诿嬖囁惴ǖ倪^程中經(jīng)常有要求現(xiàn)場(chǎng)碼代碼，雖然說不用完全按照編程語言的語法來寫，但不勤加練習(xí)的話，也很難在現(xiàn)場(chǎng)完美表現(xiàn)。

最后提醒各位面試者：從面試算法題中找出“正確”回答固然重要，但是面試官更想從中看到面試者合理的思考方向，而且算法面試優(yōu)秀不意味著能夠拿到Offer，想要得到心儀公司的Offer還是要腳踏實(shí)地學(xué)好每項(xiàng)技能，到時(shí)無論是什么考察方式都將是小菜一碟。最后祝各位面試的程序員早日找到心儀的工作~