1.二叉树前、中、后、层次非递归写法
2.排序算法(尤其是快排)
3.100000个数中找出最大的k个数
算法：
1.模型的评价指标计算公式
精确率：判黑真正为黑的占判黑总数的比例
召回率：正确判黑的占黑样本总数的比例
ROC曲线：在各个阈值下模型以FPR为横坐标、TPR为纵坐标，画的曲线
AUC：ROC曲线线下面积
2.AUC指标详解
计算公式：ROC曲线的线下面积
概率解释：在正负样本中随机取一对正负样本，其中正样本得分大于负样本得分的概率
AUC是否受正负样本比例的影响？
AUC不受正负样本比例的影响，用正负采样过后的测试集和用不进行采样的测试集AUC基本不变
AUC和其他评价指标相比的优势在哪里？为什么？
改评价指标不受测试集正负样本比例的影响，相比于其他评估指标，例如准确率、召回率和F1值，负样本下采样相当于只将一部分真实的负例排除掉了，然而模型并不能准确地识别出这些负例，所以用下采样后的样本来评估会高估准确率；因为采样只对负样本采样，正样本都在，所以采样对召回率并没什么影响。这两者结合起来，最终导致高估F1值！
3.word2vec介绍，如何进行训练？有那两种区别是什么？大数据情况下那种更适合？
a.介绍
一种词向量的表达，能使词的表达具有一定的上下文信息，原始的word2vec是一个浅层神经网络，首先把全部词进行one-hot，那么每个词将对应着一个特征向量，
（1）.首先是一个线性的Embedding层。在word2vec进行训练的时候，将输入2k个词的词向量，通过一个共享的D*V（V是词典大小，D是Embebdding的向量维度）的矩阵C，映射为2k个分布式的词向量。C矩阵例存储了要学习的word2cev向量
（2）.忽略上下文的序列信息：输入所有的词向量都汇总到一个Embedding layer(加和取平均)
（3）.用softmax进行映射，得到这个词是各个词的概率
（4）.然后根据这个词本身的情况来进行更新
c.有那几种？区别是什么？
Cbow：每次用前后k个词词来预测中间的1个词 词向量更新n词，时间复杂度较低
Skip-gram：用1个词预测前后k个词 词向量更新kn词，时间复杂度较高 更适合数据较少的情况
d.大数据情况下更适合哪种？为什么？
更适合适用Cbow，因为效率较高
e.有哪几种优化方式？具体讲一下哈弗曼树方式如何进行训练和预测
分层softmax：
负采样：
f.局限性
（1）.只能考虑局部的词之间的关联性
（2）.没有考虑词之间的内在联系
g.实质
计算输入向量和输出向量的余弦相似度
4.SVM
1.公式推导
2.损失函数
hinge(折页损失函数)+正则
3.映射到的核函数空间有什么要求(核函数要求)？
过某非线性变换 φ( x) ，将输入空间映射到高维特征空间，在低维输入空间存在某个函数 K(x, x′) ，恰好等于在高维空间中这个内积，即K( x, x′) =<φ( x) ⋅φ( x′) > (这样的函数K被称作核函数)
4.点到向量距离公式推导
5..生成模型和判别模型
1.定义
生成模型：学习得到数据的联合分布P(x,y)，然后求联合分布。能够学习到数据的生成机制。
判别模型：学习的到概率的条件分布P(y|x)
2.区别
数据量和准确率：生成模型的数据量需求比较大，在数据量足够多的时一般生成模型效果较好，因为联合分布能够提供更多的有效信息；而判别模型需要的数据量较小，引起直接面向预测在小数据条件下一般效果比生成模型效果好
速度：生成模型收敛速度较快
隐变量情况：生成模型能够应付(高斯混合模型就是生成模型的隐变量形式)
3.常见的生成模型和判别模型
生成模型：隐马尔科夫链、朴素贝叶斯
判别模型：csrf
6.xgboost
XGBoost的损失函数是什么，节点划分准则是什么？
损失函数：
节点划分准则：
分类树：信息增益获信息增益比
回归树：最大均方误差
整体流程：
Xgboost和GBDT算法时间复杂度是多少？
针对每个特征，把属于该节点的训练样本根据该特征值升序排列，通过线性扫描的方式来决定该特征的最佳分裂点，并记录该特征的最大收益（采用最佳分裂点时的收益）
时间复杂度:O(nlogn d m)(n是样本个数，d是特征个数,m是树的深度)
xgboost是如何进行剪枝的？
xgboost采用后剪枝的方式进行剪枝，即 从顶到底建立所有可以建立的子树，再从底到顶反向进行剪枝，这样不容易陷入局部最优解。
xgboost和gbdt的区别：
1.xgboost是gbdt的工程化实现
2.xgboost加入了正则化信息
3.xgboost允许使用自定义的损失函数
4.xgboost损失函数加入了二阶导数信息，下降的更快更准
5.xgboost支持和随机森林一样的列抽样
6.xgboost支持并行化，但是并不是树与树之间的并行化，而是在最费时的特征排序截断进行并行化，将排序结果进行分桶保存，各个树生成时复用
7.xgboost基模型除了支持gbdt支持的CART树外还支持其他的基模型
7.样本不平衡问题处理办法
8.L1正则化和L2正则化
极大似然和最大熵