K-Means Clustering Implementation

Question

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.

AceOffer · Accepted Answer

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.

Reported follow-ups:
1. Can you optimize this using numpy broadcasting to avoid explicit Python loops? (when: Candidate writes a pure Python loop-based solution)
2. How do you determine convergence? What stopping criteria would you use? (when: After base implementation is complete)
3. Would you prefer to write this in Python or C++? (or: does the solution need to work in C++?) (when: Implementation is working)

**Alternative approaches:** 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.)

K-Means Clustering Implementation

Problem Overview

Follow-up Arc

Approach Trade-offs

Practice

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.