K-Nearest Neighbors in High Dimensions | Dataford Interview Questions

Write a function to perform a k-nearest neighbor search on a high-dimensional vector space.

Implement knn_search(vectors, query, k), where vectors is a list of equal-length numeric vectors and query is one vector of the same dimension. Return the indices of the k nearest vectors, ordered by increasing squared Euclidean distance. Break equal-distance ties by smaller index. Use an approach that avoids sorting every vector when k is much smaller than the number of vectors.

The input contains at least k vectors, and all vector dimensions are positive.

Constraints

1 <= k <= len(vectors) <= 500
1 <= len(query) <= 512
Every vector has the same dimension as query
-10^6 <= vector coordinate, query coordinate <= 10^6
Return exactly k distinct indices

Function Signature

def knn_search(vectors, query, k):

Your question is K-Nearest Neighbors in High Dimensions. 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

Write a function to perform a k-nearest neighbor search on a high-dimensional vector space.

The input contains at least k vectors, and all vector dimensions are positive.

Constraints

1 <= k <= len(vectors) <= 500
1 <= len(query) <= 512
Every vector has the same dimension as query
-10^6 <= vector coordinate, query coordinate <= 10^6
Return exactly k distinct indices

Function Signature

def knn_search(vectors, query, k):

Your question is K-Nearest Neighbors in High Dimensions. 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.