## Problem Given a list of bus stops with (latitude, longitude) coordinates and a query point, return the ID of the nearest bus stop. Optimize for repeated queries over the same stop dataset. ```python from dataclasses import dataclass @dataclass class Stop: id: str lat: float lon: float class BusStopFinder: def __init__(self, stops: list[Stop]): ... def nearest(self, lat: float, lon: float) -> str: ... ``` **Example:** ``` stops = [Stop("A", 40.7128, -74.0060), Stop("B", 40.7580, -73.9855)] finder = BusStopFinder(stops) finder.nearest(40.730, -74.000) -> "A" ``` Use Euclidean distance as an approximation (haversine not required). ## Follow-ups 1. What data structure would you use to answer nearest-neighbor queries sub-linearly? Walk through a k-d tree insertion. 2. When does Euclidean distance fail for geographic coordinates, and how does haversine fix it? 3. If stops are updated in real time (added/removed every few seconds), how do you keep the structure fresh? 4. How would you extend this to return the K nearest stops sorted by distance?

InterviewDB Question

Closest Bus Stop: Find the Nearest Bus Stop to a Query Point Using Spatial Data

phone

Question Details

Problem Given a list of bus stops with (latitude, longitude) coordinates and a query point, return the ID of the nearest bus stop. Optimize for repeated queries over the same stop dataset. Example: Use Euclidean distance as an approximation (haversine not required). Follow-ups What data structure would you use to answer nearest-neighbor queries sub-linearly? Walk through a k-d tree insertion. When does Euclidean distance fail for geographic coordinates, and how does haversine fix it? If stops ar…

Full Details

🔒

Unlock all Waymo questions

Full insider details, leaked discussions, and candidate experiences.

or every company, $100/year →

About This Question

This is a reported interview question from a waymo interview during the phone round.

It covers the following topics: Coding, Phone .

Topics

Coding Phone

Closest Bus Stop: Find the Nearest Bus Stop to a Query Point Using Spatial Data

Question Details

Full Details

About This Question

Topics

More Waymo Interview Questions