Find the nearest city sharing axis
Company: DoorDash
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given N cities, each with a unique name and integer coordinates (x, y). For any query city, return the nearest city that shares either the same x or the same y coordinate with the query city; distance is the absolute difference along the non-shared coordinate. If there is a tie in distance, break ties by lexicographically smaller city name. Preprocess the cities so that each query can be answered efficiently (e.g., sort by x and by y and use binary search). Specify the data structures, algorithms, and time/space complexity for preprocessing and for each query.
Quick Answer: This question evaluates algorithmic problem-solving and data-structuring skills for efficient spatial queries constrained to shared axes, including handling tie-breaking rules and preprocessing for fast lookups.
You are given a list of `cities`, where each entry is `[name, x, y]` with a unique `name` and integer coordinates `x`, `y`. You are also given a `query` city name.
Return the name of the nearest city (other than the query city) that shares either the same x-coordinate OR the same y-coordinate with the query city. Distance is measured as the absolute difference along the **non-shared** coordinate: if two cities share x, the distance is `|y1 - y2|`; if they share y, the distance is `|x1 - x2|`. If a candidate city shares both coordinates is impossible here because names and coordinates are distinct, but if a city matches on both axes you take the smaller of the two distances.
If there is a tie in distance, break ties by choosing the lexicographically smaller city name. If no city shares an axis with the query (or the query is the only city / not present), return `None` (null).
For an interview, you would preprocess by sorting cities by x and by y and binary-searching the neighbors at query time; the version below is the straightforward O(N) scan that is easiest to reason about and verify.
Constraints
- 1 <= N <= 10^5 cities.
- City names are unique, non-empty strings.
- Coordinates x, y are integers and may be negative.
- The query city is one of the given cities (or may be absent, in which case return None).
- A city only counts as a candidate if it shares the same x OR the same y as the query.
Examples
Input: ([['A', 0, 0], ['B', 0, 3], ['C', 0, 5], ['D', 7, 0]], 'A')
Expected Output: 'B'
Explanation: B, C share x=0 (dist 3, 5); D shares y=0 (dist 7). Nearest is B at distance 3.
Input: ([['A', 0, 0], ['B', 0, 2], ['C', 2, 0]], 'A')
Expected Output: 'B'
Explanation: B shares x (dist 2), C shares y (dist 2) -> tie; lexicographically smaller name 'B' wins.
Hints
- A city is a candidate only if it shares the query's x or the query's y. The distance you compare is along the OTHER axis: if x matches, compare |y - qy|; if y matches, compare |x - qx|.
- Track the best (smallest) distance seen so far. On a distance tie, prefer the lexicographically smaller name.
- For efficiency at scale, group cities by x and by y (or sort and binary-search). Within the query's x-group the nearest neighbor by y is one of the two adjacent entries; same idea for the y-group.