Vibe Engines Learn
CODING CHALLENGE · N°11

K-Nearest Neighbors

Medium AI EngineeringMachine LearningClassification

The simplest classifier there is: to label a new point, look at the k closest labeled points and let them vote. No training, no weights — just distances. The whole model is the dataset. No numpy, just the math.

The problem

Implement k-nearest-neighbors classification. You are given points (a list of training feature vectors), labels (the integer class of each training point), a query vector, and an integer k. Measure the Euclidean distance from the query to every training point, take the k closest, and return the majority label among them. Tie-breaks (both deterministic): when two points are equidistant, prefer the one that appears earlier in points; when two labels are tied on votes, return the smaller label.

EXAMPLE 1
Input points=[[0,0],[10,10]], labels=[0,1], query=[1,1], k=1
Output 0
k=1 → just the single nearest point
EXAMPLE 2
Input points=[[0,0],[0,1],[1,0],[10,10],[10,11],[11,10]], labels=[0,0,0,1,1,1], query=[0.5,0.5], k=3
Output 0
the three nearest all belong to cluster 0
EXAMPLE 3
Input points=[[0,0],[2,0]], labels=[1,0], query=[1,0], k=2
Output 0
a 1–1 vote tie → the smaller label wins
CONSTRAINTS
  • Euclidean distance: √(Σ (pᵢ − qᵢ)²) across the feature dimensions.
  • Break distance ties by original index (earlier point in points is "nearer").
  • Break vote ties by returning the smaller integer label.
  • Pyodide has no numpy — use the math stdlib and plain lists only.
SOLVE IT YOURSELF

Your turn — write it

Edit the stub, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? the hints are right above and Reveal solution is one click away.

YOUR TASK

Implement knn(points, labels, query, k). Find the k training points closest to the query by Euclidean distance, then return the majority label (smaller label wins a vote tie).

HINTS — 4 IDEAS
  1. For each training point compute √(Σ (pᵢ − qᵢ)²) to the query.
  2. Sort by (distance, original index) so equidistant points keep a stable order, then take the first k.
  3. Tally the labels of those k neighbors in a dict / Map.
  4. Return the label with the most votes; on a tie, the smaller label.
CPython · WebAssembly
Approach, complexity & discussion — open after you solve

The approach

There is no training step — the dataset is the model (a “lazy” learner). For a query, compute its distance to every stored point, take the k nearest, and let them vote (majority class for classification) or average (for regression). The two choices that matter are the distance metric and k.

Complexity

Brute force: time O(n·d) per query over n points in d dimensions; space O(n·d) to hold the data. Approximate indexes (KD-tree, HNSW) make queries sub-linear.

Common mistakes

  • Not normalizing features — a single large-scale feature then dominates the distance and drowns out the rest.
  • Choosing k badly — k=1 is noisy and overfits, a huge k oversmooths across classes.
  • Brute-forcing at scale instead of using an approximate-nearest-neighbor index.

Where this shows up

k-NN is the conceptual core of vector search and RAG retrieval: “find the nearest embeddings to this query” is exactly k-NN, just run through an approximate index (HNSW) so it stays fast over millions of vectors. It also underlies recommendation and anomaly detection.

Finished this one? 0 / 75 Challenges done

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

ML Foundations

More Challenges

Explore more from Vibe Engines

Handbooks →
Roadmaps →
System Designs →
AI System Designs →
Algorithms →
Labs →
Paper Breakdowns →