求职指南【5】-算法工程师综合面试100问

AI研习图书馆，发现不一样的精彩世界

算法
面试

算法工程师面试知识点总结五

一、前言

算法工程师面试100问，问题搜集整理于网络，包括算法岗面试过程中可能会被问及的100个常见机器学习问题，如数据结构、基础算法、机器学习算法等。本次关于算法工程师面试中常见的100个问题，大多是各类网站的问题汇总，希望聪明伶俐的你能从中分析出一些端倪，文末附了部分问题的参考答案，精力和水平有限，仅供大家学习参考~

二、算法面试100问

1. kNN，朴素贝叶斯及SVM算法的优缺点

2. 朴素贝叶斯的核心思想，有没有考虑属性之间不是相互独立的情况

3. 10亿个整数，1G内存，O(n)算法，统计只出现一次的数

4. SVM非线性分类，核函数的作用

5. 海量数据排序

6. 项目中的数据是否会归一化处理，哪个机器学习算法不需要归一化处理

7. 两个数组，求差集

8. 开放性问题：每个实体有不同属性，现在有很多实体的各种属性数据，如何判断两个实体是否是同一种东西

9. 写程序实现二分查找算法，给出递归和非递归实现，并分析算法的时间复杂度 10. 用C/C++实现单链表的反转

11. Python读取文件，写代码

12. Python计算：一个文件中有N行，每行一列的数的平均值，方差，写代码

13. C++求两个一维数组的余弦相似度，写代码

14. SVM详细过程，支持向量，几何间隔概念，拉格朗日函数如何求取超平面，非线性分类

15. 海量数据中，求取出现次数最大的100个数

16. 字符串翻转

17. 快速排序

18. KNN（分类与回归）

19. 非递归的二叉前序遍历 && 两个字符串的复制

20. 一个概率题目：6个LED灯管，找整体旋转180'后仍然是一个正常输入的情况

21. 给一个情境，考察你对于机器学习算法的了解程度以及常用情景的了解

22.一个数组，如果存在两个数之和等于第三个数，找出满足这一条件的最大的三个数（设为x+y =c）

23.聚类和分类有什么区别？

24.快速排序，怎样将二叉排序树变成双向链表，且效率最高，从栈里找最小的元素，且时间复杂度为常数级

25.神经网络，plsi的推导，还有float转string，判断一棵树是否是另一棵的子树。

26.SVM的优化形式、推导SVM

27.在一个n*n的矩阵中填数的问题

28.链表存在环问题，环的第一个节点在哪里？

29.常见排序算法

30.用拉格朗日公式推导SVM kernel变换

31.数据结构当中的树，都有哪些？

32.推荐系统

33.输出一个循环矩阵

34.翻转字符串

35.确定链表中环的起始位置

36.N个数找K大数

37.一个班60个人怎么保证有两个人生日相同

38.问一个字符串怎么判断是邮箱比如:[e-mail]

39.快排的空间复杂度

40.给10^10个64位数,100M内存的空间排序

41.main(argc,argv[])里面两个参数什么意思

42.kmp算法

43.电梯问题

44.一个应用题，考察hash算法

45.求最大字段和，用动态规划和分治法两个方法，时间复杂度怎么算

46.写了一下二分查找算法的代码

47.统计字符串中出现的字符个数，忽略大小写，其中可能有其他字符

48.一个文件2G内容是userid,username 一个文件3G内容是username,userpassword 要求：输出userid,userpassword 8核cpu 2G内存

49.贝叶斯概率

50.寻找二叉树的公共父节点

51.通过寻找两条路径，然后寻找最后一个公共节点

52.SVM核函数，合并两个文件的问题

53.b+ b-树、红黑树、要求写出排序算法

54.判断两条链表是否交叉。

55.归并排序，random指针的链表复制等

56.树的广度、深度遍历，

57.L1和L2的区别

58.生成与判别模型

59.隐式马尔科夫

60.SVM：中文分词

61.关联分析、aprior

62.各类算法优缺点、模型调优细节

63.特征提取的方法

64.稳定与不稳定排序

65.RBF核与高斯核的区别

66.Python实现LogReg

67.ROC与AUC

68.K-means起始点

69.深度学习和机器学习的区别、数据挖掘和人工智能的区别、测试集和训练集的区别，kmeans，FCM，SVM算法的具体流程、如何优化kmeans算法

70. 二叉树前序遍历非递归实现

71. Deep CNN, Deep RNN, RBM的典型应用与局限

72. 有哪些聚类方法？

73. 判断一个链表是否存在环？

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

75. PCA

76. 学校食堂如何应用数据挖掘的知识

77. 哪些模型容易过拟合，模型怎么选择

78. 什么是模糊聚类，还有划分聚类，层次聚类等

79. 最长上升子序列，两个大小相同的有序数组找公共中位数

80. 并行计算、压缩算法

81. SVD、LDA

82. naive bayes和logistic regression的区别

83. LDA的原理和推导

84. 做广告点击率预测，用哪些数据什么算法

85. 推荐系统的算法中最近邻和矩阵分解各自适用场景

86. 用户流失率预测怎么做

87. 一个游戏的设计过程中该收集什么数据

88. 如何从登陆日志中挖掘尽可能多的信息

89. 统计学习的核心步骤：模型、策略、算法，你应当对logistic、SVM、决策树、KNN及各种聚类方法有深刻的理解。能够随手写出这些算法的核心递归步的伪代码以及他们优化的函数表达式和对偶问题形式。

90. 梯度下降、牛顿法、各种随机搜索算法（基因、蚁群等等）

91. CART（回归树用平方误差最小化准则，分类树用基尼指数最小化准则）

92. Logistics（推导）

93. GBDT（利用损失函数的负梯度在当前模型的值作为回归问题提升树算法中的残差的近似值，拟合一个回归树）

94. 随机森林（Bagging+CART）

95. 机器学习十大算法

96. 传统机器学习算法应用场景

97. 机器学习和深度学习的区别和联系

98. 简述你最熟悉的机器学习算法的原理和应用

99. 机器学习项目或课题研究

100. 机器学习领域的主要研究成果

参考答案整理

1. 见机器学习书籍正文

2. 朴素贝叶斯核心思想利用先验概率得到后验概率，并且最终由期望风险最小化得出后验概率最大化，从而输出让后验概率最大化的值（具体概率与先验概率由加入拉普拉斯平滑的极大似然估计而成的贝叶斯估计得到），特征必须相互独立。

3. 方案一：分拆然后分布式，方案二：对应每个数有三个状态，01代表出现一次，统计10亿以内数据，然后看最终哪些是01状态

4. 应对非线性分类问题

5. bit 位操作

6. 量纲问题：归一化有利于优化迭代速度（梯度下降），提高精度（KNN）

7. 实操

8. 重写equals方法，对类里面的对象进行属性比较

9. 实操

10. 实操：为了反转这个单链表，我们先让头结点的next域指向结点2，再让结点1的next域指向结点3，最后将结点2的next域指向结点1，就完成了第一次交换，顺序就变成了Header-结点2-结点1-结点3-结点4-NULL，然后进行相同的交换将结点3移动到结点2的前面，然后再将结点4移动到结点3的前面就完成了反转，思路有了，就该写代码了：　每次都将原第一个结点之后的那个结点放在list后面

11.12.13.14. 实操

15. 处理海量数据问题，详细见链接：

http://blog.csdn.net/flyqwang/article/details/7395866，分而治之/hash映射 + hash统计 + 堆/快速/归并排序；双层桶划分Bloom filter/Bitmap；Trie树/数据库/倒排索引；外排序；分布式处理之Hadoop/Mapreduce

16. 实操：将原数组看成 ab，需要转换成 ba，先单独对子数组a进行反转得到a'b（a'表示a反转后的结果），同理单独反转b，得到 a'b',最后将得到的 a'b' 一起进行一次反转可得 （a'b'）',而这就是最终结果 ba了

17.18.实操

19. 实操：http://ocaicai.iteye.com/blog/1047397

22.先排序，然后遍历数组，每次遍历的元素求是否是前后两个元的和，小于则左边前进，大于则右边后退

23. 分类是事先定义好类别 ,类别数不变， K-均值聚类算法、K-中心点聚类算法、CLARANS、 BIRCH、CLIQUE、DBSCAN等

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

25.实操，子树问题分两步：

• 找值相同的根结点（遍历解决）

• 判断两结点是否包含（递归：值、左孩子、右孩子分别相同）

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. 空间复杂度：快排是O(n)归并是O(2n).

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

41. args是Java命令行参数，我们在DOS中执行Java程序的时候使用“java 文件名 args参数”。args这个数组可以接收到这些参数。当然也可以在一个类中main方法中直接调用另一个类里的main方法，因为main方法都是static修饰的静态方法，因此可以通过类名.main来调用，这时就可在调用处main方法中传入String[]类型的字符串数组，达到调用的目的，也可不传入参数。

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.360doc.com/content/13/0409/14/10384031_277138819.shtml

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

46.47.实操

48. http://freewxy.iteye.com/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.iteye.com/blog/782873

57.实操

58.生成是先P(X,Y)再P(Y|X),判别是P(Y|X)

59.实操

60.LDA提取特征，再用SVM做分类

61.62.63.实操

64.a1与a2值相等，排序完以后两者顺序仍然没变则是稳定排序，稳定排序有插入、冒泡、归并

65.一样

66. http://blog.csdn.net/zouxy09/article/details/20319673

67. http://www.tuicool.com/articles/q6zYrq

68. http://www.cnki.com.cn/Article/CJFDTotal-DNZS200832067.htm

69.实操

70.见19

71.实操

72. K-均值聚类算法、K-中心点聚类算法、CLARANS、 BIRCH、CLIQUE、DBSCAN等

73. http://m.blog.csdn.net/blog/lavor_zl/42784247

74-77. 实操

78. http://blog.csdn.net/xiahouzuoxin/article/details/7748823

79. http://blog.csdn.net/zcsylj/article/details/6802062

80. http://www.doc88.com/p-1621945750499.html

81. 实操

82. http://m.blog.csdn.net/blog/muye5/19409615

83. 实操

84. http://bbs.pinggu.org/thread-3182029-1-1.html

85. http://www.doc88.com/p-3961053026557.html

86. http://www.docin.com/p-1204742211.html

87. 略

88. http://www.docin.com/p-118297971.html

89-90. 实操

90-100. 略