Implement K-Nearest Neighbors | Dataford Interview Questions

A Hitachi Energy Lumada APM classifier needs to assign an integer condition class to a new sensor-feature vector using exact k-nearest neighbors. Implement an efficient KNN predictor without using machine-learning libraries.

Formal Specification

Implement knn_predict(points, labels, query, k).

points is a list of n feature vectors, where every vector contains d integers.
labels[i] is the integer class for points[i].
query is a feature vector with d integers.
Return the predicted integer label from the k nearest points using squared Euclidean distance.

Build a balanced KD-tree, then search it with backtracking. If multiple points have equal distance, prefer the smaller original point index. Class prediction uses: highest vote count, then smallest total squared distance among tied classes, then smallest label.

Constraints

1 <= len(points) <= 20,000
len(points) == len(labels)
1 <= len(query) <= 20
Every point has exactly len(query) coordinates
1 <= k <= len(points)
Coordinates and labels are integers in [-10^6, 10^6]

Function Signature

def knn_predict(points, labels, query, k):

Your question is Implement K-Nearest Neighbors. 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