Implement K-means and solve interval/frequency tasks
Overview
This multi-part question evaluates understanding of K-means clustering, interval-merging algorithms, and frequency-based top-k retrieval, assessing competencies in unsupervised learning concepts, algorithmic problem solving, data structures, and complexity analysis.
Task 1 — Describe/implement K-means clustering
Given:
-
A data matrix
Xwith shape(n_samples, d). -
An integer
k(number of clusters).
Explain (or write high-level pseudocode for) the K-means algorithm such that:
- The steps are unambiguous.
- Matrix/vector dimensions are consistent.
- You cover initialization, assignment, centroid update, and stopping criteria.
Task 2 — Merge overlapping intervals
Given a list of closed intervals intervals, where each interval is [start, end] and start <= end, merge all overlapping intervals and return the merged list.
Input: intervals: List[List[int]]
Output: merged intervals in any order (or sorted by start), with no overlaps.
Task 3 — Return the top-k most frequent elements
Given an integer array nums and an integer k, return the k values that occur most frequently.
Input: nums: List[int], k: int
Output: List[int] containing k elements.
Constraints (assume typical interview constraints)
-
1 <= n <= 2e5 - Values fit in 32-bit signed integers
-
1 <= k <= number of distinct values in nums