算法工程师知识点大全 (正在更新…) - Mr_HHH 的博客 - CSDN 博客

下面内容为自己找工作的过程中，自己整理的知识点以及从别人面经中整理的知识点大全，对其中的大部分问题，我都会给出我认为最优答案的 csdn 链接 (ps: 本篇博客正在整理过程中，会不定期更新一些新的知识点的答案，希望可以帮到更多的同学！ 最新更新于 2019-4-19)

【1】在 github 上找到了一个 2018/2019 / 校招 / 春招 / 秋招 / 自然语言处理 (NLP)/ 深度学习 (Deep Learning)/ 机器学习 (Machine Learning)/C/C++/Python / 面试笔记链接，内容涉及机器学习，深度学习，算法，编程语言，面经，数学等，感觉灰常不错，特来分享：https://github.com/worksking/Interview_Notes-Chinese ，希望对你有帮助！

【2】今天又在 github 上发现了一个 2019 年秋招计算机类面经的项目，

https://github.com/zslomo/2019-Autumn-recruitment-experience ，截图如下：

【3】此外我再两外分享一个关于计算机基础知识的 github 主页：https://github.com/CyC2018/CS-Notes

机器学习

• Boost 算法
• CART（回归树用平方误差最小化准则，分类树用基尼指数最小化准则）
• GBDT 与随机森林比较。
• GBDT（利用损失函数的负梯度在当前模型的值作为回归问题提升树算法中的残差的近似值，拟合一个回归树）
• KKT 条件用哪些，完整描述
• KNN（分类与回归）
• L1 与 L2 的区别以及如何解决 L1 求导困难。
• L1 和 L2 函数。
• L1 和 L2 正则相关问题。
• L1 和 L2 正则项，它们间的比较
• L1 正则为什么可以把系数压缩成 0，坐标下降法的具体实现细节
• LR 为什么用 sigmoid 函数。这个函数有什么优点和缺点？为什么不用其他函数？
• LR 和 SVM 有什么区别，libsvm 和 liblinear 有什么区别。
• Logistics 与随机森林比较
• Logistics（推导）
• Logistic 回归的推导，怎么得到 objective function。
• SVM 与随机森林比较
• SVM 为什么要引入拉格朗日的优化方法。
• SVM 原问题和对偶问题关系？
• SVM 在哪个地方引入的核函数, 如果用高斯核可以升到多少维。
• SVM 怎么防止过拟合
• SVM 的目标函数。常用的核函数。
• SVM 的过程，讲了推导过程，可能表达不清晰，都是泪
• bagging、adaboost、boosting
• em 与 kmeans 的关系；
• k-means 的 k 怎么取等等
• k-means 算法初始点怎么选择？你的项目里面推荐算法是怎么实现的？
• kmeans 的原理，优缺点以及改进。
• k 折交叉验证中 k 取值多少有什么关系
• l2 惩罚项是怎么减小 Overfitting 的？l1，l2 等范数的通式是什么？他们之间的区别是什么？在什么场景下用什么范数？l1 在 0 处不可导，怎么处理？
• randomforest,GBDT
• rf, gbdt, xgboost 的区别。
• softmax 公式
• 为什么要做数据归一化？
• 主要问最优化方面的知识，梯度下降法的原理以及各个变种（批量梯度下降，随机梯度下降法，mini 梯度下降法），以及这几个方法会不会有局部最优问题，牛顿法原理和适用场景，有什么缺点，如何改进（拟牛顿法）
• 什么情况下一定会发生过拟合？
• 什么是贝叶斯估计
• 介绍 LR、RF、GBDT ，分析它们的优缺点，是否写过它们的分布式代码
• 介绍 SVD、SVD++ ？
• 会哪些机器学习算法？
• 信息熵公式 ？
• 假设面试官什么都不懂，详细解释 CNN 的原理；
• 决策树原理
• 决策树处理连续值的方法？
• 决策树如何防止过拟合 ？
• 决策树的损失函数？
• 决策树过拟合哪些方法，前后剪枝
• 分类模型可以做回归分析吗？反过来可以吗？
• 分类模型和回归模型的区别
• 判别模型，生成模型
• 各个模型的 Loss function，牛顿学习法、SGD 如何训练。
• 因为面我的总监是做 nlp 的, 所以讲了很多 rnn、lstm、还有 HMM 的东西。不算很熟，但是接触过，以前稍微看过一些相关论文，所以还是勉强能聊的。
• 在平面内有坐标已知的若干个点 P0…Pn，再给出一个点 P，找到离 P 点最近的点。
• 在模型的训练迭代中，怎么评估效果。
• 如何减少参数（权值共享、VGG 的感受野、GoogLeNet 的 inception）
• 如何防止过拟合（增加数据，减少模型复杂度 -> 正则化）
• 对于同分布的弱分类器，求分类器均值化之后的分布的均值跟方差。
• 对于机器学习你都学了哪些？讲一个印象深的。
• 常见分类模型（ svm，决策树，贝叶斯等）的优缺点，适用场景以及如何选型
• 归一化方式
• 手写 k-means 的伪代码。
• 手写 k-means 的伪代码和代码。（Code）
• 手撕 svm 硬软间隔对偶的推导
• 手撕逻辑回归（损失函数及更新方式推导）
• 接着写一下信息增益的公式。
• 推一下 bp 算法等等
• 改变随机森林的训练样本数据量，是否会影响到随机森林学习到的模型的复杂度。
• 数据挖掘各种算法，以及各种场景下的解决方案
• 是否了解 mutual infomation、chi-square、LR 前后向、树模型等特征选择方式。
• 是否了解线性加权、bagging、boosting、cascade 等模型融合方式
• 有哪些常见的分类器，简单介绍下原理
• 机器学习与深度学习的区别
• 机器学习基础（线性回归与逻辑回归区别等）
• 机器学习：几种树模型的原理和对比，朴素贝叶斯分类器原理以及公式，出现估计概率值为 0 怎么处理（拉普拉斯平滑），缺点； k-means 聚类的原理以及缺点及对应的改进；
• 梯度下降牛顿拟牛顿原理
• 梯度下降的优缺点。
• 深度学习和普通机器学习有什么不同？
• 深度学习有很大部分是 CNN，给他用通俗的语言解释下卷积的概念，解释下 CNN 中的优势及原因
• 激活函数的选择（sigmoid->ReLu->LReLU->PReLU）
• 然后 20 分钟内手写 k-means
• 牛顿法、随机梯度下降算法和直接梯度下降算法的区别？
• 牛顿法推导
• 特征选择的方法
• 由数据引申到数据不平衡怎么处理（10W 正例，1W 负例，牛客上有原题）
• 聊聊 SVM，这段说了好久，从基本的线性可分到不可分，相关升维，各种核函数，每个是如何实现升。以及出现了 XX 问题，分析是样本的原因还是其他原因。针对不同情况，采取什么解决方案较好。
• 自己实现过什么机器学习算法
• 解决过拟合的方法有哪些？
• 解释 word2vec 的原理以及哈夫曼树的改进。
• 解释一下过拟合和欠拟合，有哪些方法防止过拟合。
• 让我一步一步地构造决策树，怎么计算信息熵、信息增益、然后 C4.5 ID3 CART 的区别，还说了一下优缺点
• 详细讨论了样本采样和 bagging 的问题
• 说一下 Adaboost，权值更新公式。当弱分类器是 LR 时，每个样本的的权重是 w1，w2…, 写出最终的决策公式。
• 说了一下 bagging 跟 boosting。
• 说明 L1L2 正则的效果与为什么形成这种情况（L1 正则稀疏，L2 正则平滑，之后说明就是画图说明正则化）
• 过拟合的解决方法；
• 选个你熟悉的机器学习方法 ，着重介绍一下产生原因，推导公式，背后统计意义什么等等
• 逻辑回归估计参数时的目标函数，如果加上一个先验的服从高斯分布的假设，会是什么样。
• 逻辑回归估计参数时的目标函数
• 逻辑回归的值表示概率吗？
• 问了会不会 RNN,LSTM。
• 问了很多数据挖掘的基础知识，包括 SVM, 逻辑回归、EM、K-means 等，然后给我很多场景问我遇到这些情况我要怎么来处理数据，怎么进行建模等等，问得很细
• 随机梯度下降，标准梯度
• 随机森林和 GBDT 的区别？LR 的参数怎么求解？有没有最优解？
• 随机森林（Bagging+CART）
• 拟牛顿法
• 随机森林和 GDBT 的区别？

GBDT 和随机森林的相同点：

1、都是由多棵树组成

2、最终的结果都是由多棵树一起决定

GBDT 和随机森林的不同点：

1、组成随机森林的树可以是分类树，也可以是回归树；而 GBDT 只由回归树组成

2、组成随机森林的树可以并行生成；而 GBDT 只能是串行生成

3、对于最终的输出结果而言，随机森林采用多数投票等；而 GBDT 则是将所有结果累加起来，或者加权累加起来

4、随机森林对异常值不敏感，GBDT 对异常值非常敏感

5、随机森林对训练集一视同仁，GBDT 是基于权值的弱分类器的集成

6、随机森林是通过减少模型方差提高性能，GBDT 是通过减少模型偏差提高性能

\5. 随机森林怎么取最后的结果？

\6. 随机森林是怎样避免 ID3 算法信息增益的缺点的？

​ 答：首先说下信息增益的过程，决策树算法本质上就是要找出每一列的最佳划分以及不同列划分的先后顺序及排布。信息增益的缺点是比较偏向选择取值多的属性。而 gini 系数每次都是二分，所以跟属性多少没有关系。

\7. 为什么 deeplearning 能抑制梯度消失或者爆炸的问题？

答: 几个方面：一是激活函数不光是只用 sigmoid 函数，还有 ReLU 函数二是在参数并不是初始化的时候并不是随机选择的，而是在前面有自编码器做了特征特征器，这样避免了梯度下降法求解陷入局部最优解；三，深度学习一些手段，权值共享，卷积核，pooling 等都能抑制梯度消失问题；四，二次代价函数换成交叉熵损失函数或者选用 softmax + 对数似然代价函数的组合。

\8. 介绍下 GBDT?

​ GBDT 采用的是 boosting 的思想，先从初始训练集训练出一个基学习器，再根据基学习器的表现对训练样本分布进行调整，使得基学习器做错的训练样本在后续受到更多的关注，然后基于调整后的样本分布来训练下一个基学习器，最后将所有基学习器加权结合。GDBT 在传统的 boosting 的基础上，将以决策树为基函数的提升树拟合残差，利用损失函数的负梯度在当前模型的值作为残差的估计。 (注：GBDT 是 boost 模型的一种，但不是 adaboost,adaboost 也只是 boost 模型的一种，adaboost 和 GBDT 模型和参数更新方法都不一样)

\9. 决策树和 adaboost 的区别

\10. 卷积层为什么能抽取特征？ 激活函数的种类和特点？sigmoid 反正切都有梯度消失问题 relu 快，

\11. pooling 层的作用？ ：http://blog.csdn.net/jiejinquanil/article/details/50042791

12：什么是数据标准化，以及为什么要进行数据标准化？

答：一般来说，数据标准化是减去均值再除以标准差，如果我们不进行数据标准化，那些数值范围大的特征将在成本函数中加权更多（如果大的特征变化 1%，则该变化相当大，但对于较小的特征，这是非常不明显的），数据标准化使所有特征均等加权！

13：在神经网络中，为什么 ReLU 比 Sigmoid 更常用？

答：【1】第一个问题，为什么要引入非线性激活函数？

如果不用激励函数（其实相当于激励函数是 f(x) = x），在这种情况下你每一层输出都是上层输入的线性函数，很容易验证，无论你神经网络有多少层，输出都是输入的线性组合，与没有隐藏层效果相当，这种情况就是最原始的感知机（Perceptron）了。

正因为上面的原因，我们决定引入非线性函数作为激励函数，这样深层神经网络就有意义了（不再是输入的线性组合，可以逼近任意函数）。

【2】第二个问题，为什么要引入 Relu?

第一，采用 sigmoid 等函数，算激活函数时（指数运算），计算量大，反向传播求误差梯度时，求导涉及除法，计算量相对大，而采用 Relu 激活函数，整个过程的计算量节省很多。

第二，对于深层网络，sigmoid 函数反向传播时，很容易就会出现梯度消失的情况（在 sigmoid 接近饱和区时，变换太缓慢，导数趋于 0，这种情况会造成信息丢失，从而无法完成深层网络的训练。

第三，Relu 会使一部分神经元的输出为 0，这样就造成了网络的稀疏性，并且减少了参数的相互依存关系，缓解了过拟合问题的发生。

14：解释一下 PCA(Principal Component Analysis)

15：解释下降维，什么时候降维，以及使用它的好处？

1：降维的作用？

（1）降低时间的复杂度和空间复杂度

（2）节省了提取不必要特征的开销

（3）去掉数据集中夹杂的噪音

（4）较简单的模型在小数据集上有更强的鲁棒性

（5）当数据能有较少的特征进行解释，我们可以更好地解释数据，是的我们可以提取知识

（6）实现数据的可视化

2：降维的目的？

用来进行特征选择和特征提取。

①特征选择：选择重要的特征子集，删除其余特征；

②特征提取：由原始特征形成的较少的新特征。

在特征提取中，我们要找到 k 个新的维度的集合，这些维度是原来 k 个维度的组合，这个方法可以是监督的，也可以是非监督的，如 PCA 是非监督的，LDA 是监督的。

16：如何处理数据集中的缺失值？

答：你可以直接删掉缺失值，也可以使用一些新值来填充缺失值，在 pandas 中可以使用 isnull() 和 dropna() 方法帮助你发现缺失值所在的行和列并删掉，如果你想填充缺失值，你可能会需要使用 fillna() 函数。

17：解释下聚类算法？

18：你如何进行数据探索（EDA）?

19：Why do we use convolutions for images rather than just FC layers?

编程题

• 1~n 这 n 个数现在去掉两个，如何找到去掉的两个数。 假设去掉的两个数是 a 和 b，那么通过求和，平方和可以知道 a+b 和 a^2+b^2，然后解方程就行了。
• char a[4] = {1, 2, 3, 4}; char *b = a; b[0] = 100; 请问输出 a 的结果是什么？
• 一个 N*M 的矩阵，从左上走到右下最小需要（N+M）步走完，问一共有多少种走法。
• 一个严格递增的数组，将前缀取一部分放在后面，在修改后的数组上找到最小的数。(剑指 Offer 原题)
• 一个大写字符串如 ABABB（len<1000），代表游客进游乐场的顺序及从哪个入口进入，要求每个入口 (不多于 26 个入口) 从第一个游客直到该入口的最后一个游客，检票员都不能离开，问最少检票人数 K。
• 一个字符数组中，每个字符都出现了 3 次，只有一个出现了 2 次，如果快速找出这个出现 2 次的？
• 一个字符矩阵，只可能是 R,G,B 三种字符。判断是否满足某个条件。这个条件是每种符号连成一个长方体，三个长方体长宽一致, 且横着平行
• 一个广告，它有一个 id，一个上线时间，一个下线时间，现在我有很多这样的广告，如果现在给你一个时间，告诉我有多少个广告在这个时间在线的
• 一个数据流中，如何采样得到 100 个数，保证采样得到的 100 个数是随机的？
• 一个数组中某个数出现次数大于一半，最快找出该数。
• 一个数组只有一个数字是单独出现，其他出现了三次。
• 一个数组存着 1-1000 连续的整数，假如我取出其中一个数，怎么能快速找到（用类二分查找）
• 一个数组存着负数与正数，将正数放在前面，负数放在后面
• 一个运算序列只有 +、*、数字，计算运算序列的结果。（Code）
• 一堆 ip 地址区间，不会重叠，来一个新的 ip 地址，看它在不在，在哪个区间。
• 一维数组，swap 其中的几对数字（每个数字只属于一次 swap 操作），实现查找（与二分有关）；
• 一维有序数组，经过循环位移后，最小的数出现在数列中间，如果原数组严格递增或递减，如何找这个最小数；
• 一维有序数组，经过循环位移后，最小的数出现在数列中间，如果原数组严格递增，如何找这个最小数。
• 一维有序数组，经过循环位移后，最小的数出现在数列中间，如果原数组非严格递增或递减，如何找这个最小数；
• 一维有序数组，经过循环位移后，最小的数出现在数列中间，数组可能是递增、递减、递减后递增、递增后递减四种情况，递增递减都是非严格的，如果有转折点，返回转折点的值，否则返回 - 1；
• 一道题：给定一个整数数组，里面有两个数相同，其他数都是不同的，如何尽快找到这两个数（答，用 hash 表，O（N），有更好的方法么？）
• 一题是多位数用链表存储（ e.g. 123 用 1->2->3 存储），实现相加功能函数
• 不创建临时产量换两个数
• 两个同样大小有序数组求中位数，写代码
• 两个大整数相乘。（Code）
• 两棵树相加——对应位置两棵树都有值则相加，对应位置只有一棵树有值则取该值；
• 中序遍历二叉树，利用 O(1) 空间统计遍历的每个节点的层次。（Bug Free Code）
• 中缀表达式转逆波兰表达式，逆波兰表达式求值；
• 为分析用户行为，系统常需存储用户的一些 query ，但因 query 非常多，故系统不能全存，设系统每天只存 m 个 query ，现设计一个算法，对用户请求的 query 进行随机选择 m 个，请给一个方案，使得每个 query 被抽中的概率相等，并分析之，注意：不到最后一刻，并不知用户的总请求量。
• 二分查找
• 二分查找，查找 target，在区间 [start，end] 之间，如果有重复元素，返回最后一个下标，其他情况返回 - 1
• 二叉树前序递归遍历算法（手写代码）
• 二叉树的前中后遍历
• 二叉树的文件存储，也就是序列化。
• 二叉树遍历，描述下层序遍历。
• 二维数组，每行递增，每列递增，任意交换其中的两数，发现并恢复。
• 二维数组，每行递增，每列递增，实现查找。
• 二维数组，每行递增，每列递增，求第 k 大的数。
• 什么样的数据结构可以满足多次插入删除，取最小数，给出时间复杂度。
• 介绍二叉树前序遍历非递归遍历算法（手写代码）
• 介绍大顶堆和小顶堆
• 从一组数中找出和为 sum 的三个数（leetcode 原题，先 sort 再找，并且剪枝），写代码，四个数呢？说思路。
• 假设有个 M*N 的方格，从最左下方开始往最右上方走，每次只能往右或者往上，问有多少种走法，假设中间有若干个格子不能走，又有多少种走法。
• 允许两个元素交换一次的最大连续子序列和。
• 全排列
• 全排列。
• 冒泡排序 (手写代码)
• 写 find 函数，在目标串中匹配模式串（要考虑中文字符的情况）
• 写一个二叉树的非递归的后续遍历
• 写一个简单的正则匹配表达式 (将文本中的 123.4 匹配出来)
• 写个动态规划，最长公共子序列
• 判断一个字符串是否为另外一个字符串旋转之后的字符串
• 前 k 大的数
• 单链表的翻转
• 去掉连续的重复数字，输出新数组，例如：1，2，2，2，1，3，5——> 3，5。
• 去除字符串 S1 中的字符使得最终的字符串 S2 不包含’ab’和’c’。（Code）
• 合法括号匹配
• 在一个字符串中，找出最长的无重复字符的字串
• 在二叉树结点结构中加一个指针域，使其指向层次遍历的下一个结点，特别地，每一层的最后一个结点为空。（Code）
• 堆排序 (手写代码)
• 堆是怎么调整的。
• 复杂链表的复制。
• 如果给出一个二叉搜索树的后续能不能建立（可以，因为只要将遍历结果排序就可以得到中序结果）。
• 字符串反转（手写代码）
• 字符串移位，给出字符串 abc##dfg##gh，实现将所有 #移至字符串串头。输出 ####abcdfggh。
• 字符串转整数
• 字符串，给一个 url，求中间的 site
• 字符串，给一个 url，求中间的 site。
• 定义满足 $n=x^a+y^b$（$x，y，a，b$ 是非负整数）的 n 是神奇数。如 $4 = 2^0 + 3^1,17 = 2^3 + 3^2$。输入 l 和 r，请求出闭区间 $[l,r]$ 里，最长的一段不含有神奇数的连续区间长度。$x,y,l,r<=10^{18},x>=2,y>=2$，如 $3\ 5\ 10\ 22$，在 $[10,22]$ 区间内，$x=3,y=5$ 的条件下，区间内 [14] 是神奇数，所以最长的区间是 $[15,22]$ 长度为 $8$，如 $2，3，1，10$，在 $[1,10]$ 区间内，$x=2，y=3$ 的条件下，$2，3，4，5，7，9$ 都是神奇数，所以最长的区间只有长度 $1$。
• 实现栈，使得 添加、删除、max 操作的复杂度为 O(1)。
• 对于一个字符串，请设计一个算法，只在字符串的单词间做逆序调整，也就是说，字符串由一些由空格分隔的部分组成，你需要将这些部分逆序。给定一个原字符串 A 和它的长度，请返回逆序后的字符串。
• 对于一个字符串，请设计一个算法，将字符串的长度为 len 的前缀平移到字符串的最后。
• 寻找字符串中第一个只出现一次的字符；
• 将字符串连续重复出现的字符删到只剩一个，这个可以用双指针，时间复杂度 n，空间复杂度 1。
• 常用排序算法的时间和空间复杂度
• 平衡二叉树是什么
• 归并排序 (手写代码)
• 快速排序 (手写代码)
• 快速排序 + 二分查找
• 手写快排 (easy)
• 打印数组的组合数。
• 打印螺旋数组；
• 把一个 bst 转化成一个双向链表。
• 把一个字符串的大写字母放到字符串的后面，各个字符的相对位置不变，不能申请额外的空间。例如 AbcDeFGhi ->bceiADFG
• 排序二叉树转双向链表。（Code）
• 描述 Dijkstra 最短路径算法
• 插入排序 (手写代码)
• 数列中找第 k 大的数字（与快排或堆排序有关）
• 数据解压缩，3(a4(ab)) -> aababababaababababaabababab；
• 数组有只有一个数出现一次，其他数都出现三次，找出那个数。
• 旋转数组
• 最少时间复杂度求数组中第 k 大的数。（Code）
• 最短路径代码。
• 最长公共子串（动态规划有关）；
• 最长公共子序列
• 有一堆无向好友列表 1-2， 3-4, 2-3 之类的，问能不能把这些用户划分两组，组内都不互为好友。
• 有序数组寻找和为某数的一对数字；
• 正数数组，找三个数使积最小，问有多少种选择。
• 母鸡、公鸡和小鸡问题：公鸡五块一只，母鸡三块一只，小鸡一块三只，用 100 元买 100 只鸡的所有方法。
• 求 double 类型的二进制 1 的个数。
• 求二叉树最近公共祖先 (leetcode 原题)
• 求连续子数组最大乘积，还让考虑边界问题（最后问了：连乘有可能导致溢出，存不下了）
• 用一个队列，将每个二叉树的 root 先放入队列。
• 用数组实现队列，各操作的复杂度分析。
• 用速度不同的指针可以判断链表中是否有环，问两速度满足怎样的关系可以保证发现环。
• 直接插入排序写代码
• 看段代码，问输出是啥。(就是段求二进制中 1 的个数)
• 矩阵求最长连续递增的路径长度
• 矩阵求最长连续递增的路径长度。
• 第一题是链表倒数第 k 节点；第二题是二叉树打印路径，第三题是矩阵中将 0 元素所在行列全置 0 的最优空间解法
• 第二轮是写出一个算法输出二叉树的 s 序列，何为 s 序列，比如现在有个二叉树 1-2,3-4,5 6,7 这是一颗完全二叉树， S 序列输出就是按照 1237654 这个顺序输出，用两个栈就能实现比较简单。
• 算法题，也只记得一个了：存在一个数组，大小 98，里面的元素均为在 [1,100]，且无重复， 不申请额外空间的情况下，在时间复杂度为 O(N) 情况下，找出缺失的两个元素值。
• 给一个 n*n 的矩阵，矩阵中满足每行每列都是递增的，要查找矩阵是否存在某个数.(leetcode 原题)
• 给一个数组，只有一个元素出现了一次，其他都出现了两次，找出出现一次的数。
• 给一个数组，数组种存在一种数，它的左边都比它小，右边都比它大，找出所有这些数的位置。
• 给一个股票，n 天的价格，只能两次买入卖出，而且只能只能先卖再买，问最多赚多少钱？
• 给一个股票，n 天的价格，只能进行一次买入和卖出，问最多赚多少钱？
• 给一个股票，n 天的价格，可以买入卖出 k 次，而且只能只能先卖再买，问最多赚多少钱？
• 给一个股票，n 天的价格，可以无限次买入卖出，问最多赚多少钱？
• 给了一个链表，第 1 个结点标号为 1，把链表中标号在 M 到 N 区间的部分反转。
• 给你一个无重复的数组输出全排列。
• 给你一颗二叉树按层输出每一层输出后都换行
• 给出一个二维矩阵，从（0,0）出发走到右下角，只能向右或向下走，找到一条路径，是这条路径上的总和最大。
• 给出一段代码问代码作用（二进制数据 1 的个数）
• 给出一颗二叉树，两个叶节点，找到这两个叶节点互连通的一条最短路径。
• 给定一个数组，只有一个元素出现了一次，其他都出现了 3 次，找出出现一次的数。
• 给定一个数组，有两个元素出现了一次，其他都出现了两次，找出两个出现一次的数。
• 给定一个正整数向量，判断这个向量是否存在一个片段，使得反转这个片段后能够使该向量升序排列。如：[1, 2, 4, 3]，就可以通过反转 [4, 3] 使得向量变为[1, 2, 3, 4]。
• 给定二叉树的先序跟后序遍历，能不能将二叉树重建（不能，因为先序：父节点 - 左节点 - 右节点，后序：左节点 - 右节点 - 父节点，两者的拓扑序列是一样的，所以无法建立）
• 给定循环递增数组 $a=[7,8,9,1,2,3]$ 和一个值 $k=2$, 返回该值得再数组中的下标。
• 给定数组 A[]={1,4,7,…} 和一个数 T。求和为 T 的 A 中的数最少要几个。A 中的数可复用。 我写了个递归，面试官不建议使用，因为效率不高。但没有反对。
• 给定数组，寻找 next big（堆排序有关）；
• 给我一个数组［1，2，5，10，20，50，100］，可以从里面取若干个数，要求得出和为 100 的不同取法有多少？（说出思路）
• 统计数列中的逆序对（归并排序有关）；
• 编程题：实现求正整数平方根整数部分的函数（使用梯度下降）
• 翻转二叉树（Code）
• 若干个二叉树，如何按照层序遍历
• 设 rand （ s ， t ）返回 [s,t] 之间的随机小数，利用该函数在一个半径为 R 的圆内找随机 n 个点，并给出时间复杂度分析。
• 输入一个大长方形，长宽 ab，和一堆小长方形。选择两个小长方形，它能放进大长方形，而这个小长方形面积和最大。
• 输入两个正数数组，在两个数组分别选一个数，要求第一个数组选的数的下标小于第二个数组选的数的下标。使得两个数的乘积最大。
• 输出字符串中的所有重复子串，例如：abcab，输出: a, b, ab
• 连续子数组最大和
• 迷宫的深度搜索、广度搜索；
• 选取任意数据结构实现添加、删除、随机返回三个功能，分析复杂度。
• 选择排序 (手写代码)
• 链表上的快速排序。
• 长度为 N 的序列 Sequence=abc……Z，问有多少不同的二叉树形态中序遍历是这个。（Code）
• 问了一两个算法题，记不清了，只记得其中一个是：找数组中 2 个出现两次的数字，还有 3 个两次的数字
• 问了一个 1 的平方加到 100 的平方结果
• 非常经典的 0-1 背包问题
• 字符串移位，给出字符串 abc##dfg##gh，实现将所有 #移至字符串串头。输出 ####abcdfggh（个人认为可以用后向移位，减少移位次数）
• 给出一个二维矩阵，从（0,0）出发走到右下角，只能向右或向下走，找到一条路径，是这条路径上的总和最大。（个人认为使用动态规划或深度遍历）
• 给出一颗二叉树，两个叶节点，找到这两个叶节点互连通的一条最短路径。（个人认为主要是找两个叶节点的最近公共祖先）

智商题

100 张牌，每次只能抽一张，抽过的牌会丢掉，怎么选出最大的牌。

36 匹马，6 条跑道，选出最快 3 匹，最少赛多少场？

5 个海盗抢到了 100 颗宝石，每一颗都一样的大小和价值连城。他们决定：抽签决定自己的号码（1，2，3，4，5）。首先，由 1 号提出分配方案（你抽到 1 号），然后大家 5 人进行表决，当且仅当超过半数的人同意时，按照他的提案进行分配，否则将被扔入大海喂鲨鱼。如果 1 号死后，再由 2 号提出分配方案，依此类推。条件：每颗宝石都是一样的价值。海盗都想保命，尽量多得宝石，尽量多杀人。问题：你会提出怎样的分配方案才能够使自己的收益最大化？

一个人要过一座 80 米的桥，每走一米需要吃一颗豆子，他最多可以装 60 颗豆子，问最少需要吃多少颗豆子才能走完桥？证明一下为什么你给的答案是最少的？桥长 81 米呢？当桥长 n 米，最多装 m 颗的时候结果用公式怎么表示？

一个绳子烧完需要 1 个小时，假设所有绳子的材质都不一样，也不均匀，怎么取出 1 小时加 15 分钟。

把 1~9 这 9 个数填入九格宫里, 使每一横、竖、斜相等。

有 100 个黑球，100 个白球。两个桶，桶的容量无限，每个球都可以任意放在任何一个桶中，没有限制，请设计一种分配方法，使得白黑球分配到两个桶之后, 某个人从某个桶中取出的球是白球的概率最大化。（这个人去第一个桶取球的概率是 1/2, 第二个桶也是 1/2）

有 1 亿个货物，不能单个单个检测，只能通过两两对比来找出其中的次品，请设计一个算法来找出次品。

有 25 匹马，5 个跑道，一次只能比 5 匹马，得到跑得最快的前 3，至少需要比几次？

有 3 盏灯，房间外有 3 个开关，你只有 1 次机会进入房间，怎么判断哪个开关对应哪盏灯？

给一堆螺母和螺栓，它们可以一一对应，但是现在顺序乱了，只能用螺母和螺栓比较，将它们一一对应起来。

大数据

• 100 亿数字，怎么统计前 100 大的？
• 10 亿个 url，每个 url 大小小于 56B，要求去重，内存 4G。
• 1KW 句子算相似度（还是那套分块 + hash / 建索引，但是因为本人不是做这个的，文本处理根本说一片空白，所以就不误导大家了），之后就是一直围绕大数据的题目不断深化。
• Q1：给定一个 1T 的单词文件，文件中每一行为一个单词，单词无序且有重复，当前有 5 台计算机。请问如何统计词频？
• Q2：每台计算机需要计算 200G 左右的文件，内存无法存放 200G 内容，那么如何统计这些文件的词频？
• Q3：如何将 1T 的文件均匀地分机器统计配给 5 台机器，且每台完词频生成的文件只需要拼接起来即可（即每台机器统计的单词不出现在其他机器中）
• 一个大文件 A 和一个小文件 B，里面存出在的是单词，要求文件 B 中但不在文件 A 中的单词。然后大文件 A 是无法直接存到内存中的。
• 一道题目是如果有一个人注册一个 qq，如何保证这个 qq 号码和之前已存在的 qq 号码不重复呢？
• 扔硬币，连续出现两次正面即结束，问扔的次数期望
• 有 100W 个集合，每个集合中的 word 是同义词，同义词具有传递性， 比如集合 1 中有 word a, 集合 2 中也有 word a, 则集合 1，2 中所有词都是同义词，对这 100W 个集合进行归并，同义词都在一个集合当中。
• 有几个 G 的文本，每行记录了访问 ip 的 log ，如何快速统计 ip 出现次数最高的 10 个 ip，如果只用 linux 指令又该怎么解决；
• 海量数据的 topk 问题
• hadoop+spark+yarn 大数据处理【具体内容很多，若要详细了解需要花费很长时间】

计算机基础

1:Linux 下的一些指令，$$（进程 id），$?（上一条命令退出时状态），怎么查看进程，按照内存大小，CPU 占用排序等等。

2:Linux 的命令：pwd、ln、which

3:Linux 线程通信

4:hash 表是怎么实现的？有冲突的时候怎么处理？

5:linux 文件词频统计

6: 介绍一下 hash，怎么解决冲突。

7: 你说一下 hashmap 的原理

8: 内存泄露出现原因。

9: 悲观锁乐观锁

10: 把两个表按 id 合并怎么搞？

11: 数据库 transaction

12: 浅拷贝深拷贝

13: 第二题是两题 sql ，涉及 join,group by,max,min,sum,count 等操作的结合，以及同个题目多种写法。

14: 线程安全是什么意思？新线程什么情况下会影响原有线程？

答: 并发基础知识 — 线程安全性，参见 https://www.cnblogs.com/tcming/p/6711506.html

15: 网络基础 TCP 三次握手

答：参见 https://blog.csdn.net/qq_18425655/article/details/52163228

16: 计算机网络：描述他发一句 helloworld 到我这边显示，中间经历了哪些过程，我从应用层开始一层层往下分析答的，主要说 http 和 tcp，网络层和链路层有些忘，但主要的几个协议和子网划分什么的也答了，面试官比较满意

17: 词向量的推导，混合高斯，linux 硬链接，三次握手，linuxinode

18: 进程线程的区别

答：(1) 进程是具有一定功能的程序关于某个数据集合上的一次运行活动，进程是系统进行资源调度和分配的一个独立单位。

(2) 线程是进程的实体，是 CPU 调度和分派的基本单位，它是比进程更小的能独立运行的基本单位。

(3) 一个进程可以有多个线程，多个线程也可以并发执行

19：说一下在浏览器地址栏输入 url 之后的一系列过程？

答：参见 https://blog.csdn.net/lamiant/article/details/54947281

​ DNS 解析过程，参见 https://www.zhihu.com/question/23042131

​ ARP 解析过程，参见 https://blog.csdn.net/wswit/article/details/52578878

20：fork 过程，fork,vfork 以及 clone 的区别（从源码分析）？<腾讯面试>

21：僵尸进程，怎么避免僵尸进程？<腾讯面试>

参考博客：https://www.cnblogs.com/Anker/p/3271773.html

22：从汇编层解释一下引用？<腾讯面试>

23：中断的作用？<腾讯面试>

24：tcp 连接关闭过程，time-wait 的作用，如果此时系统中有很多 time-wait 连接，你该怎么做？

参考博客：https://blog.csdn.net/yusiguyuan/article/details/21445883

以及博客：https://segmentfault.com/a/1190000003509876

25：DDos 攻击原理？<腾讯面试>

26：数据库引擎？<腾讯面试>

27：数据库三个重要范式？<腾讯面试>

28：网络层，数据链路层，运输层的设备以及协议有哪些？<腾讯面试>

29：网络层，数据链路层，传输层的寻址方式分别是什么？<腾讯面试>

30：AVL 树，B + 树，红黑树?<腾讯面试>

31: 数据库索引，事务？<腾讯面试>

概率题

• 100 人坐飞机，第一个乘客在座位中随便选一个坐下，第 100 人正确坐到自己坐位的概率是？
• X 是一个以 p 的概率产生 1,1-p 的概率产生 0 的随机变量，利用 X 产生 1/2 概率是 0,1/2 概率是 1 的随机变量。
• X，Y 均服存于 [0,1] 的均匀分布，求 X+Y。
• 一个国家重男轻女，只要生了女孩就继续生，直到生出男孩为止，问这个国家的男女比例？
• 一个有 7 个格子的环，三种颜色染色，相邻不能颜色重复，问多少种方案
• 一个袋子里有很多种颜色的球，其中抽红球的概率为 1/4，现在有放回地抽 10 个球，其中 7 个球为红球的概率是多少？
• 一枚硬币，扔了一亿次都是正面朝上，再扔一次反面朝上的概率是多少？
• 一道概率题，54 张牌，平均分成三堆，大小王在同一堆的概率？
• 一道概率题，一个六位的密码，由 0~9 组成，问你正过来看和倒过来看密码是一样的概率。
• 一道组合数学题。10 盏灯，灭三盏，两头的必须亮着，不能灭掉相邻的两盏灯，问组合数？
• 三个硬币，分别是正正，反反，正反。随机抛一个硬币，结果是正面，问选的是那个硬币
• 个人玩游戏，100 个球，每次挑 5 个，如何保证必胜。52 张牌，四个人抽，黑桃 A 和红桃 A 同时在一个人手里的概率。
• 好像是问有 70% 的人喜欢玩游戏，30% 的人不喜欢玩游戏，现在推送的资源必须是 50% 游戏，50% 非游戏。问怎么分配比较合理。
• 有 n 个 elements 和 1 个 Compare(A, B) 函数，用 Compare 函数作为排序算法中的比较算子给 elements 排序。Compare 函数有 p 的可能比较错。排序完取 Top m 个元素，本来就在 Top m 并被正确分在 Top m 的元素个数是 x。问 x 的数学期望。
• 有两个随机数产生器，R1 以 0.7 的概率产生 1，以 0.3 的概率产生 0，而 R2 以 0.3 的概率产生 1，0.7 的概率产生 0. 问如何组合这两种产生器，使新得到的随机数产生器以 0.5 的概率产生 1，0.5 的概率产生 0。随机数产生器可复用。
• 有两枚硬币 A 和 B，A 正面的概率为 0.6，B 正面的概率为 0.5. 现在扔了一枚硬币显示为正面，问：该枚硬币是 A 的概率是多少？
• 概率题：有种癌症，早期的治愈率为 0.8，中期的治愈率为 0.5，晚期的治愈率为 0.2. 若早期没治好就会转为中期，中期没治好就会变成晚期。现在有一个人被诊断为癌症早期，然后被治愈了，问他被误诊为癌症的概率是多少？
• 给一个函数，返回 0 和 1，概率为 p 和 1-p，请你实现一个函数，使得返回 01 概率一样。
• 给定一个分类器 p，它有 0.5 的概率输出 1，0.5 的概率输出 0。Q1：如何生成一个分类器使该分类器输出 1 的概率为 0.25，输出 0 的概率为 0.75？Q2：如何生成一个分类器使该分类器输出 1 的概率为 0.3，输出 0 的概率为 0.7？
• 问了一个概率题 54 张牌，分成 6 份，每份 9 张牌，大小王在一起的概率

HR 常问问题

• 为什么不读博、对读博报以什么态度。
• 为什么选择百度，谷歌百度都给你 offer 你选哪个。
• 为什么选择跨专业学计算机？
• 为什么选择阿里
• 以后可能要学习很多新技术，你怎么看。
• 你平时喜欢做什么？看过哪些书？最近在看什么书？
• 你觉得最有挑战的项目是什么。
• 你觉得最难忘的事情是什么？
• 你认为你的优（缺）点是什么。
• 你还有什么想问的？
• 加班怎么看。
• 印象最深刻的事？
• 压力最大的情况是什么时候。
• 在面试过程中觉得自己那些当面有进步
• 场景分析题，有一个任务给你，要求一个月完成，但是以目前的能力一个月完成不了，现在你知道有一个同事擅长这部分工作，但是他有自己的活，帮助你就可能耽误他的进度，问你咋办。
• 大学令你觉得最不爽的事情是什么
• 如何学习的？
• 如何看待加班。
• 实习期间项目，在组内担任的角色，是否熟悉其他组员的工作。
• 家庭教育观念？
• 家里什么情况？独生子女？
• 将来的职业规划？
• 工作地点
• 工作地点的问题
• 平时有什么兴趣爱好。
• 我觉得我会先去专心钻研技术，到达一定的
• 最后问了一下我兴趣爱好
• 有什么问题问我。
• 有没其他 offer
• 有没有想过去创业公司
• 现在在哪里实习？实习主要做些什么？
• 简单介绍一下自己
• 聊聊 offer 情况，有什么考虑之类的。
• 聊聊实验室生活。
• 能不能来北京
• 自己有什么优点缺点？
• 自己本科生和研究生相比有哪些进步
• 要求用两个字评价大学生涯。
• 讲一下你觉得你突出的地方，有亮点的地方。
• 评价一下你自己的优点缺点？
• 详细介绍项目。
• 说下你的优缺点
• 说说你的经历。
• 说说你自己的性格。
• 说说研究生阶段最有成就的事，遇到问题具体怎么解决的。
• 请你说一下你对应聘该岗位的优势。
• 遇到的最大挫折是什么。
• 问你的职业规划，遇到挑战怎么处理，有没有之前和同事发生过较大分歧。

开放题

• 2016 年每个项目有个上线和下线时间段，统计每天在线的项目数量
• 一堆问题和答案的 pair，算它们的相关性
• 一面现场面，自我介绍加挑一个项目细讲，还有场景题，第一题是 QQ 添加好友按名称搜索时，怎么区别广告号，诈骗号；
• 为什么之前没有深度网络出现（数据量不够 + 机器性能）
• 为今日头条设计一个热门评论系统，支持实时更新。
• 从项目中在哪一方面体会最深。
• 假设一个文档，连续的 K 个词，认为是一个时间窗口，一个时间窗口的词有关系，如何得到所有的时间窗口。
• 假设你拥有一切搜索数据，问怎么在不同场景下进行推荐，具体场景忘了（核心点：共线性、语义相似度、主题聚类等等）
• 假设有 100W 个单词，如何存储（我答的是 trie 树，面试官问每个节点会有很多子节点，每个子节点是一个指针，占用 8 个字节，如何节省空间，我说不知道，面试官提示双数组 trie 树）
• 假设要对一场 nba 球赛进行自动解说，会遇到哪些困难，又该怎么解决呢？
• 做过哪些项目？项目中遇到哪些难点，你是怎样解决的？
• 关于集群调度的一些经验 trick 掌握多少；
• 分词时，为了提高效率，怎么存储词典？（键树）如何压缩存储？
• 在微信的场景下，如何判断用户的职业？开放问题
• 场景题如何鉴别淘宝上卖假货的商家，价格维度可以用什么策略等
• 如何做一个新闻推荐
• 如何在语料中寻找频繁出现的字串，分析复杂度。
• 如何用尽可能少的样本训练模型同时又保证模型的性能；
• 如何预测双十一支付宝的负载峰值。
• 对推荐算法的未来看法。
• 平面上有 n 个点，让你设计一个数据结构，能够返回这个这 n 个点中距离某特定点最近的一个点。一开始讲了下 kd 树，然而太复杂面试官不满意，就讲了一个类似 GeoHash 的方案。
• 建立一个数据结构，基于此写一段程序用于存储 sparse vector，同时编写一个函数实现两个 sparse vector 的相加运算
• 很多单词，如何计算单词之间的相似度（或者对单词进行分类）
• 怎么预测降雨量。
• 我只有一大批实体词， 如何对他们进行聚类（无监督聚类）， 如何找出这些词中， 哪些词之间有关系， 是强关系还是弱关系， 具体是什么关系，（如刘德华和朱丽倩 属于娱乐分类， 是强关系， 关系为夫妻）
• 拼车软件是如何定价的以及如何优化。
• 推荐算法（基于用户的协同过滤，基于内容的协同过滤）
• 推荐系统的冷启动问题如何解决
• 文本挖掘中，分词算法？如何选取特征？如何进行相似度计算，文本聚类结果如何评估？
• 无给定条件，预测蔬菜价格。
• 有 100W 个集合，每个集合中有一些词，对于每个集合，找出他是哪些集合的真子集。
• 有一堆已经分好的词，如何去发现新的词？
• 比赛相关问题提特征特征选择等
• 海量的 item 算文本相似度的优化方法；
• 特征工程经验。
• 用两分钟介绍自己的项目，创新点在哪里。
• 用户给三个 item（query），如何给出查询网页。
• 第三题是如何鉴别实施诈骗的 QQ 用户；
• 第二题是微信朋友圈内容的安全鉴别；
• 第四题是如何做反作弊，例如公众号的刷阅读量。
• 系统设计题，给一个 query，如何快速从 10 亿个 query 中找出和它最相似的 （面试官说可以对每个 query 找 1000 个最相似的，存起来，每天离线更新）
• 线性代数：特征线性依赖，出现冗余，会导致什么问题？
• 给一堆数据找找到最佳拟合的直线，数据有较多噪声
• 给你一个系统（面试官好像是无人车部门的），后台的逻辑已经实现了，但是前端加载很慢，怎么检测。
• 给你两个文件 a 和 b，大小大概 100M，两个文件每行一个整数，要求找到两个文件中相同的整数，存到文件 c 里，问我怎样尽快的完成这项工作？
• 给出一个算法实现如何确定快递邮件上的地址，要求从国家到省市到县到乡镇的一个识别，要求效率高（有陷阱，比如有的人把县写到市的前面，有人喜欢写地域名称的省略词比如安徽省写成安徽或者皖）。
• 给定淘宝上同类目同价格范围的两个商品 A 和 B，如何利用淘宝已有的用户、商品数据、搜索数据、评论数据、用户行为数据等所有能拿到的数据进行建模，判断 A 和 B 统计平均性价比高低。统计平均性价比的衡量标准是大量曝光，购买者多则高。
• 给很多单词，统计某个子串出现次数，我给的方法还是用 Trie，只不过一个单词要分成多个插入到 Trie 数中就行了。
• 给很多单词，要求统计出现某个前缀出现次数。
• 统计全球会弹钢琴的人数，我用机器学习的思路答的，面试官还比较满意
• 自己项目中有哪些可以迁移到其他领域的东西。
• 讲了讲自己在深度学习的认识，问的问题是几个具体场景的设计，包括怎么从海量数据中提取热点问题。
• 设计 LRU 系统
• 设计一个合理的电梯调度策略，调度两个电梯 ，考虑满足基本的接送需求，满足能耗最小，满足用户等待时间最短
• 设计一个系统可以实时统计任意 ip 在过去一个小时的访问量；
• 设计一个结构存取稀疏矩阵（面试官最后告诉我了一个极度压缩的存法，相同行或列存偏差，我当时没听懂，还不懂装懂，最后还是没记住）
• 设计实现一个 git diff
• 说一下最能代表你技术水平的项目吧？
• 项目：具体问了特征怎么做的。
• （难到我了，我想的方法不好，面试告诉我了他的想法，类似于一个进程调度问题，每一时刻只可能有一个用户按按钮，把这条指令接收，判断当前电梯能否满足，能满足就执行，不能满足则放入一个队列里，实际情况还要细化）

全文完

本文由 简悦 SimpRead 优化，用以提升阅读体验

使用了 全新的简悦词法分析引擎 beta，点击查看详细说明