文末彩蛋：七月在线干货组最新升级的《名企AI面试100题》免费送！

问题1 ：讲一下xgb与lgb的特点与区别

xgboost采用的是level-wise的分裂策略，而lightGBM采用了leaf-wise的策略，区别是xgboost对每一层所有节点做无差别分裂，可能有些节点的增益非常小，对结果影响不大，但是xgboost也进行了分裂，带来了不必要的开销。leaft-wise的做法是在当前所有叶子节点中选择分裂收益最大的节点进行分裂，如此递归进行，很明显leaf-wise这种做法容易过拟合，因为容易陷入比较高的深度中，因此需要对最大深度做限制，从而避免过拟合。

lightgbm使用了基于histogram的决策树算法，这一点不同与xgboost中的 exact 算法，histogram算法在内存和计算代价上都有不小优势。

内存：直方图算法的内存消耗为(#data* #features * 1Bytes)(因为对特征分桶后只需保存特征离散化之后的值)，而xgboost的exact算法内存消耗为：(2 * #data * #features* 4Bytes)，因为xgboost既要保存原始feature的值，也要保存这个值的顺序索引，这些值需要32位的浮点数来保存。

计算：预排序算法在选择好分裂特征计算分裂收益时需要遍历所有样本的特征值，时间为(#data),而直方图算法只需要遍历桶就行了，时间为(#bin)

问题2 ：讲一下xgb的二阶泰勒展开对于GBDT有什么优势

xgboost是在MSE基础上推导出来的，在MSE的情况下，xgboost的目标函数展开就是一阶项+二阶项的形式，而其他类似log loss这样的目标函数不能表示成这种形式。为了后续推导的统一，所以将目标函数进行二阶泰勒展开，就可以直接自定义损失函数了，只要损失函数是二阶可导的即可，增强了模型的扩展性。

二阶信息能够让梯度收敛的更快。一阶信息描述梯度变化方向，二阶信息可以描述梯度变化方向是如何变化的。

问题3 ：算法题：字母a-z对应数字1-26，给定一个数字序列， 求所有可能的解码总数，例如 1261 对应解码为 1 2 6 1 ， 12 6 1， 1 26 1总共为3种方式

这其实是一道字符串类的动态规划题，不难发现对于字符串s的某个位置i而言，我们只关心「位置i自己能否形成独立item」和「位置i能够与上一位置（i-1）能否形成item」，而不关心i-1之前的位置。

有了以上分析，我们可以从前往后处理字符串s，使用一个数组记录以字符串 s 的每一位作为结尾的解码方案数。即定义间为考虑前i个字符的解码方案数。对于字符串s 的任意位置i而言，其存在三种情况:

1. 只能由位置i的单独作为一个item，设为 a，转移的前提是| a的数值范围为[1,9]，转移逻辑为f=fi一 1]。
2. 只能由位置i的与前一位置（i-1）共同作为一个item，设为 b，转移的前提是 b的数值范围为[10,26]，转移逻辑为f[间=f处一 2]。
3. 位置i既能作为独立item也能与上一位置形成 item，转移逻辑为f[=f[i-1]+f(i-2]。

因此，我们有如下转移方程:

其他细节︰由于题目存在前导零，而前导零属于无效item。可以进行特判，但个人习惯往字符串头部追加空格作为哨兵，追加空格既可以避免讨论前导零，也能使下标从1开始，简化f[i-1]等负数下标的判断。

代码如下:

问题4 ：介绍xgboost和gbdt的区别

传统的GBDT以CART树作为基学习器，XGBoost还支持线性分类器，这个时候XGBoost相当于L1和L2正则化的逻辑斯蒂回归(分类)或者线性回归(回归);

传统的GBDT在优化的时候只用