Find the K Closest Points to a Query Location

Question

The question asks you to find the K closest points to a given query location from a set of points in a 2D space.

Codemia · Accepted Answer

To find the K closest points to a query location, we can use a max-heap to keep track of the closest points as we iterate through the list of points. The distance can be calculated using the Euclidean distance formula, but for comparison purposes, we can simply use the squared distance to avoid unnecessary computation of square roots.

1. Initialize a max-heap to store the K closest points.
2. Iterate through each point in the list:
   - Calculate the squared distance from the query point.
   - If the heap has fewer than K points, add the current point.
   - If the heap is full and the current point is closer than the farthest point in the heap, replace the farthest point.
3. Extract points from the heap and return them as the result.

The time complexity of this approach is O(N log K), where N is the number of points. This is due to the need to maintain the max-heap of size K. The space complexity is O(K) for storing the K closest points.

Consider edge cases such as:
- When K is greater than the number of points.
- When all points are equidistant from the query location.
- Handling negative coordinates and large datasets efficiently.

```python
import heapq

def k_closest(points, query, K):
    max_heap = []
    for (x, y) in points:
        distance = (x - query[0]) ** 2 + (y - query[1]) ** 2
        if len(max_heap) < K:
            heapq.heappush(max_heap, (-distance, (x, y)))
        else:
            heapq.heappushpop(max_heap, (-distance, (x, y)))
    return [point for (_, point) in max_heap]
```

Find the K Closest Points to a Query Location

Uber

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Approach

Algorithm

Submit Your Answer

Uber Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string