Implement Streaming Clustering for Numbers
Company: Uber
Role: Data Scientist
Category: Machine Learning
Difficulty: medium
Interview Round: Onsite
You receive a continuous stream of numeric values. Choose an appropriate clustering algorithm and implement it so that each incoming number can be assigned to a cluster while using bounded memory.
Clarify and address the following:
- The stream is potentially unbounded, so storing all historical values is not allowed.
- You may assume the number of clusters `k` is given, or explain how you would choose it.
- The algorithm should update cluster summaries online as new values arrive.
- The implementation should expose at least two operations: `add(value)` to process a new number and `get_clusters()` to return the current cluster centers or summaries.
- Discuss initialization, convergence behavior, outliers, concept drift, and how you would test correctness.
Overview: This question evaluates a data scientist's competency in online clustering for numeric streams, testing understanding of streaming algorithms, bounded-memory cluster summaries, online updates, and issues including initialization, convergence behavior, outlier handling, and concept drift.
Read the full Uber Data Scientist interview experience this question came from