Implementing K-Means Clustering | Dataford Interview Questions

Implement k-means clustering for a set of 2D points using Lloyd's algorithm. Given points and an integer k, partition the points into k clusters by repeatedly assigning each point to the nearest centroid and recomputing centroids until convergence or a fixed iteration limit.

Formal Specification

Write a function that takes:

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

Return a tuple (centroids, labels), where:

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

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

Constraints

1 <= len(points) <= 10^4
1 <= k <= len(points)
1 <= max_iters <= 100
Each point contains exactly 2 coordinates
-10^4 <= x, y <= 10^4
Return centroids rounded to 2 decimal places for comparison

Function Signature

def k_means(points, k, max_iters):

Your question is Implementing K-Means Clustering. 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