InterviewDB
Question
Points Clustering: Implement K-Means Clustering from Scratch on 2D Points
phone
Question Details
Problem
Implement the K-Means clustering algorithm for 2D points. Given a list of points and k, initialize centroids using the first k points, then iterate: assign each point to the nearest centroid, recompute centroids as the mean of assigned points. Stop when assignments no longer change or after max_iter iterations.
python
def kmeans(
points: list[tuple[float, float]],
k: int,
max_iter: int = 100
) -> tuple[list[int], list[tuple[float, float]]]:
**Returns** (cluster_labels, final_centroids)
pass
Example:
points = [(1,1),(1,2),(2,1),(8,8),(8,9),(9,8)]
k = 2
-> labels = [0,0,0,1,1,1]
centroids = [(1.33,1.33), (8.33,8.33)] # approx
Follow-ups
- Why does K-Means not guarantee a global optimum, and how does K-Means++ initialization improve convergence?
- What metric would you use to choose
kautomatically (elbow method, silhouette score)? - K-Means assumes spherical clusters of similar size. What algorithm handles elongated or unequal clusters better?
- How would you scale this to 1 million high-dimensional points efficiently (mini-batch K-Means, approximate nearest neighbor)?
Full Details
Problem
Implement the K-Means clustering algorithm for 2D points. Given a list of points and k, initialize centroids using the first k points, then iterate: assign each point to the nearest centroid, recompute centroids as the mean of assigned points. Stop when assignments no longer change or after max_iter iterations.
python
def kmeans(
points: list[tuple[float, float]],
k: int,
max_iter: int = 100
) -> tuple[list[int], list[tuple[float, float]]]:
**Returns** (cluster_labels, final_centroids)
pass
Example:
points = [(1,1),(1,2),(2,1),(8,8),(8,9),(9,8)]
k = 2
-> labels = [0,0,0,1,1,1]
centroids = [(1.33,1.33), (8.33,8.33)] # approx
Follow-ups
- Why does K-Means not guarantee a global optimum, and how does K-Means++ initialization improve convergence?
- What metric would you use to choose
kautomatically (elbow method, silhouette score)? - K-Means assumes spherical clusters of similar size. What algorithm handles elongated or unequal clusters better?
- How would you scale this to 1 million high-dimensional points efficiently (mini-batch K-Means, approximate nearest neighbor)?
Free preview. Unlock all Nuro questions →
About This Question
This is a reported interview question from a nuro interview during the phone round.