小红书：2022秋招提前批【RedStar】算法工程师 一面

• GNN 中 Transductive 和 Inductive 分别是什么

  Transductive 考虑的是静态的图结构，如 GCN、GAT 等经典模型都是 Transductive GNN，基于静态的图结构学习节点表示进行节点分类等下游任务；
  ​
  Inductive 考虑的是动态的图结构，经典模型如 GraphSAGE 则是在基本的学习训练后，使用采样+推理的方法得到新增加的节点特征，用于下游任务。

• LSTM 和 GRU 的区别

  GRU 可以被理解为 LSTM 的优化版，将 LSTM 中的 3 个门控优化为 1 个，提高了计算效率的同时也有着与 LSTM 相似的学习能力。

• 序列数据用 BN 还是 LN，为什么

  LN。

  NB 会对相同位置的数据的每一个维度进行缩放和平移，而 Batch 中的序列数据需要填充以进行对齐，使用 BN 时可能会出现填充元素与正常数据进行 Normalization 的情况，这会影响正常数据的特征分布。而 LN 则是针对序列数据进行设计的，对 Batch 中每一个序列元素的每一个维度进行缩放和平移，因此不会被不同的序列长度影响 Batch 的特征分布。

• Transformer Encoder 的结构

  Multi-Head Attention、Residual Connection、MLP

• Multi Head Attention 的计算

  在每一个 Head 中通过 Q * K 得到权重，在对 V 加权求和得到单个 Head 的输出，最后连接所有 Head 的输出向量。

• Transformer Encoder 中残差连接的作用

  防止过拟合。

• SGD

  基本思想是随机选择一个样本进行梯度下降，一般使用动量进行优化。动量记录了之前多次反向传播时的优化幅度，基于动量对本次反向传播的优化幅度进行调整能提高学习速度。

• KNN 和 K-Means 的区别

  KNN 是有监督的、Memory-based （无训练过程）分类算法，通过选择 K 个最近样本点并将其中样本数量最多的类别作为当前数据样本的类别。

  K-Means 是无监督的聚类算法，有着明显的训练迭代的过程。

• K-Means 的初始化、迭代过程、停止条件

  初始化：随机选择 K 个样本点作为簇的中心；

  迭代：考察所有样本点到 K 个簇中心的距离并划入距离最近的一个簇，所有样本点划分完以后更新每一个簇的中心；

  终止条件：当 K 个簇的中心点均未发生变化时，结束迭代。

• LR、SVM、树、GDBT 等模型中，哪些是线性模型

  LR、SVM 通过线性的超平面对数据进行划分，属于线性模型。树、GDBT 使用的是离散的划分条件。

• Coding

  • 计算 π

    简单粗暴的方法是蒙特卡洛模拟，随机生成正方形中点并计算落在圆中的数量得到圆的面积，再基于面积计算 。

    但是随着精度要求的增加计算量会暴增，多进程并行的代码如下：

    import random
    from concurrent.futures import ProcessPoolExecutor, wait
    
    def estimate():
        x = 2 * random.random() - 1
        y = 2 * random.random() - 1
        return x ** 2 + y ** 2 <= 1
    
    def mc(simulations=5000000):
        cnt = 0
        for i in range(simulations):
            cnt += int(estimate())
        return cnt, simulations
    
    if __name__ == '__main__':
        num_workers = 8
        total_simulations = int(8e7)
        pool = ProcessPoolExecutor()
        x, y = 0, 0
        fus = []
        for i in range(num_workers):
            fu = pool.submit(mc, total_simulations // num_workers)
            fus.append(fu)
        wait(fus)
        for fu in fus:
            rst = fu.result()
            x += rst[0]
            y += rst[1]
        s = x / y
        print(s * 4)

  • 二维有序数组的查找算法设计与分析

    力扣 面试题 10.09. 排序矩阵查找。二维二分，复杂度