Implement robust k-means with k-means++ initialization

Q: Implement robust k-means with k-means++ initialization

This is a Coding & Algorithms interview question from Tencent for Data Scientist roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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.

Implement robust k-means with k-means++ initialization

Comments (0)