Implement a 1-Nearest-Neighbor Classifier with a Manhattan-Distance Follow-Up

Implement a 1-nearest-neighbor (1-NN) classifier. You are given training points, each a vector of `d` numeric features with a class label, and a set of query points with the same `d` features. For every query, predict the label of the training point closest to it. Start with Euclidean distance; the follow-up asks you to support Manhattan distance as well. ### Clarifying Questions - May I use NumPy, or should the solution use only the standard library? - When two training points are exactly equally close to a query, which label should win? - Roughly how many training points, query points and features are there? This decides whether computing every distance at once fits in memory. - Should features be rescaled before computing distances, or used as given? ### Part 1 — Euclidean nearest neighbor Write `predict(X_train, y_train, X_query)` that returns one predicted label per query point, using Euclidean distance. ```hint Share the work across pairs Start from a correct double loop, then look for the parts of the distance computation that can be shared across all query-training pairs, and check what each version costs in memory. ``` #### What This Part Should Cover - A correct nearest-neighbor search and label lookup with a stated tie rule. - A vectorized distance computation and its memory footprint as the numbers of queries and training points grow. - Time and space complexity of training and of prediction. ### Part 2 — Follow-up: Manhattan distance Add support for Manhattan distance, the sum of absolute coordinate differences, selectable by a parameter. Explain what changes in your implementation and whether the switch can change the predictions. ```hint Check which speed-ups survive Ask whether every trick you used to speed up the Euclidean version still applies once the distance is a sum of absolute values. ``` #### What This Part Should Cover - Switching metrics without duplicating the search logic. - Which speed-ups from Part 1 carry over to the new metric and which do not, with the memory consequences. - A concrete case where the two metrics pick different neighbors, and the role of feature scaling. ### What a Strong Answer Covers - A correct, tested implementation with small hand-checked examples, including a tie. - Reasoning about when brute force is acceptable and what index structures or approximate search would replace it at scale. - Awareness of 1-NN's sensitivity to noisy labels, irrelevant features and feature scale. - Clean code: input validation, consistent shapes, and a single place where the metric is chosen. ### Follow-up Questions - How would you extend this to k nearest neighbors with majority voting, and how would you break voting ties? - With millions of training points and a latency budget per query, what would you change? - How does high dimensionality affect nearest-neighbor methods, and does the choice between the two metrics matter more there? - How would you choose between the two metrics empirically on a given dataset?