KNN From Scratch | Dataford Interview Questions

KNN From Scratch

HardPython

Problem

Develop Health needs a small, dependency-free classifier for categorizing patient records. Implement k-nearest neighbors (KNN) from scratch using Euclidean distance and majority voting.

Given training feature vectors, their labels, a query vector, and an integer k, return the predicted label for the query. Use the k training points with the smallest Euclidean distances. You may compare squared distances because the square root does not change their ordering.

If multiple labels receive the same highest vote count, return the label belonging to the closest neighbor. If distances are also equal, preserve the original training order.

Formal Specification

Implement predict_knn(points, labels, query, k), where points is a list of equal-length numeric feature vectors, labels is a list of strings parallel to points, query is one feature vector with the same dimension, and k is a positive integer. Return one string label.

Constraints

1 <= len(points) <= 10^4
len(points) == len(labels)
1 <= k <= len(points)
1 <= len(query) == len(points[i]) <= 20
Feature values are integers or floating-point numbers
Labels are non-empty strings

Function Signature

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

Develop Health needs a small, dependency-free classifier for categorizing patient records. Implement k-nearest neighbors (KNN) from scratch using Euclidean distance and majority voting.

If multiple labels receive the same highest vote count, return the label belonging to the closest neighbor. If distances are also equal, preserve the original training order.