题目重点：DoorDash Phone Coding 面经题：在共用 x 或 y 的城市中找最近者，距离相同按城市名破平局，含同坐标与无结果边界。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 城市名非空且唯一；查询给已有城市名。可见题目未说明同坐标城市是否允许，示例实现允许不同名字共享同一坐标，并将距离 0 视为最优候选。
- 共用 x 时距离为 |Δy|，共用 y 时距离为 |Δx|；这与曼哈顿距离在资格约束下相同。查询城市自身不计候选。
- 没有合格城市返回 None。题目未明确无结果的输出字符串或错误码，面试时要与函数签名确认。
解题路线
- 预处理两套分组索引：按 x 分组后按 (y,name) 排序，按 y 分组后按 (x,name) 排序。每组分别保留坐标数组和对应名字。
- 查询城市时，在固定 x 组按 y 二分，在固定 y 组按 x 二分。对每组只需比较同坐标的字典序最小其他城市、前一不同坐标组和后一不同坐标组。
- 前一坐标组可能有多个同距城市，因此再二分到该组开头取字典序最小名字；所有候选按 (距离,名字) 比较。
手动走一遍
A=(2,3)、B=(2,8)、C=(7,3)、D=(2,8)；查询 A 时 B/D 距离 5，C 距离 5，取名字最小的 B。查询 B 时 D 与它同坐标、距离 0，因此取 D。只有 A 一座城时返回 None。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""Nearest city sharing x or y, with name tie-breaking."""
from bisect import bisect_left, bisect_right
from collections import defaultdict
class CityIndex:
def __init__(self, cities: list[tuple[str, int, int]]) -> None:
self.points: dict[str, tuple[int, int]] = {}
by_x: dict[int, list[tuple[int, str]]] = defaultdict(list)
by_y: dict[int, list[tuple[int, str]]] = defaultdict(list)
for name, x, y in cities:
if not name or name in self.points:
raise ValueError("city names must be nonempty and unique")
self.points[name] = (x, y)
by_x[x].append((y, name))
by_y[y].append((x, name))
self.by_x = {key: self._ordered(items) for key, items in by_x.items()}
self.by_y = {key: self._ordered(items) for key, items in by_y.items()}
@staticmethod
def _ordered(items: list[tuple[int, str]]) -> tuple[list[int], list[str]]:
items.sort()
return [coord for coord, _ in items], [name for _, name in items]
@staticmethod
def _nearby(group: tuple[list[int], list[str]], coord: int, own_name: str) -> list[tuple[int, str]]:
values, names = group
lo = bisect_left(values, coord)
hi = bisect_right(values, coord)
candidates: list[tuple[int, str]] = []
# All cities at the same coordinate are distance zero; names are sorted.
if hi - lo > 1:
first = lo if names[lo] != own_name else lo + 1
candidates.append((0, names[first]))
if lo > 0:
previous_coord = values[lo - 1]
first_previous = bisect_left(values, previous_coord)
candidates.append((coord - previous_coord, names[first_previous]))
if hi < len(values):
candidates.append((values[hi] - coord, names[hi]))
return candidates
def nearest(self, name: str) -> str | None:
x, y = self.points[name]
candidates = self._nearby(self.by_x[x], y, name)
candidates += self._nearby(self.by_y[y], x, name)
return min(candidates)[1] if candidates else None
复杂度
n 座城市的预处理排序 O(n log n) 时间、O(n) 空间。每次查询在两组中做常数次二分，为 O(log n) 时间；暴力逐城检查为每次 O(n)。
易错点与追问
容易失分的边界
- 只看排序数组里的紧邻元素会在多个城市共用同一坐标时错过同距但名字更小的城市；要定位整个坐标组的起点。
- 同时共用 x 与 y 的另一个城市距离 0，不能因为坐标相同就当作查询城市本身排除；应按城市名区分。
- 若未先按固定 x/y 分组，直接对全部城市按 x 或 y 二分可能把不共线城市纳入候选。
继续深挖
- 若频繁新增/删除城市，静态排序数组的维护是 O(n)；改用每个 x/y 分组的有序树，并维护同坐标名字集合，查询 O(log n)、更新 O(log n) 量级。
- 若查询是任意坐标而非已有城市，仍可查 x/y 两组，但要重新定义自身排除和无匹配城市的返回契约。
