How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Remitly.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Remitly during technical interviews.

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.

Input: ([[51.5074, -0.1278], [48.8566, 2.3522], [52.5200, 13.4050]], [50.0, 5.0], 3)

Expected Output: [[48.8566, 2.3522], [51.5074, -0.1278], [52.52, 13.405]]

Explanation: Query near central Europe: Paris is closest, then London, then Berlin. k=3 returns all three in distance order.

Input: ([[10.0, 10.0]], [10.0, 10.0], 5)

Expected Output: [[10.0, 10.0]]

Explanation: Only one place exists and k=5 exceeds the list size, so all available places are returned.

Input: ([], [0.0, 0.0], 3)

Expected Output: []

Explanation: Empty input list — there are no places to return.

Input: ([[35.6762, 139.6503], [37.5665, 126.9780], [-33.8688, 151.2093]], [40.0, 130.0], 2)

Expected Output: [[37.5665, 126.978], [35.6762, 139.6503]]

Explanation: Query in northeast Asia: Seoul (37.57, 126.98) is closest, then Tokyo (35.68, 139.65); Sydney in the southern hemisphere is far away and excluded for k=2.

Hints

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.
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.
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).

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.