DoorDash VO Interview — Nearest Neighboring City | closestStraightCity | Hash Map + Sorting | Manhattan Distance

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.

This problem asks you to find, for each query city, the closest collinear neighbor sharing x or y. The core is efficient lookup and tie-breaking.

Expected approach from strong candidates:

• Build two maps:
  x -> list of cities on this x, y -> list of cities on this y.
• For each list, keep cities sorted by the other coordinate (and break ties by name).
• For a query city, binary-search its neighbors on the same x-list and y-list to find the nearest candidates on both sides, then compare distances and apply lexicographic tie-break.
  Complexity: preprocessing O(n log n); each query O(log n).

Edge cases: no shared x/y, multiple equal distances, identical coordinates blocked by“same city”rule.

The VOprep team has long accompanied candidates through various major company OAs and VOs, including Doordash, Google, Amazon, Citadel, SIG, providing real-time voice assistance, remote practice, and interview pacing reminders to help you stay smooth during critical moments. If you are preparing for Tiktok or similar engineering-focused companies, you can check out our customized support plans—from coding interviews to system design, we offer full guidance to help you succeed.