算法面经_控制算法面试题

作者：LancelotHolmes
链接：https://www.nowcoder.com/discuss/51529?type=0&order=4&pos=2&page=1
来源：牛客网

记录下渣硕的秋招经历，粗略估算大约海投了59家，真正面了9家左右吧，笔试大概也做了几十家吧，目前的情况是拿到了苏宁(准备拒)、好未来(已拒)、百度、腾讯的offer，另外饿了么面了二面，美图面了一面，迅雷10月有面试(已拒)，以上
滴滴

二面挂
第一面

开始求职的第一次面试，视频面试，原定的3点45到下午4点30多开始面，一面中规中矩，面试小哥没有为难我，主要是先自我介绍，然后问了一个Java语言的问题(抽象类与接口的区别、用过Map吗，说一下HashMap和TreeMap的底层实现的区别)，接着手写了道快排，讲解了一下就开始让我介绍参加过的京东的比赛(要求按照一定的框架讲，比如做了什么，觉得自己做的好的有说什么，有什么做的不够好的)，在介绍的过程中针对性的提了一些问题，可以说都是一些常考的问题，记录如下：

解释下过拟合
数据类别不均衡的处理方法
XGBoost相对于GBDT有什么不同
数据记录有多少？特征有多少？训练时间多久？
有什么想要问我的？ 
1
2
3
4
5

第二面

这一面倒是没有撕算法也没有问一些基础的问题，都是偏向实际应用的略开放的问题，记录如下：

我看你两个项目使用的方法类似，你觉得哪个做得更好一点？然后接着问为什么你觉得另外一个做得差一些，问题出在哪里？
我看你比赛里面用的都是树形模型，为什么不用其他的模型？
人工处理特征与使用模型自动生成一些特征各有什么优劣？
你提到你感觉一个比赛里比另一差的原因是特征这方面，但我看你写到构造了交叉特征，请问构造了哪些交叉特征？为什么还是差呢？(这里针对交叉特征的定义纠结了一段)
你实际运用XGBoost与LightGBM中感觉哪个更好一点，有什么在比赛中发现的区别？
是否还了解其他的一些常用的方法（这里开始没明白，后来询问面试官，举的例子是LR+XGBoost或者FM+XGBoost，于是我提了一下了解的用来做ctr预估的应用，但是感觉面试官并不满意）
你两次项目用的处理方法差不多，那么你后面一次是否有什么新的收获呢，还是说你只是重复的使用一套方法？
我的问题提的差不多了，请你讲一下我没有问到的你认为可以表现你自己亮点、优势的地方 
1
2
3
4
5
6
7
8

总体来说虽然第二面挂了，不过受益颇多，确实只是懂得一些基础知识恐怕还是不足以胜任公司的要求吧，顶多撑过一面，一来简历存在问题，二来实际应用中模型的区别掌握的不够，这刺激了我后面阅读算法库的文档并分析了gbdt的不同实现的真实区别
苏宁

offered

现场面
自己介绍项目
是否了解决策树，讲一下你的理解
三种决策树是如何处理缺失值的
决策树如何处理缺失值？(三个阶段：划分节点时–训练模型时–预测时)

在选择分裂属性的时候，训练样本存在缺失值，如何处理？假如你使用ID3算法，那么选择分类属性时，就要计算所有属性的熵增(信息增益，Gain)。假设10个样本，属性是a,b,c。在计算a属性熵时发现，第10个样本的a属性缺失，那么就把第10个样本去掉，前9个样本组成新的样本集，在新样本集上按正常方法计算a属性的熵增。然后结果乘0.9（新样本占raw样本的比例），就是a属性最终的熵。
分类属性选择完成，对训练样本分类，发现属性缺失怎么办？比如该节点是根据a属性划分，但是待分类样本a属性缺失，怎么办呢？假设a属性离散，有1,2两种取值，那么就把该样本分配到两个子节点中去，但是权重由1变为相应离散值个数占样本的比例。然后计算错误率的时候，注意，不是每个样本都是权重为1，存在分数。
训练完成，给测试集样本分类，有缺失值怎么办？这时候，就不能按比例分配了，因为你必须给该样本一个确定的label，而不是薛定谔的label。这时候根据投票来确定，或者填充缺失值。 
1
2
3

浣花紫溪
XGBoost里处理缺失值的方法

在xgboost里，在每个结点上都会将对应变量是缺失值的数据往左右分支各导流一次，然后计算两种导流方案对Objective的影响，最后认为对Objective降低更明显的方向（左或者右）就是缺失数据应该流向的方向，在预测时在这个结点上将同样变量有缺失值的数据都导向训练出来的方向。
例如，某个结点上的判断条件是 A>0 ，有些数据是A0，有些数据的A是缺失值。那么算法首先忽略带缺失值的数据，像正常情况下一样：

将前两种数据分别计算并导流到左子树与右子树，
然后将带缺失值的数据导向左子树，计算出这时候模型的Objective_L；
接着将带缺失值的数据导向右子树，计算出这时候模型的Objective_R；
最后比较Objective_L和Objective_R。
假设Objective_L更小，那么在预测时所有变量A是缺失值的数据在这个结点上都会被导向左边，当作A<=0处理。 
1
2
3
4
5

[TomHall]
[https://www.zhihu.com/question/34867991/answer/224122110]
随机森林处理缺失值的方法

RandomForest包里有两种补全缺失值的方法：

方法一（na.roughfix）简单粗暴，对于训练集,同一个class下的数据，如果是分类变量缺失，用众数补上，如果是连续型变量缺失，用中位数补。

方法二（rfImpute）这个方法计算量大，至于比方法一好坏？不好判断。先用na.roughfix补上缺失值，然后构建森林并计算proximity matrix，再回头看缺失值，如果是分类变量，则用没有缺失的观测实例的proximity中的权重进行投票。如果是连续型变量，则用proximity矩阵进行加权平均的方法补缺失值。然后迭代4-6次，这个补缺失值的思想和KNN有些类似。
1
2
3

补充【proximity matrix】：Proximity 用来衡量两个样本之间的相似性。原理就是如果两个样本落在树的同一个叶子节点的次数越多，则这两个样本的相似度越高。当一棵树生成后，让数据集通过这棵树，落在同一个叶子节点的”样本对(xi,敏感词roximity 值 P(i,j)加 1。所有的树生成之后，利用树的数量来归一化proximity matrix。

https://charleshm.github.io/2016/03/Random-Forest-Tricks/
https://stats.stackexchange.com/a/98967/152084 
1
2

样本类别不平衡会带来怎样的影响
讲一下auc 以及你们比赛中最后模型的auc得分
随机森林里使用的决策树是哪一种？ sklearn里实现的是CART的一种变体
如何筛选特征

你担任副班长，职业有哪些，和班长有哪些不同
担任班干部让你学到了什么
你的意向填的是上海，说明下原因
独生子女？
是否有女朋友？
班级成绩排名

有什么要问我的？
二面

据说是算法的负责人之类的来面
介绍项目
讲下三种集成方法的区别bagging,boosting,stacking
讲下如何处理缺失值
说下你的技术栈
以后想从事的具体方向
有什么问题要问的
美团点评

一面挂
第一面

自我介绍
项目部分

数据分析过程中的一些发现和最后是如何用到特征构建的？
冲动消费的占比
训练集的构造
官方评价指标的解释
类别不均问题-->类别不均的影响，欠采样前后auc得分的变化
说说构造了哪些特征？
模型调参，调整了哪些参数？
特征选择方面做了哪些措施？--feature importance,显示其中最重要的特征有哪些？ 
1
2
3
4
5
6
7
8

算法

寻找数组中出现次数超过一半的元素-->寻找数组中出现次数超过1/3的元素
股票的买入卖出时间，一次买入卖出-->k次买入卖出
笔试题，交叉改卷问题
寻找数组中的最长递增子序列，寻找最长长度-->输出最长递增子序列 
1
2
3
4

介绍了自己部门的主营业务以及接下来可能的面试流程安排

说实话美团挂的有点蹊跷，当然也可能是我想多了，因为面试官面完说感觉你答得不错，而且做的东西和部门研究也相符，后续可能会安排现场面，然后我就挂了(欢声笑语打GG?)，可能是投的广告部门hc满了或者有更适合的人了吧。
远景

一面挂
一面

远景
大数据 分布式，工业界的做法，比较前沿的技术是怎么做的，知识比较欠缺，当前从书籍，论文了解的较为陈旧
两个100亿数据集进行join 操作 考察开放思维能力，学习能力
入职后有什么打算
技术栈不符

Terosort

为什么比赛中xgboost 表现比rf要好，从数据的角度分析
仅使用pandas库进行分析是否有什么性能上的问题
是否了解java 并发
是否了解Scala
数据库了解吗

远景的话大概是需要能直接干活的人吧，上来我讲完项目就说感觉你比较熟悉，但和我们技术栈不太符合，然后就尬聊大数据
饿了么

二面等消息
一面

两道算法题 矩阵乘法，转制&字符串中最长的数字字符串
自我介绍，说常用开发工具
讲算法
问hor项目
Rf vs gbdt vs xgboost
讲讲svm ，假设分离超平面系数非常大怎么办
L1正则和l2正则区别
随机森林的随机性
异常值处理
是否有实习经验
是否用过hive
说说hashmap 底层实现，为什么查询快？
二面

讲算法
讲hor 项目
为什么你这个得分还不错，使用了什么trick
特征选择的方法
京东赛官方评价标准的解析以及是否采取对应措施
空值处理
如何处理过拟合
有什么要问的

面完二面说本来有3面boss面，然后boss出差了，后续可能给你安排电面，估计是被婉拒了吧
百度

offered
一面

实验室的研究方向是什么
用Python 写一个对文本文件的词频统计
翻转链表
画建最小堆的过程
先序遍历二叉树，非递归
讲讲随机森林的原理
比赛中用了多少棵树
异常值处理
有什么想问的

二面 约1小时
自我介绍
链表的第一个公共节点，优化
最大连续子数组和
选一个最熟悉的算法，模型讲一下
介绍一个项目

三面 约30+min
讲一下项目–针对细节提问
基本情况了解，包括技术栈、意向城市
选择工作考虑的因素
面过哪些公司
对百度的部门是否了解–开始介绍部门–需要记录意向部门
有什么想问的

百度的话应该是我运气好吧，问的不难，我也基本都答上来了，要说亮点的话可能是在二面让讲一个项目，吸取了滴滴的教训，我把gbdt从集成方法的区别到adaboost vs gbdt再到sk-learn的gbdt vs XGBoost vs. LightGBM都给他撸了一遍，从原始论文的区别到具体实现的区别，所以这里可能算是面试的一个关键点吧
腾讯

等最终结果

自我介绍
实验室做的是什么方向
主要问项目
项目目的
评价标准
自己负责那一块，讲一下
构建了什么特征
模型用了什么
模型实际应用中的比较，为什么一个比另一个好
讲下boosting 和bagging
类别不平衡怎么处理的
Rf 调参是怎么做的，这里指出树的棵树，层数可以通过样本数，特征数预估，而不是拍脑袋决定
京东表现不是很好，为什么，有没有想过原因
简历的缺陷：实验室的研究没有写出，面试官看重你研究生阶段独立完整地研究了什么东西
熟悉哪些算法，分类的和回归的
是否了解深度学习，是否了解卷积神经网络
推导lr
讲下l1,l2区别及原理细节
最近读过印象最深的书
来自哪里
意向城市
被批概率论基础不行，很多东西只记结论，过程有所跳跃，机器学习过分依赖工具，原理理解不透彻，比赛过于使用套路，缺乏自己的思考和创新

二面
自我介绍
实验室项目介绍 具体怎么做的，节点多少，数据量多少，进度如何等
比赛介绍
官方评价指标有点问题
Gbdt vs rf
构造了哪些特征，不同阶段
信息增益是怎么计算的
比赛得分不是很高，是否尝试过其他方法
是否考虑过用深度学习来做
后缀子串问题
banana 找最长子串，要求非后缀子串，但是内容与后缀子串一样

hr面
自我介绍
哪里人
对腾讯的了解
职业规划
最近看了什么书–计算广告–讲的是什么？–广告方面怎么做比较好
是否有其他同学来参加腾讯面试，或者说与你同样进了hr面试的同学(前提是他们本科好)比，你的优势在哪
参加比赛的收获
优点和缺点
参加的XX比赛是做什么的
研究生阶段成绩如何
薪资期望
选择工作时的考虑因素
目前有哪些offer，面过哪些公司
百度和腾讯都给你offer的话你选哪个，为什么
爱好是什么
喜欢看什么电影
喜欢听什么音乐
有没有谈过女朋友–为什么没有谈过？
有什么要问的
除了互联网公司还有其他公司比较有意愿

腾讯应该也是比较好运气吧，一面被招聘人员指了个错方向迟到一二十分钟被面试官压着问，后面每一面都感觉自己应该是挂了，结果反而一直被吊打到完成面试，相比较同实验室的阿里大佬来说，他是一路开挂，我是一路被吊打。
美图

一面(电面约40min)
自我介绍
介绍项目
如何处理缺失值
类别不平衡会带来哪些影响
挑一个熟悉的算法讲解
平时用什么语言开发
有什么问题要问的

美图8月内推的吧，过了一个月才面，而且是在被百度腾讯吊打一周后，已经快油尽灯枯了，感觉面的不好，估计是挂了吧
好未来

现场面

offered

一面
自我介绍
用什么语言开发
说下Java的重写和重载的区别
是否了解Java虚拟机
StringBuffer与StringBuilder的区别
常见排序算法时间复杂度为O(nlogn)的有哪些，最佳、最差时间复杂度分别是多少？
写快排
智力题，8个球，一个比其他的轻，用天平称出该球最少用几次，怎么称
项目提问
rf vs gbdt
实验室做了什么项目
手写数组旋转，要求不使用额外空间
简单聊下个人意向，手头offer、面试情况
手写计算树的深度，要求不使用递归
有什么要问的

二面
介绍比赛
类别不平衡有什么影响
欠采样会造成什么后果
写一下F值计算的公式
谈谈对auc的理解
手写算法，在旋转数组里寻找某个给定的元素，要求时间复杂度O(n)以下
有什么要问的

说实话，好未来是我面试状态最差的一场，一个没睡午睡，另一个就是在美图面试下午，就是已经油尽灯枯了，一面快排一开始写错，旋转数组没反应过来，好在后面一道算法写对了，但是也让我过了，运气使然吧。

小结一下我的一些个人的想法

1、简历上写的东西一定要掌握透彻，另外时间充裕的下一届同学们最好尽量充实自己的简历，一般对研究生而言实习>项目>比赛/论文>基础，当然不同公司侧重可能有差别，比如腾讯的话给人感觉很注重你的实验室项目、研究做了什么
2、要建立自己的优势、亮点，比如算法而言，一般考察基础会让你挑一个常见算法来讲，或者他会选一个你熟悉的算法让你讲；那么同样一个算法怎么讲的和别人不一样呢或者说显得你比较熟悉呢，其实去年有个大佬已经总结过，最好横向对比、纵向深入，可以参照我上面面百度的例子，自己至少深入掌握一个实际用过的吧，然后的话常见的LR、SVM等肯定是需要掌握的，包括推导和原理、差别、应用场景等等
3、心态放平，这比较难，但是个人觉得面试还是很看缘分的，经常和实验室小伙伴一起去面某家公司、交流会发现很多时候得看你和面试官投不投缘，此外把自己能做好的做好就行，每次面试都是一个学习的机会，可以帮你迅速纠错，当然碰到莫名其妙的面试官提的一些明显跟你方向不相关的问题，也不用往心里去，运气不好罢了，换下家(而且一般越是大厂面试官一般都还是根据你的简历来考察的，面试体验相对好)
4、讲项目的话要注意条理和层次，先简要介绍背景就是你这个是干什么的，然后最好在纸上慢慢的画给面试官看，这样思路会清晰一些，也可以避免错漏，然后梳理你项目的亮点，针对项目里的知识点深挖一下，引导面试官去问，然后抛出来；我同寝室的一大佬这个是真厉害，据说他把自己的项目往pad里一放，面试时直接打开pad，对着面试官咔咔的讲，唬的人一愣一愣的，所以他基本面一家拿一家。
5、补充一点，关于面经的，个人觉得针对不同公司提前做好面经的一个准备是很有必要的，我一般在准备某各个公司的面试头几天会针对该公司收集面经，针对其中的问题进行分类和答案搜集，而且是分阶段的，比如明天是一面我就着重准备一、二面的面经，因为有些公司的考察点不同，而且不同极端也有区别，比如百度的话前面两面可能算法、基础、项目居多，终面的话可能是项目、场景题、hr问题居多，这个时候我一般是根据当前阶段最可能考察的点排个序，然后根据自己薄弱的环节进行一个优先级的排序，在有限的时间尽量争取把自己准备到最佳状态 
1
2
3
4
5

以上大概是我秋招的一些记录了，最后运气很好拿到了比较满意的offer，开始也是看着实验室各种大佬早早结束秋招，一路走来，十分感谢实验室各位大佬还有师弟们的扶持，也感谢同寝室同班的小伙伴的相互鼓励，还有老爸、老姐的关怀，最后也感谢自己，在比较艰难的时候也没有放弃，希望每一个看到这里的小伙伴都能坚持到最后一刻，拿到心仪的offer~