K-Means From Scratch | Dataford Interview Questions

Write a function that performs k-means clustering on a set of 2D points from scratch. The function should assign each point to one of k clusters, repeatedly recompute centroids, and stop when assignments no longer change or a maximum number of iterations is reached.

Formal Specification

Implement kmeans(points, k, max_iters) where:

points is a list of 2D points, each point represented as [x, y]
k is the number of clusters
max_iters is the maximum number of iterations to run

Return a tuple (centroids, labels) where:

centroids is a list of k centroids, each centroid represented as [x, y]
labels is a list of length len(points), where labels[i] is the cluster index assigned to points[i]

Use the first k points as the initial centroids. If a cluster becomes empty, keep its centroid unchanged.

Constraints

1 <= len(points) <= 10^4
1 <= k <= len(points)
1 <= max_iters <= 100
Each point has exactly 2 coordinates
-10^4 <= x, y <= 10^4
Use Euclidean distance for assignment

Function Signature

def kmeans(points, k, max_iters):

Your question is K-Means From Scratch. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem