大厂AI算法面试题汇总

Q：如何反转一个单向链表？ A：使用双指针迭代法。初始化 pre = None，cur = head；遍历链表，每次保存 cur.next，将 cur.next 指向 pre，然后更新 pre = cur，cur = nxt；最终返回 pre。

Q：快排的时间复杂度是多少？最坏情况如何触发？ A：平均时间复杂度为 O(n log n)，最坏为 O(n²)。当每次选的 pivot 是最大或最小值（如已排序数组且选首元素为 pivot）时触发最坏情况。

Q：如何判断一棵二叉树是否是平衡二叉树？ A：递归计算左右子树高度，若任意子树高度差 >1，则不平衡。同时在递归中返回高度，避免重复计算。

Q：LeetCode 最长公共子序列（LCS）怎么解？ A：动态规划。设 dp[i][j] 表示 s1[:i] 与 s2[:j] 的 LCS 长度。状态转移：若 s1[i-1]==s2[j-1]，则 dp[i][j]=dp[i-1][j-1]+1；否则 dp[i][j]=max(dp[i-1][j], dp[i][j-1])。

Q：编辑距离的 DP 状态转移方程是什么？ A：dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + (s1[i-1]!=s2[j-1]))，分别对应删除、插入、替换操作。

Q：如何用 rand5() 实现 rand7()？ A：构造 0~24 的均匀分布：num = (rand5()-1)*5 + (rand5()-1)；若 num < 21，则返回 num % 7 + 1；否则重试。

Q：抛硬币直到连续三次正面，期望次数是多少？ A：14 次。通过状态转移方程求解：设 E₀ 为初始状态，E₁ 为已有1个H，E₂ 为已有2个H，列方程解得 E₀=14。

Q：单位圆内随机取一点，到圆心距离的期望是多少？ A：2/3。推导：半径 r 的概率密度为 f®=2r（因面积元为 2πr dr），故 E[r] = ∫₀¹ r·2r dr = 2/3。

Q：Python 中深拷贝和浅拷贝的区别？ A：浅拷贝只复制顶层对象，嵌套对象仍共享引用；深拷贝递归复制所有层级，完全独立。

Q：多进程和多线程在 Python 中如何选择？ A：CPU 密集型任务用多进程（绕过 GIL）；IO 密集型任务用多线程（如网络请求、文件读写）。

Q：TCP 和 UDP 的主要区别是什么？ A：TCP 面向连接、可靠、有序、慢；UDP 无连接、不可靠、可能乱序、快。适用于视频流、DNS 等场景。

Q：什么是装饰器？举一个日志装饰器的例子。 A：装饰器是高阶函数，用于增强函数功能。例如：

def log(func):
def wrapper(*args, **kwargs):
print(f"Calling {func.__name__}")
return func(*args, **kwargs)
return wrapper

Q：Self-Attention 的计算公式是什么？ A：Attention(Q,K,V) = softmax(QKᵀ / √d_k) V，其中 Q、K、V 由输入线性变换得到。

Q：为什么 Self-Attention 要除以 √d_k？ A：防止点积过大导致 Softmax 梯度消失。当 d_k 大时，q·k 方差增大，除以 √d_k 可使方差稳定为 1。

Q：Multi-Head Attention 的作用是什么？ A：让模型在不同子空间中学习不同的特征交互，类似 CNN 的多通道，提升表达能力。

Q：Transformer 为什么用 LayerNorm 而不是 BatchNorm？ A：因为 Transformer 处理变长序列，batch 内长度不一，BatchNorm 对小 batch 敏感；LayerNorm 对单样本归一化，更稳定。

Q：BERT 的输入包含哪三部分？ A：Token Embedding（词向量）、Segment Embedding（句子A/B标识）、Position Embedding（位置编码）。

Q：BERT 为什么不适合直接用于句向量相似度计算？ A：因其 embedding 存在各向异性（anisotropy），向量分布不均，导致余弦相似度失真。

Q：如何改进 BERT 的句向量表示？ A：使用 Sentence-BERT（微调时直接优化余弦相似度），或用 BERT-Flow 将 embedding 映射到各向同性空间。

Q：ResNet 的核心思想是什么？ A：引入残差连接（skip connection），让网络学习残差映射 F(x) = H(x) – x，缓解梯度消失和网络退化。

Q：Dropout 在训练和测试时如何处理？ A：训练时随机将部分神经元输出置0，并将剩余输出除以 (1-p)；测试时关闭 Dropout，直接前向传播。

Q：为什么测试时不关闭 Dropout 而是保持期望一致？ A：为保证训练和测试时激活值的期望相同，避免分布偏移。缩放操作使 E[output_train] = E[output_test]。

Q：L1 正则为何能产生稀疏解？ A：L1 的梯度为常数 λ·sign(w)，即使 w 接近0仍有恒定梯度将其推向0；而 L2 梯度随 w 减小而减小，趋近但不等于0。

Q：交叉熵损失 vs 均方误差（MSE）在分类任务中的区别？ A：交叉熵基于概率分布，梯度为 (y – p)，信息量大；MSE 梯度为 (y – p)·p·(1-p)，在 p 接近0/1时梯度消失。

Q：多标签分类的输出层和损失函数是什么？ A：输出层用 Sigmoid（每个标签独立），损失函数用 Binary Cross-Entropy（BCE）。

Q：Focal Loss 的公式和作用是什么？ A：FL(p_t) = -α_t (1 – p_t)^γ log(p_t)。通过 (1-p_t)^γ 降低易分样本权重，聚焦难样本，解决类别不平衡。

Q：XGBoost 的目标函数包含哪些项？ A：包括损失函数（如 log loss）的一阶和二阶梯度展开项，以及正则项（γT + ½λ||w||²），其中 T 为叶子数，w 为叶子权重。

Q：XGBoost 为何使用二阶泰勒展开？ A：可统一处理任意二阶可导损失函数，并利用曲率信息加速收敛。

Q：LightGBM 的 Leaf-wise 分裂策略是什么？ A：每次选择增益最大的叶子节点分裂，而非按层分裂（Level-wise），更高效但可能过拟合，需限制 max_depth。

Q：LightGBM 如何处理类别特征？ A：原生支持。对类别特征，按直方图统计梯度，自动寻找最优分割（如按类别集合划分）。

Q：GBDT 为什么不能使用平方损失处理分类问题？ A：可以，但效率低。GBDT 通常用指数损失（AdaBoost）或对数损失（LogitBoost）更适合分类。

Q：Wide & Deep 模型的 Wide 部分作用是什么？ A：记忆高频共现特征组合（如“用户A+商品B”），提升准确率和可解释性。

Q：DeepFM 相比 Wide & Deep 的改进是什么？ A：用 FM 替代 Wide 部分，自动学习二阶特征交叉，无需人工设计交叉特征。

Q：BatchNorm 在训练和推理时有何不同？ A：训练时用当前 batch 的均值和方差；推理时用训练阶段累积的滑动平均均值和方差。

Q：为什么 RNN 难以并行？ A：因为每一步的隐藏状态依赖前一步输出，存在时间上的串行依赖。

Q：Transformer 如何实现并行？ A：抛弃循环结构，所有位置通过 Self-Attention 同时计算，完全并行。

Q：Positional Encoding 的作用是什么？ A：为输入序列注入位置信息，弥补 Transformer 无序性的缺陷。

Q：为什么 Positional Encoding 用 sin/cos 而不用可学习向量？ A：sin/cos 具有周期性和可扩展性，能泛化到训练时未见的序列长度。

Q：如何处理 BERT 的长文本（>512 tokens）？ A：常用方法：head-only（取前512）、tail-only（取后512）、head+tail（如128+384），或分段后用 Pooling/Attention 融合。

Q：ONNX 的作用是什么？ A：提供模型中间表示格式，实现跨框架（PyTorch/TensorFlow）部署，配合 ONNX Runtime 加速推理。

Q：模型量化的作用和风险？ A：作用：减少模型体积、加速推理（INT8 比 FP32 快2~4倍）；风险：精度下降，需校准（calibration）避免崩塌。

Q：如何判断两个矩形是否相交？ A：若两矩形中心距离在 x/y 方向均小于半宽之和，则相交。或用分离轴定理（SAT）。

Q：如何合并重叠区间？ A：先按左端点排序，然后遍历：若当前区间与结果末尾重叠，则合并；否则加入新区间。

Q：最长不重复子串的解法？ A：滑动窗口 + 哈希表记录字符最近位置。右指针扩展，左指针跳至重复字符下一位。

Q：Top-K 问题为何用堆而不是全排序？ A：堆时间复杂度 O(n log k)，空间 O(k)；全排序 O(n log n)，当 k << n 时堆更优。

Q：如何实现 LRU 缓存？ A：用哈希表 + 双向链表。哈希表 O(1) 查找，链表维护访问顺序，头插新元素，尾删最久未用。

Q：Softmax 梯度怎么推导？ A：设 y_i = e^{z_i} / Σe^{z_j}，则 ∂L/∂z_i = y_i – t_i（t_i 为 one-hot 标签）。

Q：为什么不用 MSE 做分类损失？ A：MSE 对异常值敏感，且梯度在预测接近0/1时趋于0，导致训练缓慢甚至停滞。

Q：数据不平衡有哪些处理方法？ A：过采样（SMOTE）、欠采样、Focal Loss、调整分类阈值、集成方法（如 BalancedRandomForest）。

Q：如何评估多标签分类模型？ A：常用指标：Hamming Loss（错分比例）、Subset Accuracy（全对才算对）、One-error（最相关标签不在真实集中）、F1-micro/macro。

Q：如何用两个栈实现一个队列？ A：使用两个栈 in_stack 和 out_stack。入队时压入 in_stack；出队时，若 out_stack 为空，则将 in_stack 全部弹出并压入 out_stack，再从 out_stack 弹出栈顶。这样可保证 FIFO 顺序。

Q：LeetCode 300 最长递增子序列（LIS）的 O(n log n) 解法是什么？ A：维护一个数组 tails，其中 tails[i] 表示长度为 i+1 的递增子序列的最小末尾元素。遍历原数组，对每个元素用二分查找找到第一个 ≥ 它的位置，替换或追加。最终 tails 长度即为 LIS 长度。

Q：什么是梯度消失？为什么 RNN 容易出现梯度消失？ A：梯度消失指反向传播时梯度逐层衰减趋近于 0，导致浅层参数几乎不更新。RNN 中梯度通过链式法则连乘多个 Jacobian 矩阵，若其特征值 <1，多次相乘后梯度指数级衰减。

Q：LSTM 如何缓解梯度消失？ A：LSTM 引入细胞状态（cell state）和门控机制。细胞状态通过“恒等路径”传递信息，遗忘门和输入门控制信息流，使梯度可通过近似恒等映射回传，避免连乘衰减。

Q：Softmax 函数的输出为何不适合作为概率校准后的置信度？ A：现代深度网络（如 ResNet）的 Softmax 输出往往过于自信（over-confident），即高 softmax 值 ≠ 高准确率。这是由于模型未充分正则化或训练目标未显式优化校准度，需用 Temperature Scaling 等方法校准。

Q：BatchNorm 在训练和推理时有何不同？ A：训练时使用当前 batch 的均值和方差进行归一化，并记录滑动平均；推理时使用训练阶段累积的全局均值和方差，以保证确定性输出。

Q：为什么 Transformer 使用 LayerNorm 而不是 BatchNorm？ A：因为 Transformer 处理变长序列，batch 内样本长度不一，BatchNorm 对小 batch 或动态长度不稳定；LayerNorm 对单个样本所有维度归一化，与 batch size 无关，适合 NLP 任务。

Q：BERT 的 [CLS] 向量为什么不能直接用于句向量相似度计算？ A：因为 BERT 的 embedding 空间存在各向异性（anisotropy），[CLS] 向量分布不均匀，高频词聚集、低频词分散，导致余弦相似度失真，需用 Sentence-BERT 或 BERT-Flow 改进。

Q：Focal Loss 的核心思想是什么？适用于什么场景？ A：通过 (1 – p_t)^γ 降低易分类样本的权重，使模型聚焦于难分类样本。适用于正负样本极度不平衡的任务，如目标检测中的前景/背景分类。

Q：XGBoost 如何处理缺失值？ A：在节点分裂时，XGBoost 将缺失值样本分别归入左/右子树，选择使损失下降更多的方向作为默认分裂方向，并在预测时沿用该规则。

Q：LightGBM 的 GOSS（Gradient-based One-Side Sampling）是什么？ A：GOSS 保留梯度绝对值大的样本（重要样本），并对梯度小的样本随机采样，从而在减少计算量的同时保持对信息增益的准确估计，加速训练。

Q：CatBoost 如何处理类别型特征？ A：CatBoost 使用有序 boosting（Ordered Boosting）和基于统计的类别编码（如 target encoding），并在训练时自动处理类别特征，避免过拟合。

Q：Wide & Deep 模型中 Wide 部分为什么要人工构造交叉特征？ A：因为线性模型无法自动学习特征组合，需通过人工设计如 AND(user_gender=female, item_category=cosmetics) 来捕捉高频共现模式，提升记忆能力。

Q：DeepFM 相比 Wide & Deep 的最大优势是什么？ A：DeepFM 用 FM 替代 Wide 部分，自动学习二阶特征交叉，无需人工特征工程，且 FM 与 Deep 共享 embedding，训练更高效、泛化更强。

Q：如何判断一个链表是否存在环？空间复杂度 O(1) 的解法？ A：使用快慢指针（Floyd 判圈算法）。快指针每次走两步，慢指针每次走一步，若相遇则有环；若快指针到达 null 则无环。空间复杂度 O(1)。

Q：LeetCode 141 环形链表的快慢指针为什么一定能相遇？ A：设环长为 L，慢指针进入环后，快指针已在环内。两者相对速度为 1，最多 L 步内快指针会追上慢指针，故必相遇。

Q：TCP 三次握手的过程是什么？为什么不能两次？ A：过程：Client → SYN → Server；Server → SYN+ACK → Client；Client → ACK → Server。两次握手无法防止历史连接请求突然到达服务器造成资源浪费（如旧 SYN 重传）。

Q：UDP 为什么适合视频流传输？ A：因为 UDP 无连接、无重传、低延迟，即使丢包也不会阻塞后续数据，适合容忍少量丢包但要求实时性的场景（如直播、视频会议）。

Q：SIFT 特征为何具有尺度不变性？ A：SIFT 在高斯金字塔（多尺度空间）中检测极值点，通过 DoG（Difference of Gaussians）近似 LoG，找到在尺度和空间上都稳定的兴趣点，从而实现尺度不变。

Q：LBP（局部二值模式）如何提取纹理特征？ A：以像素为中心，将其 8 邻域灰度与中心比较，大于为 1，否则为 0，形成 8 位二进制数作为 LBP 值。统计整图 LBP 直方图即为纹理描述。

Q：HOG 特征的计算步骤是什么？ A：1）计算图像梯度幅值和方向；2）划分 cell（如 8×8），统计梯度方向直方图；3）组合多个 cell 为 block（如 2×2），对 block 内直方图做 L2 归一化；4）拼接所有 block 特征向量。

Q：白平衡的灰度世界假设是什么？ A：假设自然场景中 RGB 三通道的平均值趋于相同（即整体呈灰色），据此调整各通道增益，使图像平均值相等，消除色偏。

Q：Adaboost 和随机森林的核心区别是什么？ A：Adaboost 是 Boosting 方法，串行训练，每轮关注前一轮错分样本，弱分类器加权投票；随机森林是 Bagging 方法，并行训练，每棵树独立采样，最终多数投票。

Q：KKT 条件在 SVM 中的作用是什么？ A：KKT 条件是 SVM 对偶问题取得最优解的充要条件，其中包含互补松弛条件：α_i > 0 ⇒ 样本为支持向量；α_i = 0 ⇒ 样本不影响决策边界。

Q：ROC 曲线和 PR 曲线适用场景有何不同？ A：ROC 对类别不平衡不敏感，适合评估整体排序能力；PR 曲线（Precision-Recall）对正样本稀疏敏感，更适合评估少数类性能（如欺诈检测）。

Q：AUC 的物理意义是什么？ A：AUC 表示随机选一个正样本和一个负样本，模型给正样本打分高于负样本的概率。AUC=0.5 为随机猜测，AUC=1 为完美分类。

Q：TensorFlow 1.x 中 Graph 和 Session 的关系？ A：Graph 定义计算流程（静态图），Session 负责执行 Graph 并分配资源。先构建 Graph，再通过 Session.run() 输入数据、获取结果。

Q：LeetCode 3 无重复字符的最长子串如何用滑动窗口解决？ A：维护窗口 [left, right] 和哈希表记录字符最近位置。right 扩展时，若遇到重复字符，left 跳至其上次位置+1。全程记录窗口最大长度。

Q：如何在 1G 大文件中找出词频 Top 100（内存仅 1M）？ A：1）Hash 映射：hash(word) % 5000 分成 5000 个小文件；2）对每个小文件用 HashMap 统计词频；3）用最小堆维护 Top 100；4）合并各文件结果。

Q：GBDT 为什么不能使用平方损失直接处理分类问题？ A：可以，但效率低。GBDT 通常将分类转化为回归问题，用对数损失（Log Loss）或指数损失（AdaBoost）更合适，因其梯度更能反映分类误差方向。