Closest K Points | Dataford Interview Questions

Asana can use coordinate-like representations to identify tasks nearest to a selected workspace location. Given a list of 2D integer points and a reference point, return the k closest points using squared Euclidean distance.

Implement k_closest_points(points, reference, k). A point is represented as [x, y], and reference is also represented as [x, y]. The distance is (x1 - x2)² + (y1 - y2), so no square root is needed. Return exactly k points, sorted by increasing distance. If distances tie, sort by increasing x, then increasing y.

Use an algorithm that avoids sorting all points when k is much smaller than the number of points.

Constraints

1 <= len(points) <= 10^5
1 <= k <= len(points)
-10^4 <= x, y <= 10^4
All points contain exactly two integers
The reference point contains exactly two integers

Function Signature

def k_closest_points(points, reference, k):

Your question is Closest K Points. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem

Use an algorithm that avoids sorting all points when k is much smaller than the number of points.

Constraints

1 <= len(points) <= 10^5
1 <= k <= len(points)
-10^4 <= x, y <= 10^4
All points contain exactly two integers
The reference point contains exactly two integers

Function Signature

def k_closest_points(points, reference, k):

Your question is Closest K Points. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.