Return the K Closest Points with Deterministic Ties

Quick Overview

Implement `k_closest(points, target, k)`. Work through the function contract, boundary cases, correctness argument, and time and space complexity expected in a production-quality solution.

Return the K Closest Points with Deterministic Ties

Company: Asana

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

# Return the K Closest Points with Deterministic Ties Implement `k_closest(points, target, k)`. Each point and the target are integer pairs. Return exactly `k` input points with smallest squared Euclidean distance to the target, ordered by `(distance, x, y, original_index)` so ties have one canonical result. Constraints: `0 <= k <= len(points) <= 200000`; coordinates are integers between `-10^6` and `10^6`, so every squared distance is at most `8 * 10^12` and is exact in all four languages. Do not use square roots. Aim for `O(n log k)` time and `O(k)` auxiliary space. ```hint Make ties observable Include duplicate coordinates and different points at equal distance so the required ordering is exercised. ```

Quick Answer: Implement `k_closest(points, target, k)`. Work through the function contract, boundary cases, correctness argument, and time and space complexity expected in a production-quality solution.

|Home/Coding & Algorithms/Asana
Asana logo
Asana
Aug 6, 2026, 12:00 AM
mediumSoftware EngineerOnsiteCoding & Algorithms
0
0

Return the K Closest Points with Deterministic Ties

Implement k_closest(points, target, k). Each point and the target are integer pairs. Return exactly k input points with smallest squared Euclidean distance to the target, ordered by (distance, x, y, original_index) so ties have one canonical result.

Constraints: 0 <= k <= len(points) <= 200000; coordinates are integers between -10^6 and 10^6, so every squared distance is at most 8 * 10^12 and is exact in all four languages. Do not use square roots. Aim for O(n log k) time and O(k) auxiliary space.

Submit Your Answer to Earn 20XP

Sign in to leave a comment

Loading comments...