Implement robust k-means with k-means++ initialization
Company: Tencent
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Implement from scratch in Python (no scikit‑learn) a function kmeans(X, k, max_iter=300, tol=1e-4, random_state=0) that returns (centroids, labels). Requirements: a) Use k‑means++ initialization; b) Use vectorized NumPy operations for distance computation; c) Stop early when the maximum centroid shift is < tol; d) Handle empty clusters by re‑seeding to the point with the largest current assignment distance; e) Support an optional sample_weights array that reweights both assignment and centroid updates; f) Ensure deterministic behavior with random_state; g) Analyze time and space complexity in terms of n samples, d dimensions, and k clusters; h) Explain how you would test correctness (e.g., on simple 2D blobs) and diagnose convergence issues (e.g., inertia not decreasing). Provide the function signature, docstring, and well‑commented code.
Quick Answer: This question evaluates implementation and understanding of clustering algorithms (k-means with k-means++), vectorized numerical computing with NumPy, handling of edge cases such as empty clusters and sample weighting, and algorithmic complexity analysis in the Coding & Algorithms domain for Data Scientist roles.
Cluster points into k groups using deterministic k-means++ style initialization and return rounded centroids with labels.
Constraints
- X is a non-empty numeric matrix
- k may be larger than n and is capped at n
Examples
Input: ([[0, 0], [0, 2], [10, 10], [10, 12]], 2, 100, 0.0001, None, 0)
Expected Output: ([[0.0, 1.0], [10.0, 11.0]], [0, 0, 1, 1])
Explanation: Two separated 2D blobs.
Input: ([[1], [2], [10]], 5, 20, 0.0001, None, 1)
Expected Output: ([[2.0], [10.0], [1.0]], [2, 0, 1])
Explanation: k is capped at n.
Hints
- Choose the next initial centroid as the farthest weighted point from existing centroids for deterministic grading.