KNN algorithm explained: k-nearest neighbors, distance, scaling and choosing k

In this article

1. Before you start
2. Why interviewers ask this
3. KNN algorithm from first principles
4. Worked example
5. Trade-offs and edge cases
6. How to answer it in an interview
7. Common mistakes
8. Follow-up questions
9. Sources

Before you start

This page is one step of the machine learning algorithms learning path.

Why interviewers ask this

A KNN question separates candidates who can recite "vote of the nearest points" from candidates who can say what breaks it. The method has no training step, so every cost and every failure sits in two choices: how distance is measured and how k is set. Interviewers use the question to see whether a candidate connects those choices to feature scaling, noisy labels and data with many features.

A weak answer names the vote and stops. A strong answer adds that distances need comparable feature scales, that a small k follows noisy labels, and that prediction, not training, is the expensive step. A Staff-level answer also knows where the theory ends: the best-known error bound holds only as the amount of data grows without limit, and in many dimensions "nearest" stops meaning near.

KNN algorithm from first principles

k-nearest neighbors (KNN)

k-nearest neighbors is a supervised method that stores every labeled training point and, for a new point, returns the most common label among the k stored points closest to it, under a chosen distance, instead of fitting a model during training.

Euclidean distance

Euclidean distance is the straight-line distance between two points: subtract the points feature by feature, square each difference, add the squares and take the square root. It is the most common choice of distance for KNN.

Curse of dimensionality

The curse of dimensionality is the effect that as the number of features grows, the volume of the space grows so fast that data become sparse and all distances fall into a narrow range, so the nearest neighbors are no longer much nearer than the rest.

In plain words

Imagine guessing whether a house is cheap or expensive by looking at the few houses closest to it on a map and taking the label most of them have. The analogy breaks in one place. On a map "closest" has one obvious meaning, while in data, closeness depends on which measurements you include and in which units.

In one precise sentence, KNN gives a query the most common label among the k stored training points whose feature vectors are closest to the query's. It rests on one assumption, stated in the Cornell lecture note for the machine learning course (CS4780): similar inputs have similar outputs.

Step 1: Store the labeled points and choose k

KNN stores the labeled training points and builds no model. The scikit-learn user guide calls neighbors-based methods non-generalizing, because they simply remember all of their training data.

The input of this step is a table of examples with labels; the output is the same table, kept as it is, perhaps inside a search index. The value k is a setting you choose before any query, not something learned. Because nothing is fitted, "training" is nearly free, and the cost moves to the moment a query arrives. You now know what is kept: all the data. The next step decides which stored points count as close.

Step 2: Distance decides who counts as near, so scale the features

Distance picks the neighbors, so features must share a scale. The most common distance is Euclidean distance, a case of the Minkowski distance with exponent p = 2; p = 1 gives the Manhattan distance (Cornell CS4780).

Here is the error in numbers. Take a query aged 30 with an income of 50,000 dollars, a stored point X aged 31 with an income of 58,000, and a stored point Y aged 60 with an income of 51,000 (illustrative values). Unscaled, the distance to X is about 8,000.0001 and to Y about 1,000.4499, so Y looks nearer although it is 30 years older.¹

Feature scaling is the step of rewriting every feature onto a comparable range so that no unit dominates the distance. With min-max scaling (ages 20 to 60 and incomes 30,000 to 90,000, illustrative), the distances become 0.1357 to X and 0.7502 to Y, and X is nearest.¹ The scikit-learn scaling example shows KNN models fitting differently with and without scaling; the feature engineering guide covers scaling and encoding in general.

Step 3: Find the k nearest points

The k nearest points are the k stored points with the smallest distance to the query. The simplest search, brute force, computes one distance per stored point and keeps the k smallest, so its cost grows with the number of stored points and with the number of features.

At 1,000,000 stored points and 50 features (illustrative), one query needs 50,000,000 multiply-adds.¹ Trees reduce the work: the scikit-learn guide notes a k-dimensional (KD) tree is very fast for low-dimensional searches, below about 20 dimensions, and becomes inefficient as dimensions grow. For small data sets brute force can be more efficient than a tree.

Input: one query and the stored table. Output: the k closest rows. You now know why prediction is the slow part: every query pays this search.

Step 4: The neighbors vote

The majority label among the k nearest points is the prediction. Cornell defines the rule as assigning the most common label among the k most similar training inputs. The k nearest points vote and the majority label wins.

Ties need a rule. The scikit-learn guide warns that if two neighbors have identical distances but different labels, the result depends on the ordering of the training data. Cornell suggests that in case of a draw, a good solution is to return the result of KNN with a smaller k. A common variant weights each vote by the inverse of the distance, so closer points count more. For numeric targets the usual variant averages the neighbors' values instead of voting.

1 · Store2 · Distance3 · Nearest k4 · VoteReplay

Step-by-step description

1. Labeled points are kept as they are.
2. Scaled features give fair distances.
3. Keep the k closest points.
4. The majority label is returned.

• KNN stores the labeled training points and builds no model.
• Distance picks the neighbors, so features must share a scale.
• The k nearest points vote and the majority label wins.

Worked example

A query at (3, 3) and six labeled points show the vote by hand (illustrative coordinates). The distances to the points (2, 3) labeled A, (4, 4) labeled B, (1, 2) labeled B, (5, 5) labeled B, (2, 0) labeled A and (6, 6) labeled B are 1.0, 1.4142, 2.2361, 2.8284, 3.1623 and 4.2426.¹

With k = 1 the label is A. With k = 2 one A and one B tie, so falling back to k = 1 gives A. With k = 3 the neighbors are A, B and B, and the vote is B, two to one; k = 5 still gives B, three votes to two.¹ The single A at distance 1.0 plays the part of a noisy label: a small k obeys it, and a larger k outvotes it.

The edge lengths come from Cornell's analysis: to capture k of n points in a cube, the cube's edge, as a share of each feature's range, is (k / n) to the power 1 / d. At 2 dimensions the edge length is 0.1; at 1,000 dimensions the cube holding 10 of 1,000 points has edge length 0.9954, so almost the entire space is needed.¹ Keeping the edge at 0.1 needs n = k × 10 to the power d points, which is 10,000 at 3 dimensions.¹

Text description of the diagram

• At 2 dimensions the edge length is 0.1.
• At 1,000 dimensions the cube holding 10 of 1,000 points has edge length 0.9954.

The theory side has a bound. The Bayes error rate is the lowest error rate any classifier can achieve on the problem; it is above zero when the classes overlap, and it has no connection with Bayes' rule (Elkan, University of California San Diego). Cover and Hart (1967) show that for any number of categories the error of the nearest-neighbor rule is bounded above by twice the Bayes error, in the large-sample limit. For two classes and a Bayes error of 0.10 (illustrative), the bound is 2 × 0.10 × 0.90 = 0.18.¹

Trade-offs and edge cases

KNN trades a free training step for a costly prediction step, and its accuracy depends on k, on distance and on dimension. The scikit-learn guide says the best k is highly data-dependent: a larger k suppresses the effects of noise but makes the classification boundaries less distinct. A small k follows every training point, including noisy labels. In bias and variance terms, a small k has high variance and a large k has high bias, so you choose k by checking error on held-out data.

Text description of the diagram

• A larger k suppresses noise but makes class boundaries less distinct.
• A small k follows every training point, including noisy labels.

Other cases that break the textbook answer:

• Many features. The curse of dimensionality makes neighbors barely nearer than other points, and trees fall back toward brute force. Reduce dimensions or drop irrelevant features first.
• Imbalanced classes. A common class tends to fill most neighborhoods, so it wins votes it should not; weighted votes or resampling help.
• Odd k. An odd k avoids ties only with two classes; with three or more classes a vote can still tie.
• Shifted data. Stored points describe the past, so a distribution shift makes the neighbors stale.
• Memory. All the data stays in memory, so large tables need an approximate index.

Where a method with labels is confused with one without, see k-means vs KNN.

How to answer it in an interview

The spoken structure: say what is stored, say how the vote works, name the role of k, then name the two costs, slow prediction and high dimensions.

Common mistakes

• "KNN has no training, so it is cheap." (wrong) The cost moves to prediction, where every query searches the stored data. (right) "Training is nearly free; prediction is the expensive step."
• "Always use an odd k." (wrong) That avoids ties only in a two-class problem. (right) "I pick k on held-out data and break ties by falling back to a smaller k."
• "KNN is always within twice the error of the best classifier." (wrong) The bound holds only as the amount of data grows without limit. (right) "Asymptotically, the nearest-neighbor error is at most twice the Bayes error."
• "Scaling is optional." (wrong) A feature with a large range dominates the distance. (right) "I scale features before computing distances."
• "A tree makes KNN fast in any dimension." (wrong) KD trees degrade as dimensions grow. (right) "Trees help in low dimensions; beyond that I reduce dimensions or use an approximate index."

Follow-up questions

What are common KNN interview questions?

Candidates report questions on how the algorithm works, how to choose k, why features need scaling, how ties are broken, why prediction is slow and why many dimensions hurt. Each of those has its own section above, so you can answer them in that order.

What happens if k equals the number of training points?

Every query sees every stored point, so the vote returns the overall most common label for all inputs, and the boundary has no detail at all. At the other extreme, k = 1 copies the label of the single nearest point and follows every noisy label.

How is KNN different from k-means?

KNN is supervised: it needs labels and uses them to vote. k-means is unsupervised: it groups unlabeled points around centers. The k-means vs KNN page covers the difference in detail.

Does KNN work for regression?

Yes. Instead of a majority vote, the prediction is usually the average of the k neighbors' numeric labels, optionally weighted by inverse distance. Scaling, the choice of k and the curse of dimensionality apply in the same way.

Where does KNN show up in recommendations?

Neighborhood methods find users or items closest to a given one and borrow their ratings, which is the idea behind collaborative filtering. The same distance and scaling questions apply.

Sources

1. 1.6. Nearest Neighbors (scikit-learn user guide) — scikit-learn documentation, 26 Oct 2026
2. Lecture 2: k-nearest neighbors (CS4780) — Cornell University (Weinberger), 1 Jan 2018
3. Nearest neighbor pattern classification — IEEE Transactions on Information Theory (Cover and Hart), 1 Jan 1967
4. Nearest Neighbor Classification (lecture notes) — UC San Diego (Elkan), 26 Oct 2026
5. Importance of Feature Scaling (scikit-learn example) — scikit-learn documentation, 26 Oct 2026