DoorDash VO: Closest Straight City

oavoservice Original Review: Focus on "how to reduce candidates to a constant number" and implementation details of tie-breaking.

Problem (Restated)

Given n city coordinates: (x[i], y[i]), and q query city names.

For each query city c:

• Find the city with the minimum Manhattan Distance to c among all cities with the same x or same y.
• If distances are equal, return the one with the lexicographically smaller name.
• If no straight-line city exists, return "NONE".

Core Idea

Scanning n cities for each query would result in O(nq).

Optimization:

• Sort cities on the same vertical line (same x) by y.
• Sort cities on the same horizontal line (same y) by x.

For a query city, you only need to look for its adjacent predecessor/successor in the two sorted lists, comparing at most 4 candidates.

Data Structures

• name -> (x, y)
• x_map[x] = [(y, name), ...] (sorted by y, then name)
• y_map[y] = [(x, name), ...] (sorted by x, then name)

Complexity

• Preprocessing: O(n log n)
• Single Query: O(log n)

Python Reference Implementation

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 = []

        # Same x: find neighbors in list sorted by 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))

        # Same y: find neighbors in list sorted by 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

Common Pitfalls

• bisect_left key needs to include name to avoid unstable positioning when coordinates are same.
• Candidates only need to be neighbors (predecessor/successor), don't scan the whole line.
• Tie-break: Smaller lexicographical order for same distance.

If you are preparing for DoorDash VO, this question is often used to test if you can transform "global scan" into "index + neighbor candidates". oavoservice focuses on training this "reducing candidates to constant" pattern.

Need real interview questions? Contact WeChat Coding0201 immediately to get real questions.