题目重点：Uber Senior MLE 面经中的二维 k 个 Shuttle 上车点选址题。区分 k=1 的坐标中位数解、k>1 的分组与选址耦合、精确搜索和可解释迭代近似。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 目标函数为 Σ_i min_j (|x_i−cx_j|+|y_i−cy_j|)，每人被最近的一个上车点服务。本文基础版允许上车点位于平面任意坐标。
- 题目未说明上车点是否只能设在道路、公交站或已有用户位置；若有限制，坐标中位数未必可行，需要在允许的候选集合中优化。
- K 为 1..N；同距离的分配可用固定中心 ID 破平局。允许空中心时需定义重播种策略，不把空组的中心当作额外改进。
解题路线
- 先解 K=1：L1 距离按 x、y 分离，分别取 x 坐标和 y 坐标的中位数即可全局最优；偶数人数可在中间两值之间任取。
- K>1 时，分配到哪个中心与中心位置相互依赖。小 N/K 可枚举用户到 K 组的分配；给定每组成员后分别取该组 x/y 中位数，计算总成本，取最小。枚举指数增长，只用于规模较小的确切答案。
- 大规模可初始化多个候选中心，反复执行‘按 L1 最近中心分配用户→每组坐标中位数重定位’，多次不同初始化并保留目标最低结果；每轮不会增加目标，但只保证局部解。
手动走一遍
K=1，五人坐标 (0,1)、(1,0)、(2,2)、(0,2)、(2,0)，x 中位数 1、y 中位数 1，最优上车点 (1,1) 并非任一用户位置。K=2 时必须同时考虑如何把人分成两组，不能独立取全体的两个中位数。
规模与取舍
K=1 排序坐标 O(N log N) 时间、O(N) 空间，选择算法可降期望 O(N)。朴素枚举 K^N 个分配，每个分配求组中位数与目标，最坏指数级。迭代近似每轮分配 O(NK)，按组求中位数若排序 O(N log N)，运行 I 轮约 O(I(NK+N log N))，另乘重启次数。
易错点与追问
容易失分的边界
- 二维 L1 的单中心解是坐标分别取中位数，不是平均值；平方 L2 距离才引出均值。
- 只允许选某个用户坐标会把候选集缩小，平面 L1 最优点可能是不同用户的 x/y 组合。
- 迭代分配/中位数类似 k-median 的局部优化，不能因为每轮目标下降就声称全局最优。
继续深挖
- 若上车点必须在道路网络或安全候车点，先生成合法候选，再在道路距离/可达性约束下做离散选址；平面 Manhattan 距离不再足够。
- 若有每站容量或乘客最大步行距离，分配步骤成为容量约束匹配/优化，不能只按每人最近点独立分配。
