【秋招】腾讯_数据分析岗_面试题整理

1. 二叉树题目

略

2. 层序遍历算法题

    1）由顶向下逐层访问

    2）可以用队列存储树，每次打印根节点并将左右节点放进队列

（参考：https://www.cnblogs.com/masterlibin/p/5911298.html）

3. 图论中的最大团、连通分量，然后问图划分的算法

略

4. 如何判断社区活跃度（基于图），现在想着可能是根据连通分量吧

略。

5. 给定相邻两个节点的相似度，怎么计算该点到其它点的相似度

    1）把这个问题看成多维尺度分析问题（MDS），那么实际上就是已知点之间的距离，构造一个空间Z，使得这个空间内点之间的距离尽可能保持接近。点在新空间Z中的向量化就是点的表示，然后点到点的距离就可以。

（MDS求解参考：https://blog.csdn.net/u010705209/article/details/53518772?utm_source=itdadao&utm_medium=referral）

    2）其它：已知节点间距离，将节点embedding。这里我不太懂，希望大家有思路的可以指点下，谢啦

    3）上诉两个答案也可能是我没看懂题意，因为该题的上下文是做复杂网络相关的研究。那么可能是知道任意两个相邻节点的相似度，求非相邻节点的相似度。这里可以参考simRank算法，即两个点的邻域越相似（有很多相似邻居），那么两个点越相似。有点像pageRank，是一个迭代的定义。

（参考：https://blog.csdn.net/luo123n/article/details/50212207）

6. 给一堆学生的成绩，将相同学生的所有成绩求平均值并排序，让我用我熟悉的语言，我就用了python的字典+sorted，面试官说不准用sort，然后问会别的排序，我就说了冒泡排序，原理我说了，然后问我还知道其他排序，答堆排序（其实我之前这方面复习了很多），之后问我有没有实现过（这个问题简直就是我的死角，就是没实现过，所以才想找个实习练练啊）

    1）python直接pandas下groupby studentID sort

    2）实现排序算法

7. 问了我机器学习熟悉的算法，答svm，讲一下原理

    1）一种分类方法，找到一个分类的超平面，将正负例分离，并让分类间隔尽可能大

    2）过程：

        a. 线性svm：损失函数如下

        b. 对偶学习问题

        c. 核函数：为了实现非线性分类，可以将样本映射到高维平面，然后用超平面分割。为了减少高维平面计算内积的操作，可以用一些“偷吃步”的方法同时进行高维映射和内积计算，就是核函数。包括多项式核函数、高斯核函数和sigmoid核函数

        d. soft kernel

（参考林轩田《机器学习技法》，SVM这部分的推导讲得很清楚；或者参考https://blog.csdn.net/abcjennifer/article/details/7849812/）

    3）优点：

        a. 容易抓住特征和目标之间的非线性关系

        b. 避免陷入局部解，泛化能力强

        c. 可以解决小样本高维问题（如文本分类）

        d. 分类时只用到了支持向量，泛化能力强

    4）缺点：

        a. 训练时的计算复杂度高

        b. 核函数选择没有通用方案

        c. 对缺失数据敏感

8. c中struct的对齐，我这个真的没听过，面试官让我之后自己查

    为了提高存储器的访问效率，避免读一个成员数据访问多次存储器，操作系统对基本数据类型的合法地址做了限制，要求某种类型对象的地址必须是某个值K的整数倍（K=2或4或8）

    1）Windows给出的对齐要求是:任何K（K=2或4或8）字节的基本对象的地址都必须是K的整数倍

    2）Linux的对齐要求是：2字节类型的数据（如short）的起始地址必须是2的整数倍，而较大（int *,int double ,long）的数据类型的地址必须是4的整数倍

（参考：https://www.cnblogs.com/fengfenggirl/p/struct_align.html）

9. 机器学习被调数据分析了，因为做推荐的，所以面试一直在聊具体场景的推荐方法，其他方面知识没有怎么问

略。

10. 梯度下降和极大似然

    1）梯度下降：

        a. 是解决优化问题的一种方法，较适合于凸函数的优化，可以找到极值（极小值和极大值）

        b. 对于某个参数，计算损失函数对该参数的偏导，该偏导即为下降方向。然后参数沿着该方向更新一个步长（学习率）

    c. 迭代直到满足迭代次数或者参数不再变化

    d. 包括梯度下降、随机梯度下降、mini-batch梯度下降

    e. 只用到了一阶导信息，用牛顿法可以引入二阶导数信息

    f. 梯度下降有效性的证明：用泰勒展开看

（参考：https://www.zhihu.com/question/24258023 @杨涛 的回答）

    2）极大似然估计：

        a. 思想：事件概率A与一个参数θ有关，我们观察到一系列事件，那么此时θ的取值应该是能使P(A|θ)最大的那个值。

        b. 过程：

            (1)写出似然函数

            (2)我们求解的目标是使似然函数最大

            (3)因为是乘法问题，一般log化变成加法问题求解。即对要求的参数θ求偏导，令其为0

（参考：https://blog.csdn.net/zengxiantao1994/article/details/72787849）

11. 特征选择的方法

    1）过滤：计算特征与标签之间的卡方、互信息、相关系数（只能识别线性关系），过滤掉取值较低的特征。或者使用树模型建模，通过树模型的importance进行选择（包括包外样本检验平均不纯度、特征使用次数等方法）

    2）包裹：认为特征间的交叉也包含重要信息，因此计算特征子集的效果

    3）嵌入法：L1正则化可以将不重要的特征降到0、树模型抽取特征

    4）降维：PCA、LDA等

12. GBDT和xgboost，bagging和boosting

    12.1 GBDT

    1）首先介绍Adaboost Tree，是一种boosting的树集成方法。基本思路是依次训练多棵树，每棵树训练时对分错的样本进行加权。树模型中对样本的加权实际是对样本采样几率的加权，在进行有放回抽样时，分错的样本更有可能被抽到

    2）GBDT是Adaboost Tree的改进，每棵树都是CART（分类回归树），树在叶节点输出的是一个数值，分类误差就是真实值减去叶节点的输出值，得到残差。GBDT要做的就是使用梯度下降的方法减少分类误差值

    在GBDT的迭代中，假设我们前一轮迭代得到的强学习器是ft−1(x), 损失函数是L(y,ft−1(x)), 我们本轮迭代的目标是找到一个CART回归树模型的弱学习器ht(x)，让本轮的损失损失L(y,ft(x)=L(y,ft−1(x)+ht(x))最小。也就是说，本轮迭代找到决策树，要让样本的损失尽量变得更小。

    GBDT的思想可以用一个通俗的例子解释，假如有个人30岁，我们首先用20岁去拟合，发现损失有10岁，这时我们用6岁去拟合剩下的损失，发现差距还有4岁，第三轮我们用3岁拟合剩下的差距，差距就只有一岁了。如果我们的迭代轮数还没有完，可以继续迭代下面，每一轮迭代，拟合的岁数误差都会减小。

（参考：https://www.cnblogs.com/pinard/p/6140514.html）

    3）得到多棵树后，根据每颗树的分类误差进行加权投票

    12.2 xgboost

    xgb也是一种梯度提升树，是gbdt高效实现，差异是：

    1）gbdt优化时只用到了一阶导数信息，xgb对代价函数做了二阶泰勒展开。（为什么使用二阶泰勒展开？我这里认为是使精度更高收敛速度更快，参考李宏毅的《机器学习》课程，对损失函数使用泰勒一次展开是梯度下降，而进行更多次展开能有更高的精度。但感觉还不完全正确，比如为什么不三次四次，比如引进二次导会不会带来计算开销的增加，欢迎大家讨论指正。）

    2）xgb加入了正则项

    3）xgb运行完一次迭代后，会对叶子节点的权重乘上shrinkage（缩减）系数，削弱当前树的影响，让后面有更大的学习空间

    4）支持列抽样等特性

    5）支持并行：决策树中对特征值进行排序以选择分割点是耗时操作，xgb训练之前就先对数据进行排序，保存为block结构，后续迭代中重复用该结构，大大减少计算量。同时各个特征增益的计算也可以开多线程进行

    6）寻找最佳分割点时，实现了一种近似贪心法，同时优化了对稀疏数据、缺失值的处理，提高了算法效率

    7）剪枝：GBDT遇到负损失时回停止分裂，是贪心算法。xgb会分裂到指定最大深度，然后再剪枝

    12.3 bagging

    1）是一种自举聚合的方法，随机有放回地从样本内抽样构造分类器，然后多个分类器投票得到最终结果

    2）可以降低方差，用于减少过拟合

    3）常见的随机森林是bagging方法的应用

    4）是并行的

    5）最终投票一般是一个分类器一票

    12.4 boosting

    1）是一种将弱分类器组合起来形成强分类器的框架，串行结构，后一个分类器根据前一个分类器得到的信息进行重新训练，不断推进得到更好的模型

    2）常见的boost方法有：

        a. Adaboost：对每一次分类错误的样本进行加权，让下一个分类器更关心这些分错的样本

        b. gbdt：每一个分类器都是cart树，输出的是分为正类的score。真实值减去score得到残差，下一棵树对残差进行训练。通过这种方法不断缩小对真实值差距

    3）可以降低偏差，提高模型的表达能力，减少欠拟合

    4）常见的有Adaboost和GBDT等

    5）是串行的

    6）一般是按照每个分类器的分类正确率进行加权投票

13. 过拟合的解决办法

    1）增加数据

    2）正则项

    3）early stopping

    4）控制模型复杂度：

        a. dropout（我觉得类似于subfeature）

        b. 剪枝、控制树深

        c. 增大分割平面间隔

    5）bagging

    6）subsampe & subfeature

    7）特征选择、特征降维

    8）数据增强（加包含噪声的数据）

    9）ensemble

（参考林轩田的《机器学习技法》）

14. 50亿个url，找出指定的一个url

    50亿个的话是哈希查找，考虑到数量比较大会有冲突问题，那么可以用布隆过滤器。缺点还是会有误判，把不属于该集合的认为属于。

15. CNN和LSTM原理和应用场景介绍

    1）CNN原理：

        a. 在原始图片上滑动窗口，将取值乘以卷积核进行特征映射，然后作为神经网络的数据。卷积核实际上是利用了先验的知识，“图片中距离较近的像素才能提供信息，距离较远的像素关系不大”。通过卷积核对图片中的一些特征进行抽取，如垂直、水平等

        b. pooling：取窗口内的max或者avg，丢弃信息较少的数值

        c. padding：补全，避免图片越抽取越小

    2）CNN应用：

        a. 图片分类等与图片有关的问题（图像识别、图像标注、图像主题生成、物体标注、视频分类等）（利用CNN抽取图片特征的能力）

        b. 自然语言处理（实体抽取、关系抽取、问答系统、机器翻译）（将词用词向量表示，因此变成二维结构数据）

    3）LSTM原理：

        a. RNN（Recurrent Neural Network）能够把上一个时间的信息记忆，缺点是如果相隔太远联系就很弱了

        b. LSTM（Long-Short Term Memory）在RNN的神经元中加入了一些组件，控制长短期的记忆。组件包括：

            (1) 输入层门：将新的信息记录到细胞状态中

            (2) 输出层门：将前面的信息保存到隐藏层中

            (3) 忘记门：将细胞中的信息选择性遗忘（他今天有事，所以我。。。当处理到‘’我‘’的时候选择性的忘记前面的’他’，或者说减小这个词对后面词的作用。）

（参考：https://blog.csdn.net/Dark_Scope/article/details/47056361；https://blog.csdn.net/roslei/article/details/61912618）

    4）LSTM应用：

        a. 自然语言类：机器翻译、在线问答、情感分析

        b. 图片类：手写文字、图片内容理解

        c. 音频类：语音识别

16. 为什么正则化能处理过拟合

    1）惩罚了模型的复杂度，避免模型过度学习训练集，提高泛化能力

    2）剃刀原理：如果两个理论都能解释一件事情，那么较为简单的理论往往是正确的

    3）正则项降低了每一次系数w更新的步伐，使参数更小，模型更简单

    4）贝叶斯学派的观点，认为加入了先验分布（l1拉普拉斯分布，l2高斯分布），减少参数的选择空间

17. 腾讯视频和优酷的区别

略。

18. 几大常用检验方法与比较

    1）两样本均值：t检验（样本量少）、u检验（样本量大）

    2）多样本均值：F检验（方差齐性检验）、方差分析

    3）两样本事件发生频数是否关联：卡方检验、秩和检验（有序多组多分类）、二项分布检验

    4）序列自相关：DW检验、ADF检验

    5）面板数据检验：F检验、H检验

    6）相关性分析、回归分析这些算么？

19. KMP算法

    1）目标是做字符串匹配，将时间复杂度从O(m*n)降为O(m+n)

    2）思想：利用了目标字符串内部的重复性，使比较时实现最大的移动量

    3）方法：

        a. 计算next[i]：表示字符串第1至i-1个字符的子串中，前缀后缀最长重复个数

        b. 对比主串s和目标字符串ptr。当相等时，i和j都+1；当不相等时，j更新为next[j]。

（参考：https://www.zhihu.com/question/21923021 @逍遥行 的回答）

20. 哈夫曼编码

    1）一种编码方式，让出现次数越多的字符编码越短，从而压缩编码的长度

    2）过程：

        a. 建立一个加权树，出现次数越多的字符出现在越上层

        b. 左连接为0，右连接为1

        c. 到达字符的01组合记为该字符的编码

        d. 由于哈夫曼编码是前缀编码（如果没有一个编码是另一个编码的前缀，则称这样的编码为前缀编码。如0,101和100是前缀编码），因此可以唯一地还原

（参考：https://blog.csdn.net/xgf415/article/details/52628073，https://www.cnblogs.com/xidongyu/p/6031518.html）

21. 给出一个商业业务例子，这个例子中使用模型会比数据查询和简单的统计分析更有效果

    1）推荐算法

    2）异常值检测

    3）精准营销

    4）信贷发放

    ......

22. 了不了解mapreduce

略。

23. 数据库熟练程度

略。

24. 平时看什么书

略。

25. 偏差和方差

    1）偏差：预测值与真实值差异，偏差大表示欠拟合。然后引申到计算方式和解决方法

    2）方差：预测值与均值的波动，方差大表示过拟合。然后引申到计算方式和解决方法

26. 有一个类似抖音的app，请你设计推荐算法

    1）定义目标（评估函数）：点赞率、停留时间、下滑概率等

    2）数据：

        a. 用户属性

        b. 视频属性

        c. 用户-视频行为日志

    3）方法：

        a. 信息流产品的特征是内容更新快，因此如果采用协同过滤的话用基于人的协同过滤会比较合适

        b. 如果还是接受不了基于人的协同过滤的更新速度（比如说用户增长特别快），对于分类问题建立机器学习模型，输出的是用户对每个视频点击可能性的score，本质上还是一个ctr预估问题

        c. 特征包括：用户属性、视频属性、统计特征、时间特征、用户id-视频id交叉项、用户向量信息、视频向量信息（用SVD、word2vec、fm、基于图的随机游走都可以）、短期行为

        d. 注意1：降低训练成本，如先粗略计算用户对视频的响应概率，只取头部做召回。然后对召回的视频再做排序等

        e. 注意2：需要能在线学习，用户点击后能对视频进行快速重排序。因此需要支持在线学习的模型，如lr、摇臂老虎机框架等，树模型在这里可能就不适用了

        f. 注意3：冷启动问题

            (1)用户冷启动：用户进来时根据用户属性对热门的内容进行匹配，找到用户可能最感兴趣的内容

            (2)内容冷启动：这里首先要涉及到视频信息的标注，除了上传者信息、视频标题和标签，还需要一些视频理解的算法，为视频打标签。然后计算视频之间的相似程度，找到这一类视频的高响应用户，一定概率向其投放，统计点击率情况，判断是否进一步扩大投放量。

27. 一个线段上任意取两点，能组成三角形的概率

    1）设线段长度为1，三个子线段长度为x1,x2,x3

    2）根据三角形两边之和大于第三边，可得：

            a. x1+x2>x3

            b. x1-x2<x3

            c. x2-x1<x3

            d. x1+x2+x3=1

    3）将x3=1-x1-x2带入abc，然后用x1、x2为轴绘制，可以得到有效面积为1/8

28. 有uid，app名称，app类别，数据百亿级别，设计算法算出每个app类别只安装了一个app的uid总数。

    应该用map reduce吧，但我不会啊。准备写个sql，结果写了半天还是写不出。面试完走到楼下就想出来了，233

    1）小数据量的话直接查询：

        select count(*) as result from

        (select uid, category, count(app) as c from table

        group by category having c = 1) as t

        group by t.uid having count(category) = 类别数

    2）大数据量下（没用过hadoop不太清楚，望大家指正）

        a. 原始文件可以拼接为uid-app-categroy

        b. map阶段形成的<k,v>是<uid-category,1>

        c. reduce阶段统计key为“uid-category”的count数量

        d. 只保留count为1的数据

        e. 剩下的数据量直接统计uid出现次数=category类别数的数据

29. 有一个网页访问的数据，包含uid，ip地址，url，文章资料。设计算法预测用户性别

    1）分类问题用机器学习方法解（这里假设已经有部分用户的性别标签）

    2）想到的特征有：

        a. 文档主题词（top3）

  b. 文档标题词（按照标题词在文档中出现的频率，取top3）（参考：https://blog.csdn.net/u013382288/article/details/80385814）

        c. ip地址

        d. url中参数（如网页搜索中的query）

        e. 统计特征：访问数量、单页面平局访问时间、上网时间等

笔试题

1、对于过拟合有什么方法处理

    见上文。

2、冒泡排序

    1）时间复杂度O（n）到O（n²）

    2）稳定排序

3、排列组合

    略。

4、大数定律和切比雪夫不等式的式子

    方差越大，X落在区间外的概率越大，X的波动也就越大。

5、回归系数的计算

    略。

6、鞍点的Hessian矩阵是否正定

    半正定，含有0特征值。

7、快速排序的最佳状况

    O（nlogn）

8、对于svm，梯度消失怎么在图像上判定

    不懂。

9、超参不敏感

    见下文，有详细题目。

10、分层抽样的适用范围

    略。

11、贝叶斯公式

    略。

12、高数里的一些求导的知识

    略。

13、线性代数里的秩、克莱姆法则

    1）向量组中的秩，就是极大线性无关向量组中的向量个数

    2）我们可以认为一个矩阵的秩，是给矩阵按质量排序的依据。

    秩越高的矩阵内容越丰富，冗余信息越少。秩越低的矩阵废数据越多。

（知乎 @苗加加）

3）克莱姆法则是求解线性方程组的定理，详见：https://baike.baidu.com/item/%E5%85%8B%E8%8E%B1%E5%A7%86%E6%B3%95%E5%88%99/7211518?fr=aladdin；https://blog.csdn.net/yjf_victor/article/details/45065847

14、推导回归系数的过程

（参考：https://blog.csdn.net/marsjohn/article/details/54911788）

15、深度优先遍历

    1）图的深度优先遍历：

        a. 首先以一个未被访问过的顶点作为起始顶点，沿当前顶点的边走到未访问过的顶点；

        b. 当没有未访问过的顶点时，则回到上一个顶点，继续试探别的顶点，直到所有的顶点都被访问过

    2）二叉树的深度优先遍历：实际就是前序遍历

解答题：

1、解释机器学习中的偏差和方差，对不同的情况应该采取什么样的措施？

    见上文。

2、描述假设检验的过程

    1）设置原假设H0，备择假设H1（一般我们的研究假设是H1）

    2）选定检验方法

    3）计算观测到的数值分分布，如果实际观察发生的是小概率事件，并且超过显著性水平，那么认为可以排除原假设H0

3、如果微信有一个功能是用户的位置信息能够每隔1分钟上传一次数据库，那么怎么发挥它的作用？

略。

笔试题

1.深度学习，训练集误差不断变小，测试集误差变大，要怎么做（ACD）

A 数据增强 B 增加网络深度 C提前停止训练 D增加 dropout

2. 鞍点的Hessian矩阵是？

半正定。

3.快排的时间复杂度

O（nlogn）

4 哪个sigmoid函数梯度消失最快？是零点处导数最大的还是最小的？

零点处导数最大。

5. 5 7 0 9 2 3 1 4 做冒泡排序的交换次数？

16？

6. 哪种优化方法对超参数不敏感？（C）

SGD BGD Adadelta Momentum

1）SGD受到学习率α影响

2）BGD受到batch规模m影响

3）Adagrad的一大优势时可以避免手动调节学习率，比如设置初始的缺省学习率为0.01，然后就不管它，另其在学习的过程中自己变化。

为了避免削弱单调猛烈下降的减少学习率，Adadelta产生了1。Adadelta限制把历史梯度累积窗口限制到固定的尺寸w，而不是累加所有的梯度平方和

4）Momentum：也受到学习率α的影响