Implement K-Means Clustering | Dataford Interview Questions

Live coding: implement the k-means clustering algorithm on the spot.

Asked in the onsite_virtual stage. English gloss: live-code an implementation of the k-means clustering algorithm from scratch. Round 2, candidate did not finish it.

Contract

Implement k_means(points, k, max_iterations). points is a non-empty list of equal-length numeric lists. Initialize centroids using evenly spaced point indices, including the first and last point. For k == 1, use the first point as the initial centroid. Assign each point to the nearest centroid using squared Euclidean distance, breaking ties by the lowest centroid index. Recompute each non-empty centroid as the coordinate-wise mean. Preserve the previous centroid for an empty cluster. Return centroids after convergence or after max_iterations updates.

Constraints

1 <= len(points) <= 1000
1 <= len(points[0]) <= 10
All points have the same dimensionality
1 <= k <= len(points)
1 <= max_iterations <= 100
Point coordinates are finite integers or floats

Function Signature

def k_means(points, k, max_iterations):

Your question is Implement 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