Implement K-means clustering from scratch
Company: Adobe
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## Task
Implement **K-means clustering** from scratch (no ML libraries).
You are given a dataset of points:
- Input: an array `X` of shape `(n, d)` (n points, each d-dimensional)
- An integer `k` (number of clusters)
- `max_iters` and a convergence tolerance `tol`
### Requirements
1. Initialize `k` centroids (you may choose a standard approach such as random points from `X`).
2. Repeat until convergence or `max_iters`:
- **Assignment step:** assign each point to its nearest centroid (e.g., Euclidean distance).
- **Update step:** recompute each centroid as the mean of points assigned to it.
3. Handle the edge case where a cluster becomes empty.
### Output
Return:
- `centroids`: array of shape `(k, d)`
- `labels`: array of length `n` with cluster indices `0..k-1`
### Follow-ups (discussion)
- Time complexity per iteration.
- How initialization affects convergence and quality (e.g., K-means++ idea).
Quick Answer: This question evaluates a candidate's understanding of clustering algorithms and practical implementation skills in unsupervised machine learning, including distance computations, centroid estimation, and handling edge cases like empty clusters.