1125招银2面

1、L1 L2正则化的区别
2、xgboost相比gdbt有什么区别
3、二叉搜索树的缺点：可能极度不平衡退化成链表，从而查找元素的时间复杂度变为O(n)

• 延申：从二叉搜索树到二叉查找树到红黑树
• 二叉查找树：保证左右子树的高度差不超过1，当新插入的节点破坏这个规则时通过左旋右旋来调整高度：动画演示
• 红黑树：具有二叉查找树的特点，与平衡树不同的是，红黑树在插入、删除等操作，不会像平衡树那样，频繁着破坏红黑树的规则，所以不需要频繁着调整：红黑树特点
  • 根节点是黑色的
  • 每个红色节点的两个子节点都是黑色。
  • 从每个叶子到根的所有路径上不能有两个连续的红色节点
  • 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点
  • 对于任意结点而言，其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点。

    当新插入的节点破坏上述规则时，采用变色、左旋、右旋来进行调整
    这些特点保证了红黑树自平衡，红黑树从根到叶子节点的最长路径不会超过最短路径的两倍，使一棵n个结点的红黑树始终保持了logn的高度，从而也就解释了上面所说的“红黑树的查找、插入、删除的时间复杂度最坏为O(log n)”这一结论成立的原因。

4、如何在函数内部改动全局变量
5、怎样用两个栈构造队列
6、什么样的函数才可以用作激活函数：首先要非线性的，根据万能逼近定理，要求：非常数、有界、单调递增，并且连续，参考这篇

• 延申 ：什么样的函数是好的激活函数：可以有效遏制梯度消失或梯度爆炸的函数

7、SQL的优化
8、SQL索引有哪些类别
9、怎样计算二叉树的层数