Implement K-Means and Explain Convergence
Company: LinkedIn
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Implement the K-means clustering algorithm for a set of points in Euclidean space.
Your implementation should:
- Take as input a dataset of points and a target number of clusters `k`.
- Initialize `k` centroids.
- Repeatedly assign each point to its nearest centroid.
- Recompute each centroid as the mean of the points assigned to that cluster.
Then explain the stopping criteria for K-means. Discuss multiple valid choices, such as:
- no change in point-to-cluster assignments,
- centroid movement below a threshold,
- improvement in objective value below a threshold,
- reaching a maximum number of iterations.
Also describe important edge cases, such as empty clusters, and analyze the time complexity per iteration.
Quick Answer: This question evaluates a candidate's ability to implement and reason about the K-means clustering algorithm, testing skills in algorithmic implementation, unsupervised learning concepts, convergence criteria, handling edge cases like empty clusters, and per-iteration time complexity analysis.