# DoorDash VO 面试题：最近同轴城市（Closest Straight City｜哈希表 + 排序 + 二分）
oavoservice 原创复盘：重点在“如何把候选缩到常数个”，以及 tie-break 的实现细节。
题目（改写版）
给定 n 个城市坐标：(x[i], y[i])，以及 q 个查询城市名。
对每个查询城市 c：
- 在所有 x 相同 或 y 相同 的城市里，找到与
c的曼哈顿距离最小的那个。 - 若距离相同，返回名字字典序更小的。
- 若不存在同轴城市，返回
"NONE"。
思路核心
如果每次查询都扫一遍 n，会变成 O(nq)。
优化：
- 把同一条竖线（相同 x）上的城市按 y 排序
- 把同一条横线（相同 y）上的城市按 x 排序
对查询城市，只需要在两条有序列表里找它的相邻前驱/后继，最多比较 4 个候选。
数据结构
name -> (x, y)x_map[x] = [(y, name), ...]（按 y, 再按 name 排序）y_map[y] = [(x, name), ...]（按 x, 再按 name 排序）
复杂度
- 预处理：
O(n log n) - 单次查询：
O(log n)
Python 参考实现
from bisect import bisect_left
from collections import defaultdict
def closest_straight_city(names, xs, ys, queries):
pos = {}
x_map = defaultdict(list)
y_map = defaultdict(list)
for name, x, y in zip(names, xs, ys):
pos[name] = (x, y)
x_map[x].append((y, name))
y_map[y].append((x, name))
for x in x_map:
x_map[x].sort() # (y, name)
for y in y_map:
y_map[y].sort() # (x, name)
def pick_best(candidates, x0, y0):
best = None
best_dist = None
for name, x, y in candidates:
dist = abs(x - x0) + abs(y - y0)
if best is None or dist < best_dist or (dist == best_dist and name < best):
best = name
best_dist = dist
return best
ans = []
for q in queries:
if q not in pos:
ans.append("NONE")
continue
x0, y0 = pos[q]
candidates = []
# 同 x：在按 y 排序列表里找邻居
lst = x_map.get(x0, [])
i = bisect_left(lst, (y0, q))
for j in (i - 1, i + 1):
if 0 <= j < len(lst):
y, name = lst[j]
if name != q:
candidates.append((name, x0, y))
# 同 y：在按 x 排序列表里找邻居
lst = y_map.get(y0, [])
i = bisect_left(lst, (x0, q))
for j in (i - 1, i + 1):
if 0 <= j < len(lst):
x, name = lst[j]
if name != q:
candidates.append((name, x, y0))
best = pick_best(candidates, x0, y0)
ans.append(best if best is not None else "NONE")
return ans
常见坑
bisect_left的 key 需要包含 name，避免同坐标时定位不稳定。- 候选只需邻居（前驱/后继），不要扫整条线。
- tie-break：距离相同选字典序更小。
如果你在准备 DoorDash VO，这题在面试里常被用来考你是否能把“全局扫描”改造成“索引 + 邻居候选”。oavoservice 会重点训练这种“把候选缩到常数个”的套路。
需要面试真题？ 立刻联系微信 Coding0201，获得真题。
联系方式
Email: [email protected] Telegram: @OAVOProxy