zero2algo

算法面试 / 04

排序链路与系统设计题

排序系统设计是推荐、搜索、广告面试的高频大题。面试官不是只想听模型结构，而是想看你能不能设计一条可上线的排序链路。

标准链路

常见排序链路：

候选生成 -> 召回 -> 粗排 -> 精排 -> 重排 -> 过滤 -> 展示 -> 反馈

每一层解决的问题不同。

召回

召回负责从海量物料中找候选。常见召回包括：

  • 协同过滤召回。
  • 向量召回。
  • 热门召回。
  • 类目召回。
  • 关注 / 社交召回。
  • 搜索 query 召回。
  • 规则召回。

召回关注覆盖率、相关性、延迟和多样性。召回漏掉的东西，后面排序再强也没用。

粗排

粗排用于在较大的候选集中快速筛出较优物料。它需要比召回更准，但比精排更快。

粗排模型通常特征少、结构轻，目标是低延迟下保留精排可能喜欢的候选。

面试可强调：

  • 粗排不是精排的简化复制。
  • 粗排要优化 top 候选保留率。
  • 粗排和精排之间要避免目标不一致。

精排

精排使用更丰富的用户、物料、上下文、交叉和序列特征，预测点击、转化、停留、互动等目标。

常见模型：

  • LR / GBDT。
  • Wide & Deep。
  • DeepFM。
  • DIN / DIEN。
  • DCN。
  • Transformer 序列模型。

面试时不要只背结构，要讲为什么选它：是否需要特征交叉，是否需要行为序列，是否需要多目标。

重排

重排负责处理精排分数之外的业务约束：

  • 多样性。
  • 新颖性。
  • 频控。
  • 去重。
  • 内容安全。
  • 商业目标。
  • 生态平衡。

很多线上收益来自重排策略，而不是模型本身。

特征服务

系统设计题一定要讲特征。

特征分三类：

  • 离线特征：历史统计、长期画像。
  • 实时特征：最近点击、当前 session、实时位置。
  • 上下文特征：时间、地点、设备、流量入口。

要关注训练和线上一致性、特征延迟、缺失值、版本管理和监控。

多目标排序

业务排序很少只优化点击。常见目标包括点击、转化、停留、GMV、投诉、留存、广告收入。

多目标处理方式：

  • 多任务学习。
  • 加权融合。
  • 分层排序。
  • 约束优化。
  • 重排阶段做规则控制。

回答时要说清主目标和护栏指标。

系统设计回答框架

遇到“设计一个推荐系统”：

  1. 明确业务场景：内容、电商、广告、搜索。
  2. 明确目标指标：点击、转化、GMV、留存。
  3. 设计召回：多路召回和候选覆盖。
  4. 设计排序：粗排、精排、多目标。
  5. 设计重排：多样性、规则、生态。
  6. 设计数据闭环：日志、样本、特征、训练。
  7. 设计实验监控：A/B、延迟、分布漂移。

高频追问

召回怎么评估？

看 recall@K、覆盖率、命中精排 top 的比例、多样性、延迟和不同人群覆盖。不能只看整体召回率。

精排 AUC 涨了，线上不涨怎么办？

看 top 区间变化、校准、策略覆盖、特征一致性、样本偏差、多目标冲突和实验分层。

如何做冷启动？

新用户用上下文、热门、地域、入口和探索；新物料用内容特征、作者特征、相似物料、少量探索流量和质量预估。

如何做多样性？

可以在重排阶段加类目、作者、主题、价格带、内容类型等约束，也可以用 MMR、DPP 或业务规则。

一段标准回答

我会把排序系统拆成召回、粗排、精排和重排。召回保证覆盖和多样性，粗排在低延迟下筛候选，精排用丰富特征做多目标预估，重排处理多样性、频控和业务约束。上线前看离线排序指标和关键分桶，线上通过 A/B 验证主指标和护栏指标，同时监控特征分布、模型分数和链路延迟。

调度与系统设计（物流场景）

Q：请建立一个骑手排班优化模型（数学形式），同时满足：覆盖预测订单量、骑手工时上限、区域均衡三个约束。如何求解？

来源：阿里巴巴 / 算法工程师 - 运筹 & 因果推断

普通回答：用整数规划建模，用 solver 求解。

更好的回答：

建模框架（整数规划）：

  • 决策变量：x[i,t,z] = 骑手 i 在时段 t 区域 z 是否上线（0/1）
  • 目标：最小化排班成本或最大化覆盖率
  • 约束：① ∑ capacity(x) ≥ demand_forecast[t,z]（覆盖）；② ∑_t x[i,t,z] ≤ max_hours（工时）；③ 区域覆盖骑手数差异 ≤ ε（均衡）

求解方法：

  • 小规模：精确求解（CBC / Gurobi / CPLEX）。
  • 大规模：列生成法、拉格朗日松弛（将工时约束拉入目标函数）。
  • 实时场景：将 IP 松弛为 LP + 启发式修复，或用强化学习替代部分求解。

工程挑战：需求预测不确定性（鲁棒优化 / 随机规划）、动态骑手池变化（滚动优化窗口）。

考察点：能否把业务需求抽象成完整的数学优化问题，并根据规模选择合适的求解策略。

Q：请解释旅行商问题（TSP）与骑手多订单路径规划（VRP）的关系，并说明即时配送场景下 VRP 有哪些特殊约束？

来源：阿里巴巴 / 算法工程师 - 运筹 & 因果推断

普通回答：VRP 是 TSP 的多车辆版本。

更好的回答：

VRP 是 TSP 的推广：TSP 是单辆车访问所有节点，VRP 是多辆车分配配送任务，TSP 是 VRP 的特殊情况（车辆数 = 1）。

即时配送的特殊约束：

  1. 时间窗（VRPTW）：用户预计送达时间约束，骑手必须在窗口内到达。
  2. 动态订单：订单实时插入，需要在线算法而非离线批量求解。
  3. 取送同路（Pickup & Delivery）：骑手要先去餐厅取餐再送达，顺序不可颠倒。
  4. 骑手容量和载荷：同时携带订单数上限。
  5. 不确定性：行驶时间随实时路况变化（随机 VRP）。

考察点：对经典运筹问题的理解，以及能否把理论模型映射到物流业务的真实约束中。

Q：如何设计一个骑手 ETA（预计送达时间）预估模型？请从特征工程、模型选型到线上服务全链路说明。

来源：阿里巴巴 / 算法工程师 - 运筹 & 因果推断

普通回答：用 LightGBM 预测送达时间。

更好的回答：

特征工程：路径距离（直线 / 导航距离）、实时路况、历史骑手速度画像、订单数量和重量、时段和天气、商家出餐时间预估、当前骑手位置。

模型选型：

  • 基础：XGBoost / LightGBM（可解释、快速迭代）。
  • 进阶：图神经网络（建模路网结构）+ Transformer（建模骑手历史轨迹序列）。
  • 不确定性估计：分位数回归（输出 P50 / P80 / P90）、Conformal Prediction。

线上服务：模型离线训练 → ONNX / TorchScript 导出 → 特征实时拼接（Redis / Flink）→ 低延迟推理（< 50ms）→ 监控（预估偏差、分布漂移）。

难点：Train-Serving Skew（训练和线上特征一致性）、长尾场景（极端天气、节假日）。

考察点：全链路思维，不只是模型选型，还要说清特征、服务、监控和长尾处理。

Q：Transformer 的注意力机制时间复杂度是多少？在长序列骑手轨迹场景中如何优化？

来源：阿里巴巴 / 算法工程师 - 运筹 & 因果推断

普通回答：O(n²)，可以用稀疏注意力。

更好的回答：

标准 Self-Attention 的时间和空间复杂度均为 O(n²)，n 为序列长度。

优化方案：

  1. 稀疏注意力（Longformer / BigBird）：局部窗口 + 全局 token，降至 O(n)。
  2. 线性注意力（Performer / Linear Transformer）：核函数近似，O(n)。
  3. 分层聚合：将轨迹按时间段聚合为”段向量”，再做段间注意力。
  4. Flash Attention：IO-aware 算法，降低 GPU 显存访问，训练速度提升显著但不改变复杂度量级。
  5. 降采样：轨迹点按关键节点（停留点、转向点）稀疏化。

考察点：是否真正理解复杂度瓶颈的来源，以及能否针对具体业务场景选择合适的优化策略。

Q：解释 Policy Gradient 与 Q-Learning 的核心区别，各自适用什么场景？

来源：阿里巴巴 / 算法工程师 - 运筹 & 因果推断

普通回答：Q-Learning 学值函数，Policy Gradient 学策略。

更好的回答：

Q-Learning（值函数方法）：学习 Q(s,a)，取 argmax 得到策略。样本效率高，但动作空间大时 argmax 不可行，不适合连续动作空间。

Policy Gradient（策略梯度）：直接参数化策略 π(a s)，梯度上升最大化期望回报。天然支持连续和随机策略，但方差大，收敛慢。

Actor-Critic：融合两者，Actor 是策略网络，Critic 是价值函数，用 Critic 降低 Policy Gradient 方差。PPO / A3C 均属此类。

物流场景推荐：离散小动作空间（如 3 档补贴级别）→ DQN；连续出价或调度 → PPO；大规模组合动作 → 注意力 + 指针网络解码。

考察点：不只是背定义，而是能否根据物流决策场景的动作空间特点选择合适的方法。

Q：实现一个简化版骑手-订单匹配：给定 n 名空闲骑手位置和 m 个待配送订单位置（二维坐标），用最小权重二分图匹配找到总距离最小的分配方案。

来源：阿里巴巴 / 算法工程师 - 运筹 & 因果推断

普通回答：贪心选最近的骑手。

更好的回答：

from scipy.optimize import linear_sum_assignment
import numpy as np

riders = np.array([[0,0],[1,2],[3,1]])
orders = np.array([[2,2],[0,3],[3,3]])

cost = np.linalg.norm(
    riders[:, np.newaxis, :] - orders[np.newaxis, :, :], axis=2
)

row_ind, col_ind = linear_sum_assignment(cost)
print("分配:", list(zip(row_ind, col_ind)))
print("总距离:", cost[row_ind, col_ind].sum())

linear_sum_assignment 是 O(n³) 匈牙利算法实现。当 n / m 达到万级时，需要近似算法、KD 树剪枝或贪心 + 局部搜索。

考察点：二分图匹配（匈牙利算法）的理解和工程实现，以及大规模场景下的扩展思路。

下一篇建议继续看：