# Implement K-Means Without Numerical Libraries Implement K-means clustering for a list of finite numeric points using only core language features and elementary arithmetic. The function receives the initial centroids so that initialization is deterministic. ```python def kmeans(points, initial_centroids, max_iterations, tolerance): ... ``` Return the final centroids and one cluster index per input point. Use squared Euclidean distance. On an exact distance tie, choose the lower centroid index. Stop when either the iteration limit is reached or the largest centroid movement is at most `tolerance`. State and implement a deterministic policy for an empty cluster. ### Constraints & Assumptions - All points and centroids have the same positive dimension. - `1 <= k <= number of points`. - Inputs contain only finite numbers. - The returned cluster indices must correspond to the returned centroids; perform a final assignment if the last update moved a centroid. ### Clarifying Questions to Ask - Should movement use Euclidean distance or squared distance? - What empty-cluster policy is expected? - Is deterministic output required for tests? - Are duplicate points and duplicate starting centroids allowed? ### What a Strong Answer Covers - A complete assign-update loop with explicit termination - Stable, deterministic tie and empty-cluster behavior - Avoiding unnecessary square roots during assignment - Complexity in terms of points, clusters, dimensions, and iterations - Tests for duplicate points, empty clusters, convergence, and iteration limits ### Follow-up Questions - Why does standard K-means reduce its objective on each non-empty update step? - How would K-means++ change initialization? - What makes the result sensitive to scale and outliers? - How would you process data that cannot fit in memory?