多模态大模型一面面经

写在前面

【WeThinkIn出品】栏目专注于分享Rocky的认知思考与经验感悟，范围涵盖但不限于AI行业。

干货AIGC、AI Agent、LLM算法工程师/开发工程师面试面经秘籍分享（持续更新）：WeThinkIn/AIGC-Interview-Book欢迎大家Star～

大家好，我是Rocky Ding。

开场与项目讨论

1.项目深挖

回答：

项目深挖不能只按技术栈报菜名，应沿着“业务目标 -> 数据与任务定义 -> 模型方案 -> 训练/推理 -> 评测 -> 上线约束”形成一条可验证的主线。先说明系统为谁解决什么问题、原流程的瓶颈是什么，再说明为什么选择当前模型和训练方法，以及自己真正负责的模块。

一个完整的项目回答至少包含以下内容：

1. 任务定义。 输入输出是什么，属于分类、生成、检索、视觉问答、工具调用还是多阶段任务；成功与失败如何判定。
2. 数据构建。 数据来源、清洗规则、标注协议、训练/验证/测试划分、去重和困难样本覆盖。多模态项目还要说明图文对是否对齐、图片质量、OCR 文本和长宽比分布。
3. 技术决策。 为什么选择某个基座模型、视觉编码器、连接器、LoRA/全量微调、DPO/GRPO 或 RAG；替代方案是什么，取舍依据是效果、显存、延迟、成本还是合规。
4. 工程闭环。 训练配置、并行方式、混合精度、checkpoint、推理服务、批处理、缓存、超时和故障恢复如何设计。
5. 效果证据。 报告基线、数据集、样本量、指标定义、消融实验和线上口径。准确率、任务成功率、P95 延迟和成本等数字必须能追溯到实验或日志，不能把估计值包装成线上结果。

如果是 Agent 或多模态 Agent，建议把一次任务描述为：

$\text{Input}\rightarrow\text{Perception}\rightarrow\text{Plan} \rightarrow\text{Tool/Model Action}\rightarrow\text{Observation} \rightarrow\text{Verification}\rightarrow\text{Final Result}$

重点讲清模型负责生成候选决策，代码负责权限、schema、状态、预算和副作用控制。面试官继续追问时，可以具体展开一个最难的 badcase：它发生在哪一层，如何定位，尝试过哪些方案，最终用什么对照实验证明修复有效。这样项目深挖回答的是设计判断和工程归因，而不是框架名称。

训练目标与持续学习

2.ppo和grpo的区别

回答：

PPO 和 GRPO 都属于基于策略优化的强化学习方法，但关键差异在于优势估计和是否需要独立的 Critic/Value Model。

PPO 通常维护当前策略 $\pi_\theta$、冻结参考策略 $\pi_{ref}$、奖励模型以及价值模型。对采样轨迹计算回报和优势 $A_t$，然后用裁剪目标限制策略更新幅度：

$L^{CLIP}(\theta)= \mathbb{E}_t\left[ \min\left(r_t(\theta)A_t, \operatorname{clip}(r_t(\theta),1-\epsilon,1+\epsilon)A_t\right) \right]$

其中

$r_t(\theta)=\frac{\pi_\theta(a_t|s_t)}{\pi_{old}(a_t|s_t)}.$

PPO 的优势是优势估计较细，可以利用 token 级或时间步级 value；代价是需要训练和维护 Critic，显存、通信和训练稳定性成本较高。对语言模型还要加入相对参考模型的 KL 约束，防止策略偏离 SFT 能力过快。

GRPO 的典型做法是对同一个 prompt 采样一组回答，得到组内奖励 $r_{i,1},\ldots,r_{i,G}$，用组内均值和标准差构造相对优势：

$A_{i,j}=\frac{r_{i,j}-\operatorname{mean}(r_i)} {\operatorname{std}(r_i)+\epsilon}.$

它不依赖单独的 Critic，而是用同一问题的组内相对表现近似优势，因此降低了 value model 的显存与拟合成本，特别适合数学、代码、结构化工具调用等有可验证 reward 的任务。代价是每个 prompt 需要生成多个 response，Rollout 成本高；如果一组回答奖励几乎相同，优势信号接近 0；奖励模型或规则不可靠时，组内排序会把错误偏好放大。

两者都不是“天然稳定”或“只适合某种模型”。实际选择要看 reward 是否可验证、Rollout 吞吐、Critic 成本、轨迹长度和任务方差。工程上还要监控 KL、clip fraction、奖励分布、组内方差、长度偏置、熵、任务成功率和通用能力。对于工具调用或多模态任务，reward 最好拆成格式合法、工具正确、任务完成、事实一致和安全等信号，不能只用一个模糊的模型评分。

3.为什么要做dpo

回答：

DPO 的动机是：很多场景能够收集“同一个 prompt 下回答 A 比回答 B 好”的偏好数据，但直接做 PPO 需要在线 rollout、Reward Model、Value Model 和复杂的稳定性控制。DPO 从 KL 正则化 RLHF 的最优策略形式出发，消去显式奖励模型，直接用偏好对训练策略。

数据为 $(x,y_w,y_l)$，其中 $y_w$ 是 chosen，$y_l$ 是 rejected。DPO 的核心目标是：

$\mathcal{L}{DPO}(\theta)= -\log\sigma\left(\beta\left[ \log\frac{\pi\theta(y_w|x)}{\pi_{ref}(y_w|x)} -\log\frac{\pi_\theta(y_l|x)}{\pi_{ref}(y_l|x)} \right]\right).$

训练时使用策略模型和冻结参考模型对 chosen/rejected 做 teacher forcing，只累计 completion token 的对数概率，不把 prompt、padding 或错误的 mask 算进回答概率。DPO 的核心是提高策略相对于参考模型对 chosen 的偏好，同时降低对 rejected 的相对偏好；$\beta$ 控制偏离参考模型的尺度。

做 DPO 的主要价值有三点：

1. 不需要显式训练 Reward Model 和 Critic，训练链路更短、调参更直接；
2. 不需要每轮与真实环境在线交互，成本和工程复杂度较低；
3. 对风格、帮助性、格式、拒答和偏好排序等离线偏好任务比较实用。

但 DPO 不是免费午餐。它受偏好数据覆盖、标注一致性、chosen/rejected 质量和参考模型能力限制；如果数据存在长度偏好、位置偏好或标注者偏差，模型会学习这些伪相关；如果任务需要多步工具交互或环境反馈，静态回答偏好未必能教会正确的行动策略。实践中应同时评估偏好准确率、事实性、安全性、长度分布、KL 漂移、通用能力和真实任务成功率，并根据问题选择 DPO、IPO、KTO、ORPO 或在线 RL，而不是把 DPO 当作所有对齐问题的默认答案。

4.持续学习方法的分类

回答：

持续学习是让模型在数据分布、任务或知识不断变化时吸收新信息，同时尽量不破坏旧能力。它与简单地周期性重新训练不同，核心矛盾是“适应新分布”和“避免灾难性遗忘”。可以按记忆、参数更新和模型结构分为几类：

1. 基于回放（Replay-based）。 保存历史样本、原型、特征或生成式旧样本，在训练新数据时混合回放。优点是直接约束旧任务，缺点是存储、隐私、采样比例和数据时效需要管理。企业场景中常用脱敏 replay buffer 和困难样本优先回放。
2. 基于正则化（Regularization-based）。 用参数重要性约束新任务不要大幅改变对旧任务重要的参数，例如 EWC；也可以用旧模型 logits、表示或输出分布做蒸馏。优点是模型结构不变，缺点是重要性估计可能失真，任务差异大时会限制新能力。
3. 基于参数隔离或适配器。 为不同领域、租户或时间段维护 LoRA/Adapter、Prompt 参数或专家模块，推理时选择或融合对应模块。它降低了旧知识被覆盖的风险，但会带来适配器管理、路由、组合冲突和部署内存成本。
4. 基于架构扩展。 增加新专家、新头或新模块，把新能力放到独立参数空间。容量更灵活，但需要解决路由、负载均衡、版本治理和模型规模膨胀。
5. 基于检索与外部记忆。 不立即修改模型参数，而是把新知识写入文档库、向量库、数据库或结构化记忆，通过 RAG/工具在推理时取回。它更新快、可追溯，适合时效性知识；但不能替代模型对新行为模式的学习，仍要处理召回、权限、冲突和过期。
6. 周期性重训或增量预训练。 定期合并新旧数据进行 continued pretraining、SFT 或偏好优化。质量上限较高，但计算成本大，数据混合、版本回滚和遗忘评估不可省略。

选型要先判断变化的是知识、行为、任务还是输入分布：知识更新优先考虑检索；格式和行为变化可以考虑 SFT/Adapter/DPO；需要学习可验证长链路策略才考虑 RL；数据分布变化则要做回放、重加权和漂移监控。每次更新都要在新域、旧域、对抗集和安全集上做回归，使用旧能力保留率、增量收益、遗忘量、成本和延迟联合决策。

训练与推理加速

5.场景题：用8张a100的机器做7B vl模型的grpo训练如何训练加速，推理加速

回答：

这道题应先明确瓶颈。GRPO 对每个 prompt 需要生成一组回答，再计算 reward、优势和策略梯度；对 7B VL 模型，视觉编码、长图像 token、生成阶段 KV Cache 和训练阶段显存/通信都可能成为瓶颈。通常先用 profiler 测量 Rollout、视觉编码、训练 forward/backward、reward、All-Reduce/All-to-All 和 GPU 空闲时间，再决定优化顺序。

推理与 Rollout 加速

1. 使用支持批处理和 KV Cache 管理的推理引擎，例如 vLLM 或 SGLang；PagedAttention 主要解决 KV Cache 的分页管理和碎片问题，Continuous Batching 让不同请求动态加入/退出，提高 GPU 利用率。
2. 根据模型结构选择 Tensor Parallel 或其他并行策略，确保视觉编码器、语言模型和生成服务的切分方式与 A100 的显存和互联拓扑匹配。不能只写“上 TP”，还要观察通信比例和小 batch 下的收益。
3. 限制无效生成：设置合理的 max_new_tokens、停止条件、结构化输出约束和长度预算；对明显重复或格式非法的轨迹尽早终止。减少 group size 可以降低 Rollout 量，但会改变组内优势估计的方差，必须用任务成功率和训练稳定性验证，不能只追求吞吐。
4. 复用同一 prompt 的视觉特征和前缀 KV Cache，避免每个 group response 重复计算完全相同的图像编码与 prompt 前缀。缓存必须按模型版本、图像处理配置、租户和输入哈希隔离。
5. 采用 BF16 推理、FlashAttention/FlashInfer 等 fused kernel，在 A100 上结合 CUDA Graph、算子融合和合适的 batch size；对长图像可以使用动态分辨率、patch merge 或视觉 token 压缩，但要验证视觉理解质量。
6. 将 rollout、reward 计算和训练解耦或流水化。可采用部分 GPU 做 Rollout、部分 GPU 做训练，也可在同一组 GPU 上做时间片复用；关键是减少“训练等 rollout、rollout 等训练”的空转。异步策略必须处理策略版本、过期样本和 off-policy 程度，不能无条件混用旧策略生成的样本。

训练加速

1. 使用 BF16、FlashAttention、fused optimizer 和通信计算 overlap；TF32 主要影响 FP32 矩阵乘法路径，不能把它当作 BF16 的替代品。
2. 用 FSDP 或 DeepSpeed ZeRO 分片参数、梯度和优化器状态，结合 gradient accumulation 获得足够的有效 batch。Gradient Checkpointing 用额外重计算换显存，适合长序列，但会增加计算时间，应通过 profiler 判断收益。
3. 做 sequence packing 或长度分桶，减少 padding；多模态 batch 还需按图片 token 数、文本长度和生成长度分桶，否则一个超长样本会拖慢整批。
4. 控制全局 batch、mini-batch、group size、生成长度和 reward 计算频率，避免为了增大 batch 造成显存溢出或通信饱和。GRPO 的有效样本量不能只看 prompt 数，还要看每个 prompt 的 response 数和有效 token 数。
5. 用 NCCL 拓扑、梯度桶大小、通信 overlap、持久化 worker 和预分配显存降低同步开销；保存 checkpoint 时异步写盘，避免训练线程长时间阻塞。

验收方式

优化前后至少记录：tokens/s、有效 response/s、端到端 step time、GPU 利用率、显存峰值、通信占比、reward 计算时间、训练吞吐、任务成功率、KL、组内 reward 方差和单样本成本。对于 8 张 A100，没有完整模型配置、图像尺寸、序列长度、并行策略和 group size 时，不能直接承诺某个固定加速倍数。正确的回答是先定位瓶颈，再做单变量消融，确认吞吐提升没有以视觉质量、训练稳定性或策略新鲜度为代价。

6.模型训练加速有什么方法

回答：

训练加速可以按“减少计算量、减少显存、减少通信、提高流水线利用率、减少无效数据”五个方向组织。

1. 精度与算子。 使用 BF16/FP16 混合精度、TF32 的适用路径、FlashAttention、fused activation、fused optimizer、CUDA Graph 和 kernel fusion。混合精度要配合 loss scaling 或框架的数值稳定策略，并监控溢出、梯度范数和 loss 是否异常。
2. 显存优化。 Gradient Checkpointing、Activation Offload、参数/梯度/优化器分片、KV 或中间激活重用。Checkpointing 不是无成本加速，它通过重算降低显存，通常是用显存换算力。
3. 并行训练。 Data Parallel 复制模型处理不同 batch；Tensor Parallel 切分层内矩阵；Pipeline Parallel 按层切分并用 micro-batch 填充流水线；Sequence Parallel 减少长序列激活压力；MoE 还需要 Expert Parallel 和 All-to-All。混合并行要结合模型尺寸、序列长度、GPU 互联和 batch 形态选择。
4. 通信优化。 梯度桶化、通信计算重叠、梯度累积减少同步频率、合理设置 NCCL、拓扑感知的设备映射和分层通信。多卡加速不等于线性加速，通信时间、负载不均衡和 pipeline bubble 都要纳入分析。
5. 数据与序列。 清洗重复和无效样本、packing、长度分桶、动态 batch、异步预取、缓存 tokenizer/视觉特征、减少 padding。数据读取和 CPU 预处理跟不上时，GPU 再快也会空转。
6. 训练策略。 选择合适的 global batch、学习率调度、梯度累积、参数高效微调、冻结部分模块和 curriculum。若只需领域适配，LoRA/QLoRA 可能比全量训练更经济；但它不是普适的速度提升，目标模块、量化反量化和小 batch kernel 效率都要实测。
7. 系统与工程。 使用高效 checkpoint、断点续训、异步日志、持久化进程、预分配内存和 profiler；通过 Nsight Systems、PyTorch Profiler、训练框架 trace 分辨计算、内存、通信、I/O 和同步瓶颈。

一个有说服力的优化闭环是：先建立固定 batch 和数据版本的基线，记录 step time 分解；每次只改一个变量；同时报告吞吐、峰值显存、数值稳定性和验证集效果；最后在目标硬件和真实数据分布上复测。不能只报单卡 FLOPS 或 GPU 利用率，因为无效 token 增多时 GPU 利用率可能上升，任务质量却下降。

7.deepspeed的三个阶段

回答：

这里通常指 DeepSpeed ZeRO 的三个阶段。它们都利用数据并行，但逐步减少每张 GPU 必须完整保存的训练状态：

阶段	分片对象	每张 GPU 仍保留
ZeRO-1	优化器状态	完整模型参数与完整梯度
ZeRO-2	优化器状态、梯度	完整模型参数
ZeRO-3	优化器状态、梯度、模型参数	当前计算所需的参数分片或临时聚合

设参数量为 $P$，混合精度训练还需保存参数、梯度和优化器状态，朴素数据并行中每卡都复制这些内容；ZeRO 通过在 $D$ 张卡之间分片，使理想状态下每卡的持久化状态规模近似按 $1/D$ 缩减，但实际还会有通信 buffer、临时 all-gather、激活和框架开销。

ZeRO-1 通信和实现风险较低，适合优化器状态占比很大的训练；ZeRO-2 进一步节省梯度显存；ZeRO-3 最省显存，可训练更大的模型，但参数在层计算前后需要聚合和释放，通信、配置复杂度和小 batch 性能代价更高。ZeRO-Infinity 还可以把部分状态卸载到 CPU/NVMe，但会受 PCIe、内存带宽和 I/O 影响。

需要区分 ZeRO 与 Tensor Parallel、Pipeline Parallel：ZeRO 主要分片数据并行中的训练状态，TP/PP 主要切分模型计算和层；它们可以组合。选择时要综合模型大小、序列长度、GPU 数量、互联带宽、checkpoint 需求和吞吐目标，而不是默认 ZeRO-3 一定最好。

注意力与框架工程

8.多头注意力的变体有什么

回答：

标准 Multi-Head Attention（MHA）为每个 Query 头配置独立的 Key/Value 头。设 Query 头数为 $H_q$，Key/Value 头数为 $H_{kv}$：

• MHA： $H_q=H_{kv}$。表达能力完整，但自回归推理需要缓存最多的 K/V，显存和带宽开销大。
• MQA： $H_{kv}=1$。所有 Query 头共享一组 K/V，KV Cache 显著缩小，解码更快，但过度共享可能损失质量。
• GQA： $1<H_{kv}<H_q$。多个 Query 头分组共享一个 K/V 头，是质量、缓存和带宽之间常见的折中。每个 KV 头对应 $H_q/H_{kv}$ 个 Query 头。
• MQA/GQA 的 KV 头扩展： 计算时把较少的 K/V 头按组广播给 Query 头，数学上仍是缩放点积注意力，主要变化在参数组织和缓存布局。
• MLA（Multi-head Latent Attention）： 不直接缓存完整的每头 K/V，而是缓存低维 latent 表示，并在需要时结合 Query 投影重建注意力所需信息，从而在长上下文和高并发下进一步降低 KV Cache 压力。它不是简单把 GQA 的 KV 头数设为更小，具体结构还涉及低秩投影和位置编码设计。
• 局部/滑动窗口注意力： 每个 token 只关注局部窗口，降低长序列计算量，但会牺牲远距离直接交互，需要全局 token、稀疏连接或层间传播补足。
• 稀疏、块稀疏和线性注意力： 通过限制连接模式或改变计算形式减少 $O(S^2)$ 成本，适合特定长度和任务分布，但需要硬件 kernel、质量和训练稳定性共同验证。

注意力变体的本质是同时改变三件事：表示能力、每 token 的 KV 状态大小和矩阵乘法/访存模式。自回归解码的主要瓶颈往往不是 QKV 投影本身，而是每一步读取历史 K/V 的显存带宽，因此降低 KV Cache 可以带来明显收益；但在短序列、大 batch 或 prefill 阶段，计算和并行度的权衡可能不同。回答时要区分 prefill 与 decode，不能笼统说“所有场景 GQA 都更快”。

9.verl等框架都如何进行加速的

回答：

以 verl 这类 LLM/Agent 强化学习框架为例，加速重点不是一个神奇算子，而是把 Rollout、Reward、训练更新和数据调度组织成高吞吐系统。不同版本和配置的实现会变化，因此应按公开能力和实际配置说明，不应随意承诺固定版本或倍数。

主要机制包括：

1. Hybrid Engine。 在训练与生成之间复用或切换模型权重，减少重复加载和 GPU 空闲。可以采用 colocated 方式在同一批 GPU 上调度，也可以把 Rollout 与 Trainer 分离到不同 GPU 资源池；前者节省资源，后者更容易隔离吞吐，但需要处理权重同步和资源利用率。
2. 高效 Rollout。 对接 vLLM、SGLang 等推理后端，利用 Continuous Batching、Paged KV Cache、prefix caching、张量并行和高效采样；对 GRPO 通过批量生成同一 prompt 的多条 response，提高生成阶段的 GPU 利用率。
3. 训练后端优化。 对接 FSDP、Megatron 或其他分布式训练后端，使用参数/梯度/优化器分片、混合精度、梯度累积、sequence packing、激活重计算和通信计算 overlap。
4. 异步与流水化。 Rollout、Reward、数据传输和训练可以流水并行，减少阶段间互相等待。异步训练要记录 policy version，控制样本陈旧度，必要时丢弃过旧轨迹，避免吞吐提升却破坏训练目标。
5. 数据与长度管理。 按 prompt 长度、response 长度、图片 token 数分桶，动态 batch，减少 padding；设置最大生成长度和停止条件，避免把大量计算浪费在无效轨迹上。
6. 通信和内存。 预分配 buffer、减少 CPU-GPU 拷贝、使用 pinned memory、优化 NCCL 拓扑和通信 bucket；模型权重、KV Cache、奖励结果和训练 batch 的生命周期要明确，避免显存碎片。
7. 可观测性。 分别统计生成 tokens/s、训练 tokens/s、reward 延迟、权重同步时间、GPU 空闲比例、通信占比、样本陈旧度、有效 batch 和端到端 step time。只有找到具体瓶颈，才能判断某项优化是否真正有效。

对 8 张 A100 的小规模集群，常见优先级是先确认 rollout 是否主导耗时，再选择 colocate 或 disaggregate；随后按模型大小和序列长度选择 FSDP/Megatron、TP/DP 和 checkpoint；最后优化 kernel、packing 和通信。任何“减少 group size”“训练推理解耦”都需要与 reward 方差、样本新鲜度、最终任务质量一起验证。

手撕题

手撕：MHA

回答：

设输入 query、key、value 的形状分别为 [B, Lq, D]、[B, Lk, D]、[B, Lv, D]，在标准注意力中要求 Lk == Lv。头数为 H，每头维度为 Dh = D / H。计算过程为：

$Q=XW_Q,\quad K=XW_K,\quad V=XW_V,$

$\operatorname{Attention}(Q,K,V)= \operatorname{softmax}\left(\frac{QK^{\mathsf T}}{\sqrt{D_h}}+M\right)V.$

下面实现支持 Self-Attention 和 Cross-Attention，mask=True 表示允许关注，mask 可广播到 [B, H, Lq, Lk]。因果 mask 只适用于 Self-Attention 或明确给出对应的 query/key 位置关系。

import math
from typing import Optional

import torch
from torch import Tensor, nn

class MultiHeadAttention(nn.Module):
    def __init__(self, d_model: int, num_heads: int, dropout: float = 0.0):
        super().__init__()
        if d_model <= 0 or d_model % num_heads != 0:
            raise ValueError("d_model must be divisible by num_heads")
        self.d_model = d_model
        self.num_heads = num_heads
        self.head_dim = d_model // num_heads
        self.q_proj = nn.Linear(d_model, d_model)
        self.k_proj = nn.Linear(d_model, d_model)
        self.v_proj = nn.Linear(d_model, d_model)
        self.out_proj = nn.Linear(d_model, d_model)
        self.dropout = nn.Dropout(dropout)

    def forward(
        self,
        query: Tensor,
        key: Tensor,
        value: Tensor,
        mask: Optional[Tensor] = None,
        causal: bool = False,
    ) -> Tensor:
        batch, query_len, _ = query.shape
        _, key_len, _ = key.shape
        if value.shape[:2] != (batch, key_len):
            raise ValueError("key and value must have the same batch and length")

        q = self.q_proj(query).view(batch, query_len, self.num_heads, self.head_dim)
        k = self.k_proj(key).view(batch, key_len, self.num_heads, self.head_dim)
        v = self.v_proj(value).view(batch, key_len, self.num_heads, self.head_dim)
        q = q.transpose(1, 2)  # [B, H, Lq, Dh]
        k = k.transpose(1, 2)  # [B, H, Lk, Dh]
        v = v.transpose(1, 2)  # [B, H, Lk, Dh]

        scores = torch.matmul(q, k.transpose(-2, -1)) / math.sqrt(self.head_dim)
        if causal:
            if query_len != key_len:
                raise ValueError("this simple causal mask expects self-attention")
            causal_mask = torch.ones(
                query_len, key_len, dtype=torch.bool, device=query.device
            ).tril()
            scores = scores.masked_fill(~causal_mask, torch.finfo(scores.dtype).min)
        if mask is not None:
            scores = scores.masked_fill(~mask.to(torch.bool), torch.finfo(scores.dtype).min)

        # Float32 softmax is more stable for low-precision training.
        weights = torch.softmax(scores.float(), dim=-1).to(scores.dtype)
        weights = self.dropout(weights)
        output = torch.matmul(weights, v)
        output = output.transpose(1, 2).contiguous().view(batch, query_len, self.d_model)
        return self.out_proj(output)

复杂度为 $O(BHL_qL_kD_h)$，即 $O(BL_qL_kD)$ 的注意力矩阵计算，注意力权重额外占用 $O(BHL_qL_k)$ 空间。面试中还要主动指出：缩放因子应使用 sqrt(head_dim) 而不是 sqrt(d_model)；转置后合并维度前要 contiguous()；mask 的语义、dtype 和广播形状要明确；现代实现可用 torch.nn.functional.scaled_dot_product_attention 或 FlashAttention，但不能因此省略数学和张量形状。

查找两个正序数组的中位数

回答：

设两个正序数组分别为 A 和 B，长度为 m、n。目标是在不真正合并数组的情况下找到第 (m+n+1)/2 小和第 (m+n+2)/2 小的元素。最优方法是在较短数组上二分切分位置。

选择切分 i 个元素来自 A，则需要 j = half - i 个元素来自 B。合法切分要求：

$A[i-1]\le B[j]\quad\text{且}\quad B[j-1]\le A[i].$

其中越界左值视为 $-\infty$，越界右值视为 $+\infty$。找到合法切分后，左半部分最大值为 $\max(A[i-1],B[j-1])$，右半部分最小值为 $\min(A[i],B[j])$。总长度为奇数时取左最大值，为偶数时取左右平均值。

from typing import List

def find_median_sorted_arrays(a: List[int], b: List[int]) -> float:
    if len(a) > len(b):
        a, b = b, a
    m, n = len(a), len(b)
    if m + n == 0:
        raise ValueError("both arrays cannot be empty")

    left, right = 0, m
    half = (m + n + 1) // 2
    neg_inf = float("-inf")
    pos_inf = float("inf")

    while left <= right:
        i = (left + right) // 2
        j = half - i
        a_left = neg_inf if i == 0 else a[i - 1]
        a_right = pos_inf if i == m else a[i]
        b_left = neg_inf if j == 0 else b[j - 1]
        b_right = pos_inf if j == n else b[j]

        if a_left > b_right:
            right = i - 1
        elif b_left > a_right:
            left = i + 1
        else:
            left_max = max(a_left, b_left)
            if (m + n) % 2 == 1:
                return float(left_max)
            right_min = min(a_right, b_right)
            return (left_max + right_min) / 2.0

    raise ValueError("input arrays are not sorted")

二分发生在较短数组上，因此时间复杂度为 $O(\log\min(m,n))$，额外空间复杂度为 $O(1)$。边界包括一个数组为空、两个数组都为空、重复元素、负数和总长度为偶数。不能只用双指针合并到中点后宣称最优，那样时间复杂度是 $O(m+n)$；如果面试官只要求普通实现，双指针可接受，但应说明这是线性方案。