Classify points with k-nearest neighbours (standard library only) — interview question

Implement a k-nearest-neighbours classifier. You get m labelled training points (x, y, label) and q query points. For each query:

Compute the Euclidean distance to every training point.
Take the k closest. If two training points are at the same distance, the one given earlier in the input counts as closer.
Predict the label that occurs most often among those k.
If labels tie on count, pick the tied label whose member appears first in the neighbour list sorted from nearest to farthest.

Constraints

1 ≤ k ≤ m ≤ 500
1 ≤ q ≤ 300
|coordinates| ≤ 10^4

Input and output

Input: First line: m q k. Then m lines `x y label`. Then q lines `x y`. Coordinates are integers; labels are single words.
Output: q lines, each the predicted label.

Examples

Input 1

6 2 3
0 0 red
1 0 red
0 1 blue
5 5 blue
6 5 blue
5 6 red
0 0
5 5

Output

red
blue

Query (0,0): the nearest three are red (distance 0), then red and blue (distance 1), so red wins 2–1. Query (5,5): the nearest are blue, then blue and red, so blue wins.

Input 2

4 1 2
1 0 cat
-1 0 dog
0 3 cat
0 -3 dog
0 0

Output

cat

cat and dog are both at distance 1. cat is earlier in the input, so it ranks nearer. The vote is 1–1, and cat appears first in the neighbour list.

Show hints

Compare squared distances: same order, no square roots, exact integers.
sorted(range(m), key=lambda i: (d2[i], i)) gives the nearest-first order together with the index tie-break.

Show the explanation

For each query:

Python

order = sorted(range(m), key=lambda i: (dist2(q, train[i]), i))[:k]
votes = Counter(label[i] for i in order)
top = max(votes.values())
pred = next(label[i] for i in order if votes[label[i]] == top)

next(...) walks the neighbours from nearest to farthest and returns the first label with the top count, which is exactly the tie rule.

Why squared distance? √ is monotonic, so ordering by d² gives the same order as ordering by d. It stays an exact integer and is faster.

Cost. Brute force is O(m log m) per query because of the sort. heapq.nsmallest(k, ...) makes it O(m log k). For large data, KD-trees or ball trees (used by scikit-learn) or approximate-nearest-neighbour indexes avoid scanning every point.

What interviewers expect you to know about k-NN

It is a lazy learner. There is no training phase, so all the work happens at prediction time and every training point must be stored.
Scale your features. If one feature ranges up to 100000 and another up to 1, the first dominates every distance. Standardise first.
Choosing k. Small k gives a jagged boundary that overfits noise. Large k gives a smoother boundary that can underfit. Pick k by cross-validation. An odd k avoids ties between two classes.
Curse of dimensionality. In many dimensions, distances become nearly equal and "nearest" loses meaning. Dimensionality reduction (such as PCA) can help.

Original UniCircle question. Last reviewed 22 Oct 2026.