Nearest Stops

Problem

A rider opens the app and we know their GPS position. We keep every pickup stop in a city in memory as (id, lat, lng). Write nearestStops(stops, rider, k, radiusKm) that returns the ids of the k closest stops within radiusKm of the rider, closest first. Use great-circle (haversine) distance with an Earth radius of 6371 km. Cairo alone has about 40k stops and this runs on every app open, so once the naive version works we will ask how to avoid scanning all of them.

Examples

Example 1, stops = [(1, 30.0444, 31.2357), (2, 30.05, 31.24), (3, 30.06, 31.22)], rider = (30.045, 31.236), k = 2, radiusKm = 5 → [1, 2]. Stop 1 is about 70 m away, stop 2 about 680 m, stop 3 about 2.3 km but only two were requested.

Example 2, same stops, rider = (30.1, 31.4), k = 3, radiusKm = 5 → []. The nearest stop is roughly 16 km away, outside the radius.

Constraints

• 1 ≤ len(stops) ≤ 50,000, 1 ≤ k ≤ 50, 0 < radiusKm ≤ 20
• Coordinates are valid WGS84 decimal degrees
• Ties are broken by the lower stop id

What they look for

A correct haversine (convert to radians!), not sorting all 40k candidates when k is small (a bounded heap or partial sort), and then the follow-up: how would you index this, geohash prefixes, an H3/S2 cell grid, or a k-d tree, and what happens when the rider sits right on a cell boundary.