Implement K-Means Clustering from Scratch in Plain Python or NumPy

Implement k-means clustering from scratch. The interviewer allows NumPy but not a ready-made clustering library, and plain Python is acceptable too. Your code has to run and pass test cases the interviewer has prepared, so it must be complete and correct, not pseudocode. Assume this interface unless the interviewer specifies another: ```python def kmeans(points, k, max_iters=100, tol=1e-6, seed=None): """Return (centroids, labels). points: n points, each a list of d numbers centroids: k points, each a list of d floats labels: n integers in [0, k); labels[i] is the cluster of points[i] """ ``` ```hint Two alternating steps Write the step that assigns points to centers and the step that recomputes the centers as separate pieces you can test on their own. ``` ```hint A cluster can end up empty Decide what the update step does when no point is assigned to one of the centers. ``` ### Constraints and Clarifications - `n >= 1`, all points have the same dimension `d >= 1`, and `1 <= k <= n`. - Distance is Euclidean. - Results must be reproducible when `seed` is fixed. ### Clarifying Questions - How should the initial centers be chosen: random points, the first `k` points, or k-means++? Will the tests fix the seed or the initial centers? - What is the stopping rule: assignments stop changing, centers move less than a tolerance, or a fixed number of iterations? - What do the tests compare: centers, labels, or the total within-cluster squared distance, and with what tolerance? Does the numbering of the clusters matter? - Should an empty cluster be re-seeded, dropped, or left where it is? ### What a Strong Answer Covers - Correct assignment and update steps that run end to end - A clear initialization and convergence rule, with reproducible results - Edge cases: empty clusters, duplicate points, ties, `k = 1` and `k = n` - The cost per iteration, and a vectorized version - Tests that allow for cluster numbering being an arbitrary permutation ### Follow-up Questions - How does k-means++ initialization work, and why does it help? - How would you choose `k` when it is not given? - How would you run k-means on data that does not fit in memory? - Which cluster shapes does k-means handle poorly, and why does feature scaling matter for it?