How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at DoorDash.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at DoorDash during technical interviews.

Find the nearest city sharing axis | DoorDash Coding Question

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.

Input: ([['A', 1, 1], ['B', 1, 4], ['C', 5, 1]], 'A')

Expected Output: 'B'

Explanation: B shares x=1 (dist 3); C shares y=1 (dist 4). B is closer.

Input: ([['Z', 0, 0], ['Y', 0, 2], ['X', 2, 0]], 'Z')

Expected Output: 'X'

Explanation: Y shares x (dist 2) and X shares y (dist 2) -> tie; 'X' < 'Y' lexicographically.

Input: ([['A', 0, 0], ['B', 5, 5]], 'A')

Expected Output: None

Explanation: B shares neither x nor y with A, so there is no valid neighbor.

Input: ([['Solo', 3, 3]], 'Solo')

Expected Output: None

Explanation: The query is the only city; itself is excluded, so no answer exists.

Input: ([['A', 0, 0], ['B', 0, -4], ['C', -4, 0]], 'A')

Expected Output: 'B'

Explanation: B shares x (dist 4) and C shares y (dist 4) -> tie with negatives; 'B' < 'C' wins.

Input: ([['A', 2, 2], ['B', 2, 7], ['C', 9, 2], ['D', 2, -3]], 'A')

Expected Output: 'B'

Explanation: B shares x (dist 5), D shares x (dist 5), C shares y (dist 7). Tie between B and D at dist 5; 'B' < 'D'.

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.

Quick Overview

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.