Implement a k-Nearest Neighbors Classifier from Scratch

Implement a k-nearest neighbors (KNN) classifier from scratch, without a machine learning library. It was one of two from-scratch ML algorithm implementations in a timed, 75-minute online assessment for a machine learning engineering internship that also contained a short coding problem and multiple-choice ML questions, so aim for correct, tested code rather than a complete library. The report names only the algorithm. The interface below is an assumption that makes the task concrete: ```python class KNNClassifier: def __init__(self, k: int): ... def fit(self, X: list[list[float]], y: list) -> "KNNClassifier": ... def predict(self, X: list[list[float]]) -> list: ... ``` `fit` stores `n` labeled training points with `d` numeric features each. `predict` returns one label per query point: the majority label among the `k` training points closest to that query. ```hint Two kinds of tie Both distances and votes can tie. Pick an explicit rule for each, so that the same inputs always produce the same prediction. ``` ```hint Count the work Count how many distance computations `predict` performs for `m` queries and `n` training points, and how much memory a full table of those distances would take. ``` ### Constraints and Clarifications - Not reported: the distance metric, the input sizes, whether NumPy is allowed, how ties are broken, and whether distance weighting or regression is expected. Ask, or state your assumptions. - Assume numeric features with no missing values, and labels that can be compared for equality. ### Clarifying Questions - Is this classification by majority vote, regression by averaging the neighbors' values, or both? - Which distance should be used (Euclidean, Manhattan, cosine), and are the features already on comparable scales? - What should happen when `k` is larger than the number of training points, or when the vote ties? - May I use NumPy, and roughly how many training points, query points and features should the code handle? - Should closer neighbors count more than farther ones? ### What a Strong Answer Covers - A correct `fit`/`predict` with an explicit distance and an explicit `k`, plus input validation - Deterministic rules for equal distances and for tied votes - The time and memory cost of prediction, and an efficient way to select the `k` nearest points - Edge cases: `k` larger than the training set, duplicate training points, a query identical to a training point - Feature scaling, and how the choice of `k` trades bias against variance ### Follow-up Questions - Make the vote distance-weighted. What breaks when a query coincides exactly with a training point, and how do you handle it? - The training set grows to 10 million points with 100 features. What does brute force cost per query, and what would you use instead? - How would you choose `k`, and how does accuracy behave as `k` goes from 1 to `n`? - Why does KNN tend to degrade as the number of features grows?