Quick Overview

This question evaluates geospatial algorithm and systems-design competencies, focusing on nearest-neighbor search, great-circle distance computation, spatial indexing, and runtime/memory trade-offs for scalable location queries.

Solve k-Nearest Places by Latitude/Longitude

Company: Remitly

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Given a set of geographic coordinates and a query point, return the k nearest locations. Describe how you compute great-circle distance (e.g., Haversine), choose data structures or indexes (e.g., k-d tree variants, geohash bucketing, or R-tree), and bound runtime and memory complexity. Discuss handling of Earth curvature, antimeridian crossings, and performance at scale, including approximate search and batching.

Quick Answer: This question evaluates geospatial algorithm and systems-design competencies, focusing on nearest-neighbor search, great-circle distance computation, spatial indexing, and runtime/memory trade-offs for scalable location queries.

You are given a list of geographic locations, each as a `[latitude, longitude]` pair in decimal degrees, a query point `[latitude, longitude]`, and an integer `k`. Return the `k` locations closest to the query point, ordered from nearest to farthest, where distance is the **great-circle distance** computed with the Haversine formula on a sphere of radius 6371 km. Rules: - Return the place coordinate pairs themselves (not indices), in increasing order of distance. - If two places are equidistant, the one that appears earlier in the input list comes first (stable tie-break by original index). - If `k` is greater than the number of places, return all places sorted by distance. - If the input list is empty, return an empty list. Haversine distance between points (lat1, lon1) and (lat2, lon2), with all angles converted to radians: a = sin^2(Δlat/2) + cos(lat1)·cos(lat2)·sin^2(Δlon/2) c = 2·atan2(√a, √(1−a)) distance = R · c, R = 6371 km Because Haversine works on angular differences along the sphere, it naturally handles the antimeridian (longitudes near ±180) without special casing — the cosine/sine terms wrap correctly.

Constraints

  • 0 <= len(places) <= 10^5
  • Each coordinate is [latitude, longitude] with -90 <= latitude <= 90 and -180 <= longitude <= 180 (decimal degrees).
  • 1 <= k (k may exceed len(places); in that case return all places).
  • Distances use a spherical Earth model with R = 6371 km (Haversine).
  • Ties in distance are broken by the original index (earlier place first).

Examples

Input: ([[40.7128, -74.0060], [34.0522, -118.2437], [41.8781, -87.6298], [29.7604, -95.3698]], [40.0, -75.0], 2)

Expected Output: [[40.7128, -74.006], [41.8781, -87.6298]]

Explanation: Query is near New York. NYC (40.71, -74.01) is closest, then Chicago (41.88, -87.63) — both nearer than Los Angeles and Houston.

Input: ([[0.0, 0.0], [10.0, 10.0], [1.0, 1.0]], [0.0, 0.0], 1)

Expected Output: [[0.0, 0.0]]

Explanation: The query coincides exactly with the first place (distance 0), so it is the single nearest.

Hints

  1. Haversine needs radians: convert every latitude/longitude with math.radians before applying sin/cos. The constant R = 6371 km only scales the result, so it does not affect the ordering — but use it for consistency.
  2. You only need the *relative* ordering of distances. You could even sort by the chord term `a` instead of the full distance, since the Haversine distance is monotonic in `a` — but computing the real distance is clearer and fast enough.
  3. For deterministic output when two places are equidistant, sort by (distance, original_index). When k << n, a max-heap of size k gives O(n log k) instead of O(n log n).

Loading coding console...