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.