搜广推校招面经七十五

字节推荐算法

一、SVM 原理与推导

1.1. 问题定义

给定训练集：
{ ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x n , y n ) } , x i ∈ R d , y i ∈ { − 1 , + 1 } \{(x_1, y_1), (x_2, y_2), ..., (x_n, y_n)\}, \quad x_i \in \mathbb{R}^d, \quad y_i \in \{-1, +1\} {(x1​,y1​),(x2​,y2​),...,(xn​,yn​)},xi​∈Rd,yi​∈{−1,+1}
目标是找到一个线性分类器：
$$f(x)=\text{sign}(w^{T}x+b)$$
使得所有样本被正确分类，且分类间隔最大。

1.2. 几何间隔与函数间隔

几何间隔定义为：
$${\gamma }_i=\frac{y_i(w^T{x}_i+b)}{\Vert w\Vert }$$

最大化几何间隔：
$$\max \gamma =\underset{i}{\min }{\gamma }_i$$

约定几何间隔为 1，转换为约束：
$$y_i(w^T{x}_i+b)\ge 1$$

1.3. 原始优化问题（线性可分）

将最大间隔问题转化为优化问题：
$$\begin{gathered} \underset{w,b}{\min }\frac{1}{2}\Vert w{\Vert }^2 \\ \text{subject to}{y}_i(w^T{x}_i+b)\ge 1,i=1,...,n \end{gathered}$$

1.4. 对偶问题推导（拉格朗日乘子法）

构造拉格朗日函数：
$$L(w,b,\alpha )=\frac{1}{2}\Vert w{\Vert }^2-\sum _{i=1}^n{\alpha }_i[y_i(w^T{x}_i+b)-1]$$

对 $w,b$ 求偏导并令其为 0：

• $\frac{\partial L}{\partial w}=0\Rightarrow w={\sum }_i{\alpha }_i{y}_i{x}_i$
• $\frac{\partial L}{\partial b}=0\Rightarrow {\sum }_i{\alpha }_i{y}_i=0$

代入得到对偶问题：
$$\begin{gathered} \underset{\alpha }{\max }\sum _{i=1}^n{\alpha }_i-\frac{1}{2}\sum _{i,j}{\alpha }_i{\alpha }_j{y}_i{y}_j{x}_i^T{x}_j \\ \text{subject to}\sum _{i=1}^n{\alpha }_i{y}_i=0,{\alpha }_i\ge 0 \end{gathered}$$

1.5. 支持向量与决策函数

求得 ${\alpha }_i$ 后，有些 ${\alpha }_i>0$ 的样本为支持向量（support vectors）。

最终分类器为：
$$f(x)=\text{sign}\left(\sum _{i\in SV}{\alpha }_i{y}_i{x}_i^{T}x+b\right)$$

1.6. 软间隔 SVM（线性不可分）

引入松弛变量 (\xi_i)，允许部分样本被错分：
${\min }_{w,b,\xi }\frac{1}{2}\Vert w{\Vert }^2+C{\sum }_{i=1}^n{\xi }_i$
$\text{subject to}{y}_i(w^T{x}_i+b)\ge 1-{\xi }_i,{\xi }_i\ge 0$
其中 $C$ 为惩罚因子，控制间隔与误差的权衡。

1.7. 核方法（非线性 SVM）

使用核函数将数据映射到高维空间，实现非线性可分的分类：
$$f(x)=\text{sign}\left(\sum _{i\in SV}{\alpha }_i{y}_i\kappa (x_i,x)+b\right)$$
常见核函数：

• 线性核：$\kappa (x_i,x_j)=x_i^T{x}_j$
• 多项式核：$(x_i^T{x}_j+c{)}^d$
• RBF 核（高斯核）：$\exp \left(-\frac{\Vert x_i-x_j{\Vert }^2}{2{\sigma }^2}\right)$

二、XGBoost 和 LightGBM 中的树构建与加速机制详解

2.1. 最优分裂节点的选择

2.1.1 分裂点选择目标

目标是最大化增益（Gain）：
$$\text{Gain}=\frac{1}{2}\left[\frac{G_L^2}{H_L+\lambda }+\frac{G_R^2}{H_R+\lambda }-\frac{(G_L+G_R{)}^2}{H_L+H_R+\lambda }\right]-\gamma$$
其中：

• $G_L,H_L$：左子树的梯度和 Hessian
• $G_R,H_R$：右子树的梯度和 Hessian
• $\lambda$：正则项
• $\gamma$：分裂代价

遍历每一个特征的候选划分点，计算 Gain，选择最大 Gain 的分裂点。

2.2. 加速技巧对比

2.2.1. 预排序（Pre-sorted）机制（XGBoost 早期）

原理（排序耗时，缓存效率差）：

• 每个特征提前对样本排序（一次性预处理）。
• 每次分裂时只需线性扫一遍候选点，计算增益。

2.2.2. 直方图优化（Histogram-based）（LGB）

原理：

• 将连续特征离散为有限数量的 bins（桶）。
• 在每个 bin 上统计梯度和 Hessian 累加值。
• 枚举 bins 而不是每个样本，提高效率。
• XGBoost 中的 tree_method=hist
• LightGBM 默认使用 histogram 构建

2.3. 缺失值处理

(1)训练时的处理方式：

1. XGBoost 的做法：

• 在每个特征分裂时，尝试将缺失值分到左或右子树两种情况，计算哪种情况下 Gain 更高。
• 将缺失值统一分到“默认方向”。

2. LightGBM 的做法：

• 将缺失值看成一个独立的 bin，参与增益比较。
• 根据缺失值所在 bin 的增益选择其应去的方向。

(2)预测时的处理：

• XGB：根据训练中学到的“缺失值默认方向”将缺失样本分配下去。所以预测时无需补全缺失值。
• LGB：仍然看作独立的bin

三、有了解过设计模式吗？

设计模式大致分为 三大类，共23 种经典模式

3.1. 创建型模式（Creational Patterns）- 解决“对象如何创建”的问题

3.2. 结构型模式（Structural Patterns）- 解决“类或对象如何组合”的问题

3.3. 行为型模式（Behavioral Patterns）- 解决“对象间如何通信、如何协作”的问题

四、解释装饰器模式（Decorator Pattern）

装饰器模式是一种结构型设计模式，允许在不改变原有类结构的情况下，动态地给对象添加功能。它通过将原始对象包装在装饰器对象中，达到扩展功能的目的。

本质：使用“对象包装”替代“类继承”来扩展功能。

4.1. 实际中的应用

五、46. 全排列

• 代码：
  按照答案每个位置该选的位置。

class Solution:
    def permute(self, nums):
        n = len(nums)
        ans = []
        path = [0] * n  # 所有的排列长度都是一样的
        def dfs(i, s):  # 从答案的角度，第i个位置该从剩余s中选择哪一个
            if i == n:
                ans.append(path.copy())
                return
            for x in s:
                path[i] = x
                dfs(i+1, s-{x})
        dfs(0, set(nums))
        return ans