問(wèn)答專(zhuān)欄Q & A COLUMN
大家好，我們以java排序算法為例，來(lái)看看面試中常見(jiàn)的算法
第一、基數(shù)排序算法
該算法將數(shù)值按照個(gè)位數(shù)拆分進(jìn)行位數(shù)比較，具體代碼如下：
第二、桶排序算法
該算法將數(shù)值序列分成最大值+1個(gè)桶子，然后遞歸將數(shù)值塞進(jìn)對(duì)應(yīng)值的桶里，具體代碼如下：
第三、計(jì)數(shù)排序算法
該算法計(jì)算數(shù)值序列中每個(gè)數(shù)值出現(xiàn)的次數(shù)，然后存放到多帶帶的數(shù)組中計(jì)數(shù)累加，具體代碼如下：
第四、堆排序算法
該算法將數(shù)值序列中最大值挑選出來(lái)，然后通過(guò)遞歸將剩下的最大值也選出來(lái)，這樣排序就完成了，具體代碼如下：
第五、快速排序算法
該算法將數(shù)值序列拆分成2塊，一塊的所有數(shù)值比另一塊都大，然后分別對(duì)兩塊進(jìn)行快速排序，具體代碼如下：
第六、歸并排序算法
該算法把待排序數(shù)值序列拆分成若干子序列進(jìn)行排序后合并，具體代碼如下：
第七、希爾排序算法
此算法跟插入排序類(lèi)似，是一個(gè)泛化的插入排序，具體代碼如下：
第八、插入排序算法
此算法主要在迭代時(shí)將數(shù)值插入到前面的位置，進(jìn)行比對(duì)換位，具體代碼如下：
第九、選擇排序算法
此算法選擇一個(gè)值然后從右邊開(kāi)始進(jìn)行比對(duì)換位，具體代碼如下：
第十、冒泡排序算法
該算法主要將第一個(gè)和最后一個(gè)數(shù)值進(jìn)行對(duì)比，當(dāng)滿(mǎn)足預(yù)先設(shè)定的條件時(shí)交換一下位置，具體的代碼如下：
希望我的回答能幫到你，謝謝
評(píng)論0
加載中...
簡(jiǎn)單一點(diǎn)的算法題：
手寫(xiě)一個(gè)單例
1、餓漢式
2、懶漢式
還有快速排序、二分查找，這些簡(jiǎn)單的算法，本人遇到過(guò)上面這個(gè)手寫(xiě)單例，當(dāng)時(shí)記得就寫(xiě)了兩種，好像單列有好多種寫(xiě)法，什么線(xiàn)程安全跟線(xiàn)程不安全的。
評(píng)論0
加載中...
所謂知己知彼，百戰(zhàn)不殆，今天就和大家聊聊互聯(lián)網(wǎng)公司那些最常見(jiàn)的面試算法題。
清點(diǎn)面試算法題之前我們先要明確面試官考察的目的，比如有一道經(jīng)典考題是“怎么用3升和5升的桶量出4升的水？”其實(shí)這道題的答案并不難，但是對(duì)于面試官，可以通過(guò)這道題考察的內(nèi)容就比較豐富了。
1、基礎(chǔ)知識(shí)儲(chǔ)備量
考察知識(shí)儲(chǔ)量是面試算法最基本的目的，但是直接考察算法基礎(chǔ)已經(jīng)很少出現(xiàn)在實(shí)際面試中了，需要快速篩選面試者的時(shí)候才會(huì)用到。
2、思考方向
有的算法可能有兩個(gè)甚至多個(gè)答案，這時(shí)面試官就不是單純的考察面試者的知識(shí)儲(chǔ)備量了，通過(guò)面試者的答案可以看出面試者的思考方向，符合公司的日常工作需求才是“有緣人”。
3、解決問(wèn)題能力
能不能解出答案是次要的，分析和解決問(wèn)題的思路才是面試官考察的根本所在。
4、輔助能力
算法是整個(gè)計(jì)算機(jī)領(lǐng)域里最基礎(chǔ)的學(xué)科，其余大部分的學(xué)科和技能都是在算法的基礎(chǔ)上展開(kāi)的，所以這類(lèi)考察實(shí)則是考察面試者能否快速融入工作當(dāng)中。
總的來(lái)說(shuō)，算法題是綜合考察面試者思維邏輯和基礎(chǔ)知識(shí)的好辦法。
雖然面試算法題層出不窮，但從算法的類(lèi)型來(lái)看，互聯(lián)網(wǎng)公司最常見(jiàn)的面試算法題分以下幾種。
1、基礎(chǔ)算法
基礎(chǔ)算法主要有大數(shù)據(jù)查找、快排、哈希算法解決沖突等。以針對(duì)搜索來(lái)講，可能設(shè)計(jì)一個(gè)數(shù)據(jù)庫(kù)表內(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é)中，這類(lèi)面試題涉及到鏈表、堆、棧、隊(duì)列、圖、二叉樹(shù)等。
比如2018年科大訊飛的筆試題：
下面關(guān)于二叉排序樹(shù)的說(shuō)法錯(cuò)誤的是（ ）
A. 在二叉排序樹(shù)中，完全二叉樹(shù)的查找效率最低
B. 對(duì)二叉排序樹(shù)進(jìn)行中序遍歷，必定得到節(jié)點(diǎn)關(guān)鍵字的有序序列
C. 二叉排序樹(shù)的平均查找長(zhǎng)度是O(log2n)
D. 二叉排序樹(shù)的查找效率與二叉樹(shù)的樹(shù)形有關(guān)
通過(guò)二叉排序樹(shù)，可以發(fā)現(xiàn)完全二叉樹(shù)的查找效率最高，故答案選A。
3、靈活解決問(wèn)題的算法
靈活解決問(wèn)題的算法在面試中占據(jù)了相當(dāng)重要的地位，這類(lèi)題不告訴面試者具體需要用什么算法，而是虛構(gòu)一個(gè)問(wèn)題，讓你找出具體的解決方案。
比如ucloud優(yōu)圖的面試題：
給你8顆小石頭和一架天平，其中7顆石頭重量是一樣的，另外一個(gè)比這7顆略重。請(qǐng)問(wèn)在最壞的情況下，最少要稱(chēng)量幾次，才能把這顆最終的石頭找出來(lái)？
最簡(jiǎn)單的方法是挑出兩顆，把剩下6顆分成兩份稱(chēng)重，如果一樣重，則再稱(chēng)一下挑出的那兩顆即可，如果不一樣重，排除較輕的三顆，剩下3顆挑一顆出來(lái)，稱(chēng)其余兩顆。如果一樣重，則挑出的那顆便是，如果不一樣重，重的那顆便是。所以答案是兩次。
淘寶的面試題：
假設(shè)淘寶一天有5億條成交數(shù)據(jù)，求出銷(xiāo)量最高的100個(gè)商品并給出算法的時(shí)間復(fù)雜度。
看似是考察查找算法的，但是因?yàn)樵?xún)問(wèn)了時(shí)間復(fù)雜度，所以要多想一步，如何優(yōu)化？針對(duì)具體問(wèn)題，可以把5億條數(shù)據(jù)分組來(lái)存放，這樣就可以分別在每個(gè)文件的1000000個(gè)數(shù)據(jù)中，用哈希以及堆來(lái)統(tǒng)計(jì)每個(gè)區(qū)域內(nèi)前100個(gè)頻率最高的商品，最后求出所有記錄中出現(xiàn)頻率最高的前100個(gè)商品。
4、崗位需要的具體算法
這一類(lèi)型的考察比較深入，以自然語(yǔ)言處理（NLP）崗位為例，在算法考察的過(guò)程中肯定不會(huì)簡(jiǎn)單的考察搜索等問(wèn)題，可能直接考察word2vec的huffman tree 和negative sampling的目的是什么，另外還有機(jī)器學(xué)習(xí)領(lǐng)域的AUC曲線(xiàn)、PRF值能衡量什么等問(wèn)題。
比如ucloud巴巴機(jī)器學(xué)習(xí)算法面試：
學(xué)習(xí)過(guò)程中出現(xiàn)過(guò)擬合現(xiàn)象該怎么辦？
1）重新清洗數(shù)據(jù)，有可能是因?yàn)閿?shù)據(jù)不純導(dǎo)致的過(guò)擬合。
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)致問(wèn)題的側(cè)重有所區(qū)別，但萬(wàn)變不離其宗，尤其是前兩種最常見(jiàn)的算法，一定不可以大意。
總結(jié)一下方法論，面試之前可以參考下面幾個(gè)方式來(lái)提高面試成功的概率。
1、書(shū)本知識(shí)儲(chǔ)備
在備戰(zhàn)算法面試的過(guò)程中，首先還是要打牢基礎(chǔ)，現(xiàn)在市面上有大量的針對(duì)面試算法的書(shū)籍，像《算法導(dǎo)論》、《編程珠璣》、《編程之美》都是不錯(cuò)的經(jīng)典教材，在這里推薦一本面試經(jīng)典算法題集錦——《劍指 offer》，這是一本實(shí)戰(zhàn)類(lèi)的講解書(shū)，很貼近實(shí)際，很實(shí)用很接地氣，其次像《程序員面試寶典》上面也都是常見(jiàn)的面試題目。
2、視頻手把手教學(xué)
很多技巧性的東西是書(shū)本上難以描述清楚的，但通過(guò)視頻學(xué)習(xí)可以準(zhǔn)確領(lǐng)悟老師的思想，比如慕課網(wǎng)上應(yīng)對(duì)面試算法題的課程視頻就有很多，“玩轉(zhuǎn)算法面試 leetcode題庫(kù)分門(mén)別類(lèi)詳細(xì)解析”、“程序猿的內(nèi)功修煉，學(xué)好算法與數(shù)據(jù)結(jié)構(gòu)”以及“看的見(jiàn)的算法 7個(gè)經(jīng)典應(yīng)用詮釋算法精髓”，一線(xiàn)老師手把手為你揭秘算法面試的訣竅，這比自己領(lǐng)悟要來(lái)的快得多。
3、日常練習(xí)實(shí)踐
紙上得來(lái)終覺(jué)淺，絕知此事要躬行。平時(shí)有時(shí)間一定要多刷一刷 leetcode、hihocoder，這這兩個(gè)算法習(xí)題網(wǎng)站上很多題目思考起來(lái)還是很有意思的，也非常有代表性，因?yàn)樵诿嬖囁惴ǖ倪^(guò)程中經(jīng)常有要求現(xiàn)場(chǎng)碼代碼，雖然說(shuō)不用完全按照編程語(yǔ)言的語(yǔ)法來(lái)寫(xiě)，但不勤加練習(xí)的話(huà)，也很難在現(xiàn)場(chǎng)完美表現(xiàn)。
最后提醒各位面試者：從面試算法題中找出“正確”回答固然重要，但是面試官更想從中看到面試者合理的思考方向，而且算法面試優(yōu)秀不意味著能夠拿到Offer，想要得到心儀公司的Offer還是要腳踏實(shí)地學(xué)好每項(xiàng)技能，到時(shí)無(wú)論是什么考察方式都將是小菜一碟。最后祝各位面試的程序員早日找到心儀的工作~
評(píng)論0
加載中...0
回答0
回答0
回答0
回答0
回答0
回答0
回答0
回答0
回答1
回答
