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