Katkat
Back

Implement KNN from Scratch

J.P. MorganData Scientist · Technical Screen
MediumData ScientistTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to implement the K-Nearest Neighbors (KNN) algorithm from scratch, focusing on distance computation, sorting, and majority voting logic.

Problem Statement

Implement a KNNClassifier class that classifies a new data point based on the majority class of its k nearest neighbors in the training set using Euclidean distance.

Requirements

  1. fit(X_train, y_train): Store the training data and labels.
  2. predict(X_test, k): For each point in X_test, find the k closest points in the training set and return the most frequent class. In case of a tie in voting, return the class with the smaller index value (e.g., if classes 0 and 1 are tied, return 0).

Constraints

  • X_train, X_test: 2D lists of floats representing feature vectors.
  • y_train: 1D list of integers representing class labels.
  • Distance Metric: Euclidean distance sqrt(sum((a_i - b_i)^2)).
  • Time complexity: Aim for O(N * M) per query, where N is the number of training samples and M is the number of features.

Example

train_x = [[1, 2], [2, 3], [5, 5], [6, 7]]
train_y = [0, 0, 1, 1]
model = KNNClassifier()
model.fit(train_x, train_y)

# Predicting a point close to [1, 2] and [2, 3]
print(model.predict([[1.5, 2.5]], k=3))
# Output: [0]

Edge Cases

  • What happens if k is greater than the number of training samples?
  • How should the model handle empty inputs?

Hints

Hint 1

Calculate the Euclidean distance between the test point and every point in the training set, storing these distances alongside their corresponding labels.

Hint 2

Sort the list of (distance, label) tuples based on the distance value to identify the top k neighbors.

Hint 3

Use a hash map (dictionary) or a frequency array to count the occurrences of labels among the k neighbors and return the key with the highest count.

Follow-up questions

  • How would the algorithm change if we wanted to use weighted voting, where closer neighbors have more influence?
  • What are the limitations of KNN in terms of memory and latency as the size of the training dataset grows to millions of rows?
  • How does the choice of k affect the bias-variance tradeoff in this model?