Katkat
Back

Implement K-Means Clustering from Scratch in Plain Python or NumPy

LyftMachine Learning Engineer · Technical Screen
MediumMachine Learning EngineerTechnical ScreenMachine Learning

Last updated

A live coding exercise that asks you to implement k-means clustering from scratch in Python, with NumPy optional, and make it pass the interviewer's test cases. It tests the assignment and update steps, initialization, convergence, empty clusters and writing runnable code under time pressure.

Implement k-means clustering from scratch. The interviewer allows NumPy but not a ready-made clustering library, and plain Python is acceptable too. Your code has to run and pass test cases the interviewer has prepared, so it must be complete and correct, not pseudocode.

Assume this interface unless the interviewer specifies another:

def kmeans(points, k, max_iters=100, tol=1e-6, seed=None):
 """Return (centroids, labels).

 points: n points, each a list of d numbers
 centroids: k points, each a list of d floats
 labels: n integers in [0, k); labels[i] is the cluster of points[i]
 """

Constraints and Clarifications

  • n >= 1, all points have the same dimension d >= 1, and 1 <= k <= n.
  • Distance is Euclidean.
  • Results must be reproducible when seed is fixed.

Clarifying Questions

  • How should the initial centers be chosen: random points, the first k points, or k-means++? Will the tests fix the seed or the initial centers?
  • What is the stopping rule: assignments stop changing, centers move less than a tolerance, or a fixed number of iterations?
  • What do the tests compare: centers, labels, or the total within-cluster squared distance, and with what tolerance? Does the numbering of the clusters matter?
  • Should an empty cluster be re-seeded, dropped, or left where it is?

Hints

Hint 1

Two alternating steps: Write the step that assigns points to centers and the step that recomputes the centers as separate pieces you can test on their own.

Hint 2

A cluster can end up empty: Decide what the update step does when no point is assigned to one of the centers.

Follow-up questions

  • How does k-means++ initialization work, and why does it help?
  • How would you choose `k` when it is not given?
  • How would you run k-means on data that does not fit in memory?
  • Which cluster shapes does k-means handle poorly, and why does feature scaling matter for it?