DoorDash VO 面试题解析：最近同轴城市（closestStraightCity｜哈希表 + 排序｜曼哈顿距离）

You are given n cities on a Cartesian plane.
For each city i, you know:

• cityName[i] — the city’s name (a unique string)
• (x[i], y[i]) — its integer coordinates

For every queried city q, return the name of the nearest city that shares either the same x or the same y coordinate with q.

If no other city shares the same x or the same y with q, return "NONE".

If multiple candidate cities are at the same distance, return the one with the alphabetically smallest name.

The distance is the Manhattan distance:
|x1 - x2| + |y1 - y2|.

Example

n = 3
cityName = ['c1', 'c2', 'c3']
x        = [  3 ,   2 ,   1 ]
y        = [  3 ,   2 ,   3 ]
q        = ['c1', 'c2', 'c3']

Return:

['c3', 'NONE', 'c1']

Explanation (informal):

• For c1(3,3), the candidates must share x=3 or y=3 → c3(1,3) shares y; distance = 2 → answer c3.
• For c2(2,2), no city shares x=2 or y=2 → "NONE".
• For c3(1,3), c1(3,3) shares y; distance = 2 → answer c1.

这题要在二维平面上，对每个查询城市 q，找到与它 x 相同或 y 相同 的城市里 最近 的一个；如果距离一样， 按名字字典序更小 的优先；如果一个都没有，就返回 "NONE"。距离用 曼哈顿距离。

高分思路：

1. 预处理两张表：
   • x -> 该纵线上的城市列表（按 y 升序，遇到 y 相同再按名字升序）
   • y -> 该横线上的城市列表（按 x 升序，遇到 x 相同再按名字升序）
2. 查询时：在对应的两条有序列表里，用 二分 找到 q 的左右（或上下）相邻城市，最多比较 4 个候选；选距离最小、再按名字最小。
3. 若同轴列表不存在，直接返回 "NONE"。

复杂度：预处理 O(n log n)，单次查询 O(log n)，非常适合大规模输入。面试官关注你是否：

• 正确限定候选（必须同 x 或同 y）
• 说清 tie-break 规则
• 给出可扩展的时间复杂度

VOprep 团队长期陪同学员实战各类大厂 OA 与 VO，包括 Doordash、Google、Amazon、Citadel、SIG 等，提供实时答案助攻、远程陪练与面试节奏提醒，帮助大家在关键时刻不卡壳。
如果你也在准备 Tiktok 或类似工程向公司，可以了解一下我们的定制助攻方案——从编程面到系统设计，全程护航上岸。