机器学习算法面经---2018秋招

更新线-2017-09-12 22:37---------------------------------------------------------------------------

上周末收到了链家的offer。还是蛮开心的。毕竟是准备这几个月以来的第一个结果。

更新线-2017-08-29 14:06---------------------------------------------------------------------------

2017-08-10-阿里菜鸟-机器学习-内推-1面-电话

6、有一堆已经分好的词，如何去发现新的词？

面试官给的提示：用这个词和左右词的关系。互信息 新词的左右比较丰富，有的老词的左右也比较丰富。还要区分出新词和老词。

9、spark Executor memory 给16G  executor core 给2个。问每个core分配多少内存

9、撸代码。实现一个java迭代器

数据：

int[][] data = new int[][] {

null,

new int[] {1,2,3,4},

new int[] {},

null,

new int[] {5,6,7},

new int[] {8},

null,

};

要求：遍历是跳过NULL。依次遍历每个元素：1,2,3,4,5,6,7,8

hasNext里面不应该改变迭代器内部状态，hashNext只判断

next返回值，并且指向下一个有效元素。

P.S. 面试官很忙，在我写代码的时候。还在跟另一个***约时间~~~

求连续子数组最大乘积，还让考虑边界问题（最后问了：连乘有可能导致溢出，存不下了）

-----------------------------------------------------------------------------------------------------------

2017-08-15-拼多多-算法-内推1面-电话

1、自我介绍

2、介绍项目

3、项目延展题：电商搜索框，每天有500W的搜索query。针对新来的一个query，给出和它最相似的100个query。

如果用RNN分类模型表征，那么向量不应该用最后一层的分类特征。应该用倒数第二层的更纯的特征。

4、K-means聚类个数选择，做什么样的试验来确定K

5、两个4G的文件（每个文件可能有重复），里面全都是数字。现有内存1G，求这两个文件的交集。

2个4G的文件，分别hash成10个子文件，一个400M。

1、自我介绍

2、介绍项目

3、说了SVM

4、为什么要把原问题转换为对偶问题？

因为原问题是凸二次规划问题，转换为对偶问题更加高效。

5、为什么求解对偶问题更加高效？

我答了，因为只用求解alpha系数，而alpha系数只有支持向量才非0，其他全部为0.

6、alpha系数有多少个？

我答了：样本点的个数

7、避免过拟合的方法

答了：决策树剪枝、L2正则和L1正则

8、为什么L1正则可以实现参数稀疏，而L2正则不可以？

答了：L1正则因为是绝对值形式，很多系数被压缩为0,。而L2正则是很多系数被压迫到接近于0，而不是0

9、为什么L1很多系数可以被压缩为0，L2是被压缩至接近于0？

答了：图像上，L1正则是正方形，L2正则是圆形。

L1正则的往往取到正方形顶点，即有很多参数为0

10、问平时用啥语言比较多？

说了之前用java、scala多。现在用python较多。

11、问jvm 啥啥啥（没听清）。。。

答：不会

12、python...直接问你个开发中的实际问题吧，如果写的程序跑的非常慢，多方面分析这个问题？

答了： 1、检查程序是否有多层嵌套循环，优化

2、检查程序是否有很耗时的操作，看能否优化为多线程并行执行

13、SQL中inner join 和outer join的区别？

14、试图给他说说SPARK，结果被严词拒绝（开玩笑的）。。。说时间紧迫，还是他来问吧。。。

15、Kmeans中，现在给你n个样本点不在欧式空间中，无法度量距离。现在给了一个函数F，可以衡量任意两个样本点的相似度。请问Kmeans如何操作？

答：想了一会，比如K=4的聚类。

1、首先，随机去4个点，作为初始类簇中心。

2、计算所有样本点与这4个点的F相似度。根据相似程度，把所有样本点分到4个类中。

3、在这4个类中，计算每一个样本点 i 到该类其他样本点的相似度和Si。取Si最大的那个点作为这个类的中心。

4、重复2、3步骤，直到类中心不再变化或者循环次数达到目标。

来了之后先做1个小时的题，5道算法题

因为比较长，所以采用 A：面试官   B：本人

B 自我介绍

A 你自己学机器学习，怎么学的？

B 自己看书，周志华的西瓜书、机器学习实战。先找着撸代码，然后去深究里面的理论。

A西瓜书看到什么程度？

B刚开始看，看不太懂，然后就以机器学习实战为主，先照着撸代码，然后去西瓜书里深究里面的理论。

B我给您说说SVM吧，自学的时候留下很深的印象（试图抓住主动权~）

SVM是基于。。。说着手动起来写SVM的损失函数

A （打断）为什么样本点到决策面是 1/||w||

B 手推向量点到决策面的表达式（麻蛋，竟然一时紧张忘了。。。没推出来）

A 点到直线距离公式记得吧？

B 嗯嗯，又没写出来。只能说之前推过，现在一紧张忘了。。。

A 这个也无关紧要，继续

B 继续说SVM

A （打断）知道LR吧，知道LR和SVM有什么不同吗？

B 知道，首先这两个算法的分类思想不同，LR是基于概率推导的，SVM是基于最大化几何间隔的

A （打断）写一下，LR的损失函数

B 手写出来。其实这个sigmoid函数由那个什么族分布（真的忘了名字，其实是：指数族分布），加上二项分布导出来的。损失函数是由最大似然估计求出的。

A 怎么由最大似然估计导出的？推导一下

B 最大似然估计就是求让已知事件发生的概率最大的参数。

假设有5个样本，每一个的类别是yi，由LR计算出的概率是h(x)。那么每一个样本预测正确的概率为：

(H(x)^yi)*((1-h(x))^(1-yi)) ----

（刚开始一紧张，把h(x)和yi写反了）面试官说是这样吗？你这样全为0，我感觉你在背公式。。。你再看看

我一看，卧槽这竟然写错了。赶紧改过来，然后表明是自己紧张了。

概率连乘后，然后取对数就是LR的损失函数了。

A 为什么损失函数有个负号？

B 这是因为要应用梯度下降法，引入的。不加负号也可以，梯度上升法。这都是一样的。

A OK，继续，LR和SVM有什么区别？

B SVM决策面只由少量的支持向量决定，而LR的话是所有样本都会参与决策面的更新。

A 对，所以说SVM怎么样？

B SVM对于异常点不敏感，而LR敏感。SVM更加健壮，决策面不受非支持向量影响。

A OK

A 知道过拟合吧？

B 知道，在训练集表现好，在测试集表现一塌糊涂。举个例子就是：学生平时考试成绩非常棒，但一到实际应用就很烂。

A 说说常见的过拟合的解决办法

B 数据，样本不够，如果现在的训练集只是所有样本空间的一个小小的部分，那么这个模型的泛化能力就非常差（边画图，边说）

A 嗯嗯，还有呢

B 可以加正则项，L1，L2正则。L1还可以用来选择特征

A 为什么L1可以用来选择特征

B 因为L1的话会把某些不重要的特征压缩为0

A 为什么L1可以把某些特征压缩为0

B 因为（画图）L1约束是正方形的，经验损失最有可能和L1的正方形的顶点相交，L1比较有棱角。所以可以把某些特征压缩为0

A 还有什么过拟合的解决方法

B 神经网络中，dropout方法。就是每层网络的训练，随机的让一半神经元不工作。达到防止过拟合的目的

A 还有吗？

B 决策树中可以用剪枝操作。

B 决策树过拟合，可以用随机森林。。。

A 什么？？？现在一个决策树已经过拟合了，还要再以它为基准训练随机森林？

B 。。。对，你说的对。我想错了。。。

B 我就知道这些方法了。。。

A OK，挑一个项目给我说说吧

B 说项目（不记得中间有没有再提问了。。。）

B 要不我给您说说spark框架吧，之前还用的挺多。

A 嗯（看简历和笔试题中。。。）

B 开始说。。。说到三分之一

A 好了！ 你不必说了。（大手一挥~）我看你5道笔试题都没写思路，现在把第二题代码写出来

注： 第二题就是检测括号是否匹配

B 我写了啊。。。（给他翻到其中一个的背面）

A 哦，（迅速扫过代码，），为什要把字符压栈呢？不压栈也可以的。

B 是吗？{abc()}这样的也是合法的吗？

A 当然啊（看了一眼题。）

B 好吧，我本来也准备看到字符就丢到，不入栈。但担心这种情况不合法，就给入栈了。

A 嗯，第三题呢？

B 没思路，没写

A 给我说说第四题

第四题：10分钟内，恶意IP访问检测（10分钟内访问次数超过1024即为恶意访问）

B 这是10分钟动态检测的，需要时间刻度精确到秒吗？

A 不需要

B 把10分钟内的<ip,次数>存入hashmap, 再把key,value互换存入treemap。因为treemap是基于key有序的，升序。然后直接拿出来最后一个和1024比较。

A 怎么实现动态的检测，当前检测0-10分钟，那么第11分钟怎么办？

B 把0-10分钟的摘出来，从10分钟内的hashmap中减去，再把10-11分钟内的加上。

我知道这样实现起来，效率应该不高，但这一会我只想到了这个。。。

A 嗯，其实可以这样，把每分钟的分开存储，动态的向后移动，取这10个的总的数据就行。

甚至可以每分钟只存储TOP200的，然后10个分钟的汇总，取TOP1

B 嗯，明白了。

A 说说循环依赖这个怎么解决的？

第五题：系统有很多相互依赖的包，怎么检测循环依赖

B 把它当做一个链表。记录当前的名字在hashset中。如果某一次遍历的依赖名字存在于这个hashet中。就认为有循环依赖。

A 学过数据结构吧？学过图吧？给你一个有向图，怎么检测有环？

B 维护一个访问的数组，记录哪些点被访问过，从一点开始遍历，如果遍历的点被访问过，就说明有环

A 从哪个店开始遍历？

B 从入度为0的点开始遍历

A 如果有多个入度为0的点呢？

B 嗯。。。都要以它为入口开始遍历。

A show me the code!!!

（我内心是崩溃的。。。）

B 纠结了一会，又给他说了一遍思路。

A 嗯，好吧，我没有什么想问的了。你呢？

B 请问您说的这个图的这个应该怎么。。。算了，我还是下去自己看吧。。。我还是想知道怎么解决。。。

A 你说的对啊，就把思路给我讲了一下，和我的差不多。

B 贵公司这里机器学习、深度学习有什么应用场景呢？

1、自我介绍

2、之前写过spark？写过统计日志用户数？那手写一下统计用户数（scala手写）

3、项目中用到了聚类？手写一下Kmeans

4、一般工业界不这样用，用kd-tree加速

5、给你出道题写一下，一个文件每一行有3列（\t分隔），每个字符串是abcd，这种形式，中间有大写有小写。

现认为：abcDe 等于BcaDe （即：不区分大小写，无关顺序）

要求输出： 字符 空格 出现次数 空格 每一种字符（以|分隔）

实例输出： abcde 2 abcDe|BcaDe

6、记不得了。。。好像没了。。。

-----------------------------------------------------------------------------------------------------------

2017-09-07-美团点评-机器学习-2面-内推-电话

经过RNN，每一时刻的输出。。。扯完我现在想都想不通了。。。

数轴上从左到右有n各点a[0], a[1], ……,a[n -1]，给定一根长度为L的绳子，求绳子最多能覆盖其中的几个点。要求时间复杂度O(n)，空间复杂度O(1)

-----------------------------------------------------------------------------------------------------------

2017-09-11-美团点评-机器学习-3面-内推-电话

面试官是一个和蔼的秃顶大叔，估计是总监级别。问的问题就是有深度，考察解决问题能力

-----------------------------------------------------------------------------------------------------------

2017-09-11-搜狗-机器学习-1面-校招-现场

1、自我介绍

2、说项目

3、用RNN了，说一下原理

4、问RNN怎么训练的？

大概说了说，BPTT。这个不太懂

5、RNN的输入是什么呢？

有word2vec训练的词向量库，一个句子分词后，把词都换成对应的向量输入

6、继续说项目

7、项目用到聚类了？介绍一下

巴拉巴拉巴拉

8、说文本情感分类项目，文本向量用tf-idf这种有什么问题没有？

有，不能捕获到上下文之间的联系。以后尝试用doc2vec这种。

9、了解bagging和boosting吗？

巴拉巴拉

10、做题

1、全排列

2、数组第k大的数

3、数组左减右，求最大差

因为笔试做的比较烂，所以以为没有面试机会。于是去了现场企图霸面。结果小姐姐当场一查，居然我也在面试名单，是还没有通知。于是回去，愉快的等待第二天面试。

因为较长 A:面试官    B:本人

A你是上午最后一个，咱们可以多聊一会（内心是崩溃的。。。）

A（原本以为要套路的自我介绍。。。结果。。。）你用C++多吗？

B不多，用java、python较多

A那STL熟悉吗？

B不熟

A知道Trie树吗？

B不熟，一顿扯

A详细讲解Trie树。

A红黑树了解吗？（据说让搞红黑树就要挂，难道这里就是预兆？？？）

B说了说5个特性

A详细讲解红黑树、B树、2-3-4树。

B（一脸谦虚的认真听）

A来做道题

一副扑克牌，未拆封，是有序的排列。要给4个人发牌，要使发的每一张牌的概率相同。

即发第i次牌，发出10和发出2的概率要相等。

B想了想，问了问，说了说思路，谈论了一下。

A排序算法知道哪些

B巴拉巴拉

A快排了解吗？

B说了思想，说了如何划分集合。

A知道快排的非递归实现吗？

B不了解

A那写个mergeSort吧，规定要写代码的。

B一会就搞定了

A咱们问问机器学习吧

A随机森林了解吗？Bagging和boosting了解吗？

B介绍随机森林

A RF的话，如果有一个特征和标签特别强相关。选择划分特征时，如果不随机的从所用特征中随机取一些特征的话，那么每一次那个强相关特征都会被选取。那么每个数都会是一样的。这就是随机森林随机选取一些特征的作用，让某些树，不选这个强相关特征。

B搜嘎。。。

A知道为什么bagging吗？

B。。。

A bootstrap aggregating

B又介绍了boosting

A说说这个项目吧

B巴拉巴拉

A看你项目用了SVM，介绍一下

B巴拉巴拉（中间被打断）

A你们怎么过来说的都很像啊，你们都看什么书？

B。。。我看的周志华的西瓜书和李航的统计学习方法。。。

A继续

B。。。巴拉巴拉

A还用到了RNN，介绍一下