K-Nearest Neighbors Search
Problem statement
Given a list of points in $n$-dimensional space (each a tuple), a query point and an integer k, return the k points closest to the query under Euclidean distance.
Implement k_nearest_neighbors(points, query_point, k):
- Compute $d(p, q) = \sqrt{\sum_{i=1}^{n} (p_i - q_i)^2}$ from the query to every point.
- Return the
kpoints with the smallest distances, nearest first, as a list of tuples. - Ties: when two points are equally far, the one that appears earlier in the input list comes first.
- If
kexceeds the number of points, return all of them (sorted). Ifpointsis empty ork <= 0, return[].
Example
Input:
points = [(1, 2), (3, 4), (1, 1), (5, 6), (2, 3)]
query_point = (2, 2)
k = 3
print(k_nearest_neighbors(points, query_point, k))
Output:
[(1, 2), (2, 3), (1, 1)]
Reasoning: The distances from $(2, 2)$ are 1.0, 2.24, 1.41, 5.0 and 1.0. The three nearest are $(1, 2)$ and $(2, 3)$ at distance 1, then $(1, 1)$. The two points at distance 1 tie, so $(1, 2)$ comes first because it appears earlier in the input.
Show hint
Can you compute the distance from the query to every point in one array operation instead of a Python loop?
Relevant roles: ML Engineer, Data Scientist, Applied Scientist and AI Engineer.
Related free problems
- Multi-Head AttentionMedium
- Masked Self-AttentionMedium