【原】求職指南【5】-算法工程師綜合面試100問

知識分享家 2021-04-16

展開全文

AI研習(xí)圖書館，發(fā)現(xiàn)不一樣的精彩世界

算法
面試

算法工程師面試知識點總結(jié)五

一、前言

算法工程師面試100問，問題搜集整理于網(wǎng)絡(luò)，包括算法崗面試過程中可能會被問及的100個常見機(jī)器學(xué)習(xí)問題，如數(shù)據(jù)結(jié)構(gòu)、基礎(chǔ)算法、機(jī)器學(xué)習(xí)算法等。本次關(guān)于算法工程師面試中常見的100個問題，大多是各類網(wǎng)站的問題匯總，希望聰明伶俐的你能從中分析出一些端倪，文末附了部分問題的參考答案，精力和水平有限，僅供大家學(xué)習(xí)參考~

二、算法面試100問

1. kNN，樸素貝葉斯及SVM算法的優(yōu)缺點

2. 樸素貝葉斯的核心思想，有沒有考慮屬性之間不是相互獨立的情況

3. 10億個整數(shù)，1G內(nèi)存，O(n)算法，統(tǒng)計只出現(xiàn)一次的數(shù)

4. SVM非線性分類，核函數(shù)的作用

5. 海量數(shù)據(jù)排序

6. 項目中的數(shù)據(jù)是否會歸一化處理，哪個機(jī)器學(xué)習(xí)算法不需要歸一化處理

7. 兩個數(shù)組，求差集

8. 開放性問題：每個實體有不同屬性，現(xiàn)在有很多實體的各種屬性數(shù)據(jù)，如何判斷兩個實體是否是同一種東西

9. 寫程序?qū)崿F(xiàn)二分查找算法，給出遞歸和非遞歸實現(xiàn)，并分析算法的時間復(fù)雜度 10. 用C/C++實現(xiàn)單鏈表的反轉(zhuǎn)

11. Python讀取文件，寫代碼

12. Python計算：一個文件中有N行，每行一列的數(shù)的平均值，方差，寫代碼

13. C++求兩個一維數(shù)組的余弦相似度，寫代碼

14. SVM詳細(xì)過程，支持向量，幾何間隔概念，拉格朗日函數(shù)如何求取超平面，非線性分類

15. 海量數(shù)據(jù)中，求取出現(xiàn)次數(shù)最大的100個數(shù)

16. 字符串翻轉(zhuǎn)

17. 快速排序

18. KNN（分類與回歸）

19. 非遞歸的二叉前序遍歷 && 兩個字符串的復(fù)制

20. 一個概率題目：6個LED燈管，找整體旋轉(zhuǎn)180'后仍然是一個正常輸入的情況

21. 給一個情境，考察你對于機(jī)器學(xué)習(xí)算法的了解程度以及常用情景的了解

22.一個數(shù)組，如果存在兩個數(shù)之和等于第三個數(shù)，找出滿足這一條件的最大的三個數(shù)（設(shè)為x+y =c）

23.聚類和分類有什么區(qū)別？

24.快速排序，怎樣將二叉排序樹變成雙向鏈表，且效率最高，從棧里找最小的元素，且時間復(fù)雜度為常數(shù)級

25.神經(jīng)網(wǎng)絡(luò)，plsi的推導(dǎo)，還有float轉(zhuǎn)string，判斷一棵樹是否是另一棵的子樹。

26.SVM的優(yōu)化形式、推導(dǎo)SVM

27.在一個n*n的矩陣中填數(shù)的問題

28.鏈表存在環(huán)問題，環(huán)的第一個節(jié)點在哪里？

29.常見排序算法

30.用拉格朗日公式推導(dǎo)SVM kernel變換

31.數(shù)據(jù)結(jié)構(gòu)當(dāng)中的樹，都有哪些？

32.推薦系統(tǒng)

33.輸出一個循環(huán)矩陣

34.翻轉(zhuǎn)字符串

35.確定鏈表中環(huán)的起始位置

36.N個數(shù)找K大數(shù)

37.一個班60個人怎么保證有兩個人生日相同

38.問一個字符串怎么判斷是郵箱比如:vzcxn@sdf.gre

39.快排的空間復(fù)雜度

40.給10^10個64位數(shù),100M內(nèi)存的空間排序

41.main(argc,argv[])里面兩個參數(shù)什么意思

42.kmp算法

43.電梯問題

44.一個應(yīng)用題，考察hash算法

45.求最大字段和，用動態(tài)規(guī)劃和分治法兩個方法，時間復(fù)雜度怎么算

46.寫了一下二分查找算法的代碼

47.統(tǒng)計字符串中出現(xiàn)的字符個數(shù)，忽略大小寫，其中可能有其他字符

48.一個文件2G內(nèi)容是userid,username 一個文件3G內(nèi)容是username,userpassword 要求：輸出userid,userpassword 8核cpu 2G內(nèi)存

49.貝葉斯概率

50.尋找二叉樹的公共父節(jié)點

51.通過尋找兩條路徑，然后尋找最后一個公共節(jié)點

52.SVM核函數(shù)，合并兩個文件的問題

53.b+ b-樹、紅黑樹、要求寫出排序算法

54.判斷兩條鏈表是否交叉。

55.歸并排序，random指針的鏈表復(fù)制等

56.樹的廣度、深度遍歷，

57.L1和L2的區(qū)別

58.生成與判別模型

59.隱式馬爾科夫

60.SVM：中文分詞

61.關(guān)聯(lián)分析、aprior

62.各類算法優(yōu)缺點、模型調(diào)優(yōu)細(xì)節(jié)

63.特征提取的方法

64.穩(wěn)定與不穩(wěn)定排序

65.RBF核與高斯核的區(qū)別

66.Python實現(xiàn)LogReg

67.ROC與AUC

68.K-means起始點

69.深度學(xué)習(xí)和機(jī)器學(xué)習(xí)的區(qū)別、數(shù)據(jù)挖掘和人工智能的區(qū)別、測試集和訓(xùn)練集的區(qū)別，kmeans，F(xiàn)CM，SVM算法的具體流程、如何優(yōu)化kmeans算法

70. 二叉樹前序遍歷非遞歸實現(xiàn)

71. Deep CNN, Deep RNN, RBM的典型應(yīng)用與局限

72. 有哪些聚類方法？

73. 判斷一個鏈表是否存在環(huán)？

74. 正則化是怎么回事（L1和L2）

75. PCA

76. 學(xué)校食堂如何應(yīng)用數(shù)據(jù)挖掘的知識

77. 哪些模型容易過擬合，模型怎么選擇

78. 什么是模糊聚類，還有劃分聚類，層次聚類等

79. 最長上升子序列，兩個大小相同的有序數(shù)組找公共中位數(shù)

80. 并行計算、壓縮算法

81. SVD、LDA

82. naive bayes和logistic regression的區(qū)別

83. LDA的原理和推導(dǎo)

84. 做廣告點擊率預(yù)測，用哪些數(shù)據(jù)什么算法

85. 推薦系統(tǒng)的算法中最近鄰和矩陣分解各自適用場景

86. 用戶流失率預(yù)測怎么做

87. 一個游戲的設(shè)計過程中該收集什么數(shù)據(jù)

88. 如何從登陸日志中挖掘盡可能多的信息

89. 統(tǒng)計學(xué)習(xí)的核心步驟：模型、策略、算法，你應(yīng)當(dāng)對logistic、SVM、決策樹、KNN及各種聚類方法有深刻的理解。能夠隨手寫出這些算法的核心遞歸步的偽代碼以及他們優(yōu)化的函數(shù)表達(dá)式和對偶問題形式。

90. 梯度下降、牛頓法、各種隨機(jī)搜索算法（基因、蟻群等等）

91. CART（回歸樹用平方誤差最小化準(zhǔn)則，分類樹用基尼指數(shù)最小化準(zhǔn)則）

92. Logistics（推導(dǎo)）

93. GBDT（利用損失函數(shù)的負(fù)梯度在當(dāng)前模型的值作為回歸問題提升樹算法中的殘差的近似值，擬合一個回歸樹）

94. 隨機(jī)森林（Bagging+CART）

95. 機(jī)器學(xué)習(xí)十大算法

96. 傳統(tǒng)機(jī)器學(xué)習(xí)算法應(yīng)用場景

97. 機(jī)器學(xué)習(xí)和深度學(xué)習(xí)的區(qū)別和聯(lián)系

98. 簡述你最熟悉的機(jī)器學(xué)習(xí)算法的原理和應(yīng)用

99. 機(jī)器學(xué)習(xí)項目或課題研究

100. 機(jī)器學(xué)習(xí)領(lǐng)域的主要研究成果

參考答案整理

1. 見機(jī)器學(xué)習(xí)書籍正文

2. 樸素貝葉斯核心思想利用先驗概率得到后驗概率，并且最終由期望風(fēng)險最小化得出后驗概率最大化，從而輸出讓后驗概率最大化的值（具體概率與先驗概率由加入拉普拉斯平滑的極大似然估計而成的貝葉斯估計得到），特征必須相互獨立。

3. 方案一：分拆然后分布式，方案二：對應(yīng)每個數(shù)有三個狀態(tài)，01代表出現(xiàn)一次，統(tǒng)計10億以內(nèi)數(shù)據(jù)，然后看最終哪些是01狀態(tài)

4. 應(yīng)對非線性分類問題

5. bit 位操作

6. 量綱問題：歸一化有利于優(yōu)化迭代速度（梯度下降），提高精度（KNN）

7. 實操

8. 重寫equals方法，對類里面的對象進(jìn)行屬性比較

9. 實操

10. 實操：為了反轉(zhuǎn)這個單鏈表，我們先讓頭結(jié)點的next域指向結(jié)點2，再讓結(jié)點1的next域指向結(jié)點3，最后將結(jié)點2的next域指向結(jié)點1，就完成了第一次交換，順序就變成了Header-結(jié)點2-結(jié)點1-結(jié)點3-結(jié)點4-NULL，然后進(jìn)行相同的交換將結(jié)點3移動到結(jié)點2的前面，然后再將結(jié)點4移動到結(jié)點3的前面就完成了反轉(zhuǎn)，思路有了，就該寫代碼了：　每次都將原第一個結(jié)點之后的那個結(jié)點放在list后面

11.12.13.14. 實操

15. 處理海量數(shù)據(jù)問題，詳細(xì)見鏈接：

http://blog.csdn.net/flyqwang/article/details/7395866，分而治之/hash映射 + hash統(tǒng)計 + 堆/快速/歸并排序；雙層桶劃分Bloom filter/Bitmap；Trie樹/數(shù)據(jù)庫/倒排索引；外排序；分布式處理之Hadoop/Mapreduce

16. 實操：將原數(shù)組看成 ab，需要轉(zhuǎn)換成 ba，先單獨對子數(shù)組a進(jìn)行反轉(zhuǎn)得到a'b（a'表示a反轉(zhuǎn)后的結(jié)果），同理單獨反轉(zhuǎn)b，得到 a'b',最后將得到的 a'b' 一起進(jìn)行一次反轉(zhuǎn)可得（a'b'）',而這就是最終結(jié)果 ba了

17.18.實操

19. 實操：http://ocaicai./blog/1047397

22.先排序，然后遍歷數(shù)組，每次遍歷的元素求是否是前后兩個元的和，小于則左邊前進(jìn)，大于則右邊后退

23. 分類是事先定義好類別 ,類別數(shù)不變， K-均值聚類算法、K-中心點聚類算法、CLARANS、 BIRCH、CLIQUE、DBSCAN等

24. 實操：http://m.blog.csdn.net/blog/wkupaochuan/8912622，

25.實操，子樹問題分兩步：

找值相同的根結(jié)點（遍歷解決）
判斷兩結(jié)點是否包含（遞歸：值、左孩子、右孩子分別相同）

26.實操

27. http://www.docin.com/p-19876385.html

28. http://blog.csdn.net/kerryfish/article/details/24043099

29.30.實操

31. 二叉查找樹（二叉排序樹）、平衡二叉樹（AVL樹）、紅黑樹、B-樹、B+樹、字典樹（trie樹）、后綴樹、廣義后綴樹。詳見下面鏈接

http://www.cnblogs.com/dong008259/archive/2011/11/22/2255361.html

32.http://baike.baidu.com/linkurl=ECsYE4xe1gguMd3R5X4x5V7eQX54NkFp0PJ0FYbAvgJIFPDiaCdD_PuftDAYZTuzH0EuIobF1vDa2Vx2rj6Dda

33. 實操

34.見16，實操

35.見28

36. http://www.douban.com/note/275544555/

37. 1減去50個人生日不同的概率≈100%

38. 略

39. 空間復(fù)雜度：快排是O(n)歸并是O(2n).

40. http://blog.csdn.net/guyulongcs/article/details/7520467

41. args是Java命令行參數(shù)，我們在DOS中執(zhí)行Java程序的時候使用“java 文件名 args參數(shù)”。args這個數(shù)組可以接收到這些參數(shù)。當(dāng)然也可以在一個類中main方法中直接調(diào)用另一個類里的main方法，因為main方法都是static修飾的靜態(tài)方法，因此可以通過類名.main來調(diào)用，這時就可在調(diào)用處main方法中傳入String[]類型的字符串?dāng)?shù)組，達(dá)到調(diào)用的目的，也可不傳入?yún)?shù)。

42. http://www.cnblogs.com/goagent/archive/2013/05/16/3068442.html

43.http://www.cnblogs.com/BeyondAnyTime/archive/2012/06/06/2538764.html

44.http://www.qqstock.cn/content/13/0409/14/10384031_277138819.shtml

45. http://blog.csdn.net/wwj_748/article/details/8919838

46.47.實操

48. http://freewxy./blog/737576

49. http://book.51cto.com/art/201205/338050.htm

50. http://blog.csdn.net/zcsylj/article/details/6532787

51.52. 53.實操

54. http://m.blog.csdn.net/blog/yangmm2048/44924997

55.實操

56. http://driftcloudy./blog/782873