Find the K Nearest Neighbors Practice Problem
This data science coding problem helps you practice K-Nearest Neighbors, find the k nearest neighbors, and implementation skills. Read the problem statement, write your solution, and strengthen your understanding of K-Nearest Neighbors.
- Problem ID: 188
- Problem key: 188-find-the-k-nearest-neighbors
- URL: https://datacrack.app/solve/188-find-the-k-nearest-neighbors
- Difficulty: easy
- Topic: K-Nearest Neighbors
- Module: Supervised Learning
Problem Statement
# 🧩 Find the K Nearest Neighbors
---
### 🎯 Goal
Find the `k` training samples closest to a new query sample.
---
### 📖 Introduction
KNN predicts a new sample by looking at nearby training examples. After calculating the distance from the query to every training sample, it sorts those distances from smallest to largest.
The first `k` samples in that sorted order are the **K nearest neighbors**. Their labels will be used for voting in the next problem.
This problem does not make a class prediction yet. Its job is to correctly find, order, and return the nearby examples.
---
### 💻 Task
Implement `find_k_nearest_neighbors(X, y, query, k)`.
Your function should:
- Calculate Euclidean distance from `query` to every row in `X`.
- Keep each distance together with its row index and label.
- Sort from closest to farthest.
- Return only the first `k` neighbors.
- Round returned distances to 6 decimals.
- When distances tie, put the smaller index first.
---
### 📥 Input / 📤 Output
**Input**
- `X`: a training feature matrix.
- `y`: one label for every row in `X`.
- `query`: one new sample.
- `k`: number of neighbors to return.
**Output**
- A list of dictionaries in closest-to-farthest order. Every dictionary has `index`, `distance`, and `label`.
---
### 🧩 Starter Code
```python
def find_k_nearest_neighbors(X, y, query, k):
def distance(row):
# Calculate distance from row to query
pass
# Your code here
pass
```
---
### 💡 Example
```python
find_k_nearest_neighbors(
[[1, 1], [2, 2], [5, 5], [6, 6]],
["A", "A", "B", "B"],
[1.5, 1.5],
2
)
```
Expected output:
```python
[
{"index": 0, "distance": 0.707107, "label": "A"},
{"index": 1, "distance": 0.707107, "label": "A"}
]
```
---
### ⚠️ Common Mistakes
- Finding distances but forgetting to sort them.
- Sorting distances without keeping their matching labels and indices.
- Returning every row instead of only the first `k`.
- Sorting only by distance without defining what happens when distances tie.
Starter Code
def find_k_nearest_neighbors(X, y, query, k):
def distance(row):
# Calculate distance from row to query
pass
# Your code here
pass