Given a 2D array of coordinate points where each element is [row, col], and an integer k representing the number of clusters, implement K-Means clustering from scratch.
Given a 2D array of coordinate points where each element is [row, col], and an integer k representing the number of clusters, implement K-Means clustering from scratch. Initialize centroids using the first k points in the array. Iteratively assign each point to its nearest centroid and recompute centroids as the mean of their assigned points. Continue until convergence. Return the clustered results (points grouped by cluster). Emphasis is placed on using numpy broadcasting and vectorization for performance optimization.
Can you optimize this using numpy broadcasting to avoid explicit Python loops?
How do you determine convergence? What stopping criteria would you use?
Would you prefer to write this in Python or C++? (or: does the solution need to work in C++?)
| Approach | Notes |
|---|---|
| Pure Python (no numpy) | Simpler to reason about but significantly slower for large datasets; not preferred by interviewers who explicitly test for vectorization. |
| Random centroid initialization (K-Means++) | Better convergence properties in practice, but the interview specifies using the first k points as initial centroids, so this may be out of scope unless asked. |
Common mistakes: Candidates were unsure whether a basic Python solution was sufficient or whether numpy vectorization was required — the answer is that numpy broadcasting was explicitly required and heavily weighted.
Interviewer hints: The interviewer specifically pushed on numpy broadcasting and vectorization as a key optimization goal, not just a nice-to-have.; The session included two problems total; K-Means was the harder first problem, and the second problem (character coordinate grouping from a multiline string) was notably simpler.
What passers do: Candidates who did well demonstrated strong numpy broadcasting skills — the interviewer placed heavy emphasis on vectorized distance computation and centroid updates rather than loop-based implementations.