哔哩哔哩：2021 算法岗（实习）

问题

Python列表与元组的区别 元组一旦初始化后，就不可以再改变（无法直接修改元组内对象的指针或者增删元素，但是可以调用内部元素的方法进行操作，如list.append），但是列表没有这些限制。
深浅拷贝的区别

是否会对对象内部的对象递归地拷贝（内部对象指针指向原地址还是新的地址）。
类和对象的区别

类主要定义了方法，可以当做行为的模板；对象是数据的载体，并可以执行类中定义的行为。
装饰器的原理

装饰器本身就是一个接收方法为参数的方法，可以在内部调用被装饰的方法前后执行其他逻辑。
常见的排序算法

冒泡、插入、归并、快排、堆排序、基数排序等。
归并算法的思想与时间复杂度

思想：分治， $k$ 路归并算法每次将 $n$ 个元素的排序问题分解成多个 $n / k$ 规模的子问题，在子问题求解完以后再对子问题的解进行合并，可递归地进行实现。

时间复杂度：子问题数量： $\log(n)$ ，分解与合并的复杂度 $O (n)$ ，整体的复杂度： $O(n\log (n))$ 。
数组与链表在原理、操作时间复杂度上的区别，以及应用场景

原理：二者都拥有线性的逻辑结构，区别主要在物理结构上，数组的内存大小固定且连续，链表中元素在内存中不连续。

操作时间复杂度：
- 读取、修改：数组 $O (1)$ ，链表 $O (N)$ ；
- 增、删：数组 $O (n)$ （需要批量移动内部元素），链表 $O (1)$ 。
应用场景：
- 数组：数据量已知、固定，且读取和修改操作的需求量大于增删操作的需求量；
- 链表：数据量未知，且增删操作较多。
如何用两个栈实现队列

假设有两个栈 A、B：
- 对于队列的入队操作，直接全部压到栈 A 的顶部，此时 A 中元素的顺序与入队的顺序相反，初始时 B 为空栈。
- 一旦遇到出队操作：
  - 如果 B 为空，则将 A 中的元素全部依次出栈并放入 B 中，此时 B 中元素的顺序和入队的顺序是一致的，再将 B 中元素出栈；
  - 如果 B 不为空，则直接从 B 中将元素出栈；
  - 出队操作完成后，不需要将 B 中元素再装回 A 中，可直接用于下次出栈。
梯度爆炸与梯度消失的原因与理论基础

理论基础：反向传播时的链式求导。

原因：
- 根本原因：反向传播时，如果导数权重一直大于 $1$ ，则在链式求导的过程中梯度会越来越大，最终导致梯度爆炸；相反，如果导数权重一直小于 $1$ 则会导致梯度越来越小，最终导致梯度消失。
- 导致梯度问题的直接原因可能是：
  - 使用了不适当的激活函数，如 sigmoid 容易导致梯度消失；
  - 模型复杂，深度过大，导致求导链过长；
  - 初始的特征、权重过大，导致输出值方差较大，最终导致梯度过大。
如何处理梯度爆炸与梯度消失
- 处理梯度爆炸：
  - 对于梯度本身，可以考虑使用梯度裁剪限制每次优化的幅度区间；
  - 使用 L1、L2 正则化，每次在优化时对参数施加一个正则惩罚项，防止优化幅度过大。
- 处理梯度消失：
  - 对于线性的数据，使用 LSTM 中的“门控”（gate）思想，每次“记住”前面一些时间步的“记忆”，防止梯度消失。
- 通用的优化手段：
  - 选择更好的激活函数，如 ReLU、LeakyReLU 等；
  - 使用残差连接的思想设计模型，提供降低模型复杂度的可能性；
  - 预训练+微调，每次仅对一层模块进行训练优化并固定其他层，从而得到一层模块的局部最优解，在得到众多的局部最优参数后，通过全局的反向传播进行微调得到全局最优；
  - 对不同的模块使用不同的学习率；
  - 使用 BatchNorm 等正则化方法，对层的输入进行优化，使得训练更加稳定。
如何处理过拟合
- 从网络结构层次的角度，可以采用残差连接的方式，提供降低模型复杂度的可能；
- 从正向传播的角度，可以使用 Dropout的方式，每次丢弃一部分特征，防止参数过分依赖训练数据，增加参数对数据集的泛化能力；
- 从反向传播的角度，可以通过正则化的方式，每一次计算loss时增加一个参数相关的惩罚项，缩放参数值使输出的区间更为稳定合理；
- 从数据处理的角度，通过进行 shuffle 打乱数据的顺序、对数据进行增广（增加噪音、变换等），避免参数对数据的依赖，提高泛化能力；
- 从训练的角度，可以考虑使用 EarlyStopping 在模型持续优化一定 Epoch 后便提前停止训练；
CNN 卷积神经网络，用于对规则的欧氏空间内的数据进行处理：通过一个共享的卷积核（kernel），每次在输入的矩阵中按照设定的卷积核大小、步长（Stride）和填充（padding）进行移动，输出为一个新的矩阵。

即使卷积核为 $1\times 1$ 的，其计算也与 MLP 不同：MLP是不同维度对应不同的权重；而 $1\times1$ 的卷积核是共享的，即所有维度共享同一个权重。
开放思考题：有哪几种方法（思路）来判断APP的截图中是否存在弹窗

基本就是 CV 相关的领域了，不涉及具体技术细节仅从解决思路来回答的话，主要可以从以下几个角度（训练 CV 相关的模型）进行检测：
- 边框：大部分弹窗以及其中的互动按钮都包含一些规则的边框（如矩形、圆角矩形、圆形）等，可提取这些边框进行识别，但是如果背景中存在边框或者遇到不规则的弹窗（如有其他附加物）则难以准确识别；
- 颜色：从弹窗的设计机制来说，一般在弹窗出现时会通过降低背景界面的明度、饱和度等方式让用户聚焦于弹窗，从颜色的角度可以进行识别；
- 文本：使用 OCR 相关功能提取截图中的文本，并判断是否属于弹窗相关的文本（如“关闭”、“确定”、“注意”、“通知”等）；
- 位置：弹窗一般位于截图的中间、中上等用户容易聚焦的位置，重点关注这些位置的信息可以提高弹窗识别的准确度。
将以上角度综合进行考虑就能基本覆盖大部分弹窗场景。

总结

面试所考察的知识点不深且较广（但也属于正常该掌握的范围），包含机器学习与 Python、算法、数据结构的基础。

面试的部门偏向通过 AI 算法为测试和研发提供技术支持，所以面试中涉及到的开放思考题也和测试的业务有关。