寻找题库中美团笔试类似的题目，方便回顾掌握

选择题集与相关知识点解析

选择题 1

要求在对表达式 6 + 5 * (3 * 2 + 1) - 9 使用栈进行求值的过程中，当扫描到数字1时，对象栈（也叫操作数栈）中的内容是什么。

相关知识点：表达式求值

1. 中缀表达式 (Infix Notation)
  • 定义：运算符位于两个操作数之间，是人类最习惯的书写方式。
  • 示例：A + B，(3 + 4) * 5 - 6
  • 用途：日常数学书写、编程语言中的表达式（如 C、Python、Java 等）。直观易读，但计算机直接求值较复杂，因为需要处理括号和运算符优先级。
  • 缺点：需要括号来明确运算顺序，不能直接用栈高效求值，通常需要先转换为前缀或后缀表达式。
2. 前缀表达式 (Prefix Notation / Polish Notation)
  • 定义：运算符位于两个操作数之前。由波兰逻辑学家 Jan Łukasiewicz 提出，故称“波兰表示法”。
  • 示例：中缀 A + B 转换为前缀 + A B；中缀 (3 + 4) * 5 转换为前缀 * + 3 4 5。
  • 用途：无需括号，无歧义。适合递归解析和自顶向下求值。
  • 求值方法：从右往左扫描，遇到操作数入栈，遇到运算符则弹出两个操作数计算后压回。
3. 后缀表达式 (Postfix Notation / Reverse Polish Notation, RPN)
  • 定义：运算符位于两个操作数之后，称为“逆波兰表示法”。
  • 示例：中缀 A + B 转换为后缀 A B +；中缀 (3 + 4) * 5 转换为后缀 3 4 + 5 *。
  • 用途：无需括号，无优先级问题，表达式无歧义。非常适合用栈进行求值，是计算器和编译器中间代码的常用形式。
  • 求值方法：
    1. 从左往右扫描，遇到操作数则入栈。
    2. 遇到运算符则弹出栈顶两个元素（注意顺序），计算结果压回栈。
    3. 最终栈中只剩一个值，即为结果。
使用双栈计算中缀表达式

使用双栈（一个操作数栈，一个运算符栈）计算中缀表达式的步骤如下：

  1. 从左到右扫描表达式。
  2. 遇到操作数，直接压入操作数栈。
  3. 遇到运算符（如 +, -, *, /）：
    1. 如果运算符栈为空，或栈顶是左括号 (，直接压入运算符栈。
    2. 如果当前运算符的优先级高于运算符栈顶的运算符，也直接压入。
    3. 否则，从运算符栈弹出一个运算符，从操作数栈弹出两个操作数进行计算，将结果压回操作数栈。重复此过程，直到当前运算符可以压入运算符栈。
  4. 遇到左括号 (，直接压入运算符栈。
  5. 遇到右括号 )，不断从运算符栈和操作数栈弹出元素进行计算，直到遇到左括号 ( 为止，然后将左括号 ( 弹出。

核心思想：模拟人类处理括号和运算优先级的过程。栈的作用是暂存尚未能确定是否可以立即计算的部分。

选择题 2

对10个关键字 {278, 109, 63, 930, 589, 184, 505, 269, 8, 83} 进行链式基数排序，则总共需要进行 () 趟分配收集，第二趟分配后，基数为6的队列中的元素为 ()。

相关知识点：基数排序 (Radix Sort)

基数排序是一种非比较型整数排序算法，它不通过元素之间的比较来排序，而是借助“按位处理”的思想，利用数字的每一位（如个位、十位、百位）进行多轮分配与收集，最终实现有序。

1. 时间复杂度：为什么能突破 O(n log n)？
  1. 比较排序（如快排、归并）的理论下限是 O(n log n)。
  2. 基数排序不依赖比较，因此可以做到线性时间：O(d⋅(n+k))，其中：
    • n ：元素个数
    • d ：最大数的位数（如最大数是 999，则 d=3）
    • k ：每一位的可能取值数（如十进制 k=10）
  3. 当 d 和 k 为常数时，时间复杂度近似为 O(n)。

理论下限解释：比较排序的过程可以看作一个二叉决策树。要区分 n 个元素的所有 n! 种排列，决策树至少需要 n! 个叶子。根据数学推导，树的最小深度（即最少比较次数）为 O(n log n)。基数排序不依赖比较，因此不在此模型的限制之内。

2. 优缺点
  1. 优点：速度快，在特定条件下可达线性时间。
  2. 代价：
    1. 需要数据可拆分为有限范围的符号位。
    2. 空间代价更高，需要额外的桶空间。
    3. 对浮点数、对象或变长数据结构不直接适用，需要额外技巧。

选择题 3

下列关于同步和异步的说法，错误的是 ( )

A 同步是阻塞模式，进程需要等待 B 异步是非阻塞模式，进程无需等待 C 同步的解析速度比异步快 D 同步是有顺序的，异步没有顺序

相关知识点：同步/异步 vs. 阻塞/非阻塞

同步/异步关注程序逻辑层面的设计和消息通知机制；阻塞/非阻塞关注操作系统 I/O 层面的调用状态。

名称含义关键特征举例
同步 (Synchronous)调用方必须等待操作完成后才能继续执行。顺序执行，调用阻塞，逻辑简单。Python 普通函数调用、Java 传统 I/O。
异步 (Asynchronous)调用方在发出请求后无需等待，可在操作完成后通过回调/事件获得结果。非顺序执行，通过事件驱动或 Future 机制管理结果。JavaScript async/await、Python asyncio。
阻塞 (Blocking)调用线程被挂起，直到操作完成。CPU 处于空闲等待状态。占用线程但不占用 CPU。read() 系统调用等待磁盘数据。
非阻塞 (Non-blocking)调用立即返回，即使操作未完成，也可通过轮询或回调获得结果。提高 CPU 利用率，典型于高并发 I/O。Linux epoll、select、aio、Go runtime。

选择题 4

将 IP 地址空间 211.212.1.0/24 划分为 2 个子网，每个子网需分配的 IP 地址数不少于 120 个。

相关知识点：IP地址与子网划分

  1. 总地址数：由主机位的数量决定，总地址数 = 2^主机位数。
  2. 可用主机数：可用主机数 = 总地址数 - 2。需要减去网络地址（主机位全为0）和广播地址（主机位全为1）。
  3. 网关：必须是子网内的一个合法主机地址，不能是网络地址或广播地址。

选择题 5

使用FlashAttention优化推理速度后，推荐系统NDCG下降5%。原因是：

A 近似计算忽略低频用户行为模式 B 块计算（Tiling）导致注意力权重截断误差 C 硬件指令集不兼容FP16精度损失 D 稀疏化掩码破坏行为序列连续性

相关知识点 1：推荐系统评估指标 (NDCG)

NDCG (Normalized Discounted Cumulative Gain) 是一种衡量排序质量的指标，尤其适合推荐系统。

  1. CG (Cumulative Gain): 将推荐列表中所有物品的相关性得分相加，不考虑位置。
  2. DCG (Discounted Cumulative Gain): 在CG的基础上，对排在后面的物品施加一个位置惩罚（分母变大）。位置越靠后，其相关性得分的贡献越小。
  3. NDCG (Normalized DCG): 用当前列表的DCG除以“理想”推荐列表的DCG（IDCG），得到一个0到1之间的归一化值，方便跨用户比较。值越接近1，排序质量越高。

相关知识点 2：FlashAttention 核心原理

FlashAttention 是一种通过 I/O 感知优化来加速注意力计算并减少显存占用的技术，其数学计算结果与标准 Attention 等价。

  1. 块计算 (Tiling)：将巨大的注意力矩阵（N x N）切分成小块，逐块进行计算。
  2. 重计算 (Recomputation)：在反向传播时，不存储中间的巨大注意力矩阵，而是在需要时重新计算，极大节省显存。
  3. IO感知 (IO-Aware)：优化 GPU 内存（HBM）和高速缓存（SRAM）之间的数据读写，减少了慢速内存的访问次数。

相关知识点 3：数值精度 (FP16/BF16)

  1. FP32：单精度浮点（32位），标准精度。
  2. FP16：半精度浮点（16位）。指数位仅5位，动态范围小，容易在训练中出现梯度下溢（underflow）或上溢（overflow）。
  3. BF16 (Bfloat16)：半精度浮点（16位）。指数位与FP32相同（8位），因此能表示与FP32相同范围的数值，有效避免上溢和下溢问题，更适合深度学习训练。
  4. INT8 / INT4：量化计算，常用于推理加速。

选择题 6

跨城市迁移外卖推荐模型时，直接微调在新城市AUC下降20%。最优策略是：

A 用原城市数据继续预训练再微调 B 对新城市样本进行加权损失训练 C 采用课程学习渐进切换数据分布 D 冻结Transformer底层仅微调顶层

相关知识点：迁移学习与领域自适应

参数微调 (Fine-tuning)

将一个在海量数据上预训练好的模型作为起点，在目标任务数据上继续训练，使其适应新任务。

  1. 全量微调 (Full Fine-tuning)：对所有层都进行训练。适用于目标数据量充足的场景。
  2. 冻结部分层 (Freezing Layers)：冻结学习通用特征的底层，只训练学习具体特征的顶层。适用于目标数据量较少的场景，能有效防止过拟合。
  3. 逐层解冻与差分学习率：更精细的策略，先训练顶层，然后逐步解冻下层，并为不同层设置不同的学习率（底层学习率小，顶层学习率大）。
领域自适应 (Domain Adaptation)

解决源域和目标域数据分布不一致，但任务相同的问题。

  1. 领域对抗训练 (Domain-Adversarial Training)：引入领域判别器，与特征提取器进行对抗，迫使模型学习领域无关的特征。
  2. 样本加权/重要性采样：给源域中与目标域分布更相似的样本更高的权重。
  3. 课程学习/渐进式训练 (Curriculum Learning)：模仿人类“先易后难”的学习过程，平滑地将模型从源域迁移到目标域。
    1. 热身: 训练数据 = 90% 源域数据 + 10% 目标域数据。
    2. 适应: 逐步增加目标域数据的比例，例如 70%/30% -> 50%/50%。
    3. 专注: 最后，只使用 100% 的目标域数据进行微调。

选择题 7

在10亿用户规模的实时推荐系统中，传统Transformer推理延迟超标。采用稀疏专家模型（MoE）后GPU内存溢出，根本原因是：

A. 专家路由算法（如GShard）未均衡负载 B. 专家参数未分区存储（Parameter Sharding） C. 门控网络（Gating Network）计算开销过高 D. FFN层未启用梯度检查点（Gradient Checkpointing）

相关知识点：稀疏专家模型 (MoE) 工作流

MoE 用 N 个专家网络 (Experts) 替代了标准 Transformer 中的单个 FFN 层。

  1. 门控网络 (Gating Network)：为每个输入的 token 计算一个概率分布，决定该 token 应该由哪些专家处理。通常采用 Top-k 路由策略（如 Top-1 或 Top-2）。
  2. 路由 (Dispatch)：根据门控网络的结果，将每个 token 的表示发送到被选中的专家那里。
  3. 专家计算 (Expert Computation)：每个专家都是一个独立的 FFN 网络，它只处理被路由到自己这里的 token 子集。计算是稀疏的，但所有专家的参数都需要存储在显存中。
  4. 聚合 (Combine)：将各个专家的输出结果根据门控网络的权重进行加权求和，得到最终的输出。

相关知识点：分布式训练与显存优化

  1. 负载均衡损失 (Load Balancing Loss)：在 MoE 中，为门控网络加入一个额外的正则项损失，鼓励它将 token 均匀地分配给所有专家，防止某些专家过载。
  2. 参数分区 (Parameter Sharding / ZeRO)：由 Microsoft DeepSpeed 提出的技术。它将模型的参数、梯度和优化器状态切分到不同的 GPU 上，从而极大地节省了单张 GPU 的显存。ZeRO-3 会对模型参数本身进行分区。

选择题 8

联邦微调广告点击率模型时，参与方恶意上传噪声梯度。最可靠防御是：

A 采用RSA加密梯度传输 B 添加梯度范数截断（Gradient Clipping） C 使用Krum或多维中值聚合 D 启用同态加密本地训练

相关知识点：联邦学习 (Federated Learning, FL)

一种分布式的、保护隐私的机器学习框架，核心思想是“数据不动，模型动”。

  • 流程：
    1. 分发：中央服务器将全局模型分发给各参与方。
    2. 本地训练：各参与方使用本地数据训练模型，计算出模型更新（梯度或权重）。
    3. 上传：参与方只上传模型更新，原始数据保留在本地。
    4. 聚合：服务器收集所有更新，通过聚合算法（如 FedAvg）融合成新的全局模型。
    5. 循环：重复以上步骤。

相关知识点：拜占庭攻击与鲁棒聚合

  • 拜占庭攻击：指分布式系统中的恶意节点发送虚假或有害信息，企图破坏系统的共识和正确性。在联邦学习中，表现为上传恶意的模型更新来“毒化”全局模型。
  • 鲁棒聚合 (Robust Aggregation)：旨在抵御拜占庭攻击的聚合算法。它不盲目相信所有上传的更新，而是通过统计方法识别并过滤掉异常值。
经典鲁棒聚合算法
  1. Krum / Multi-Krum：
    • 思想：一个诚实的更新应该与大多数其他诚实的更新“距离”更近。
    • 流程：为每个梯度更新计算一个分数（它到其最近邻居们的距离之和），选择分数最低的一个（或 k 个）更新作为本轮的聚合对象。
  2. 多维中值 / 几何中值 (Geometric Median)：
    • 思想：将一维数据中“中位数”对异常值不敏感的特性推广到高维空间。
    • 流程：寻找高维空间中的一个“中心点”，该点到所有梯度向量的距离之和最小。这个中心点就是本轮的聚合结果。它拥有极高的鲁棒性。

选择题 9

在显存充足、RoPE编码的情况下，使用Ring Attention训练长文本客服模型，序列长度扩展至1M tokens后训练崩溃。经查，Ring Attention的环形通信流程中缺少对超长序列下块处理超时的异常处理机制。根本原因是：

A 块间依赖导致死锁（Deadlock） B 位置编码未适配超长序列 C 显存分配策略导致通信缓冲区溢出 D 注意力计算未启用稀疏化

相关知识点：FlashAttention vs. Ring Attention

FlashAttention：单卡 GPU 的极致优化
  • 解决问题：GPU 内部的内存读写瓶颈。
  • 核心技术：
    1. 分块计算 (Tiling)：将 Q, K, V 矩阵切块，加载到高速 SRAM 中计算。
    2. 核函数融合 (Kernel Fusion)：将矩阵乘法、Softmax 等多个操作合并成一个 GPU 核函数，避免中间结果写回慢速 HBM。
  • 结果：在单卡上实现 2-4 倍加速和大幅显存节省，使处理更长序列成为可能。
Ring Attention：多卡 GPU 的协同扩展
  • 解决问题：当序列长到单卡无法容纳时，如何进行跨设备并行计算。
  • 核心技术：
    1. 序列并行 (Sequence Parallelism)：将序列本身切分到多个 GPU 上。
    2. 环形通信 (Ring Communication)：K 和 V 数据块在 GPU 之间进行环形传递。
    3. 计算与通信重叠 (Overlap)：当 GPU 在进行计算时，同时将自己的数据块发送给下一个 GPU，从而隐藏通信延迟。
  • 结果：使序列长度可以随 GPU 数量线性扩展，理论上可处理无限长序列。
为什么 Ring Attention 会导致死锁？

死锁的四个必要条件：

  1. 互斥：GPU 资源一次只能被一个进程使用。
  2. 持有并等待：GPU i 持有自己的数据块，并等待来自 GPU i-1 的数据块。
  3. 非抢占：不能强制从一个 GPU 手中夺走正在处理的数据。
  4. 循环等待：GPU 0 等待 GPU 3，GPU 3 等待 GPU 2，…，GPU 1 又等待 GPU 0，形成了一个完美的等待环路。

Ring Attention 的工作模式天然满足这四个条件。如果环上任何一个节点的处理或通信发生延迟或阻塞，整个环路就会陷入无限等待，即死锁。

选择题 10

冷启动骑手调度系统中，大模型对新骑手能力评估误差>40%。当前首要目标是在不影响真实订单体验的前提下，快速获得对骑手能力的可靠估计。系统已积累了大量历史骑手的详细画像与初期表现数据。最优方案是：

A 在模拟环境中使用强化学习进行大量随机派单探索 B 让新骑手在真实环境中尝试高难度订单以测试其极限能力 C 基于历史相似骑手画像进行能力估计迁移 D 仅使用新骑手的年龄和性别进行简单线性回归预测

知识点详解：构建智能骑手冷启动系统

第一部分：从画像到向量——量化“相似”
  1. 特征工程 (Feature Engineering)：将骑手的所有信息（画像）转换成一个机器可以处理的特征向量。
    1. 数值型特征：年龄、驾龄等（需归一化）。
    2. 类别型特征：性别、交通工具、学历等（需独热编码）。
    3. 地理/时间特征：常驻区域、活跃时段等（需地理编码或分段编码）。
  2. 相似度度量 (KNN方法)：
    1. 对新骑手，计算其特征向量与数据库中每个历史骑手向量的距离或相似度。
    2. 找到距离最近的 K 个历史骑手（Top-K）。
    3. 将这 K 个历史骑手入职初期的表现数据进行加权平均，作为对新骑手能力的初始估计。
  3. 更复杂的模型 (Embedding)：使用双塔模型或图神经网络（GNN）学习一个更深刻、更准确的骑手嵌入向量表示，再进行相似度匹配。
第二部分：贝叶斯框架——从静态估计到动态学习
  1. 先验信念 (Prior Belief)：
    1. 使用Beta分布 Beta(α, β) 来为骑手的能力（如准时率）建模。α 可理解为成功次数，β 为失败次数。
    2. 基于第一部分找到的相似群体的初期表现，为新骑手设定一个先验分布。
  2. 收集证据与更新信念 (Posterior Update)：
    1. 当新骑手完成订单后，利用贝叶斯更新规则更新其能力分布。
    2. Posterior = Beta(α_prior + successes, β_prior + failures)。
    3. 随着真实数据的积累，分布会变得越来越“瘦高”，代表我们对骑手能力的估计越来越确定。
  3. 决策：汤普森采样 (Thompson Sampling)：
    1. 一种优雅地平衡“探索与利用”的算法。
    2. 流程：当有新订单时，为每个可用骑手，从其当前的能力分布中随机采样一个值。将订单派给采样值最高的那个骑手。
    3. 效果：能力确定且高的老骑手有很大概率被选中（利用）；能力不确定的新骑手偶尔能采到高值，从而获得证明自己的机会（探索）。

编码题集与相关知识点解析