Implement K-means and solve interval/frequency tasks

Task 1 — Describe/implement K-means clustering

Given:

• A data matrix X with 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

Part 1: Deterministic K-means Clustering

Given a data matrix X with n points and d features per point, implement a deterministic version of K-means clustering. Use the first k points of X as the initial centroids. In each iteration, assign every point to the nearest centroid using squared Euclidean distance; if two centroids are tied, choose the smaller centroid index. Then update each centroid to the coordinate-wise mean of the points assigned to it. If a cluster receives no points, keep its centroid unchanged. Stop when the labels no longer change or when max_iters iterations have been executed. Return both the final centroids and the label for each point. Do not round the centroid values.

Constraints

• 1 <= n <= 10^3
• 1 <= d <= 20
• 1 <= k <= n
• 1 <= max_iters <= 100
• All rows of X have the same length d
• Each coordinate fits in standard Python int/float ranges

Examples

Example 1

Input: ([[1, 1], [1, 2], [4, 4], [4, 5]], 2)
Output: {'centroids': [[1.0, 1.5], [4.0, 4.5]], 'labels': [0, 0, 1, 1]}

Explanation: Two obvious groups form, and the centroids converge to the means of those groups.

Example 2

Input: ([[0, 0], [2, 2], [4, 4]], 1)
Output: {'centroids': [[2.0, 2.0]], 'labels': [0, 0, 0]}

Explanation: With one cluster, the centroid becomes the mean of all points.

Hints

1. Use squared Euclidean distance so you do not need to call sqrt.
2. During the update step, keep a sum vector and a count for each cluster; if a count is 0, leave that centroid unchanged.

Part 2: Merge Overlapping Closed Intervals

You are given a list of closed intervals, where each interval is [start, end] and start <= end. Merge all overlapping intervals and return a list of disjoint intervals sorted by starting value. Because the intervals are closed, [1, 4] and [4, 5] should be merged.

Constraints

• 0 <= len(intervals) <= 2 * 10^5
• -2^31 <= start <= end <= 2^31 - 1

Examples

Example 1

Input: ([[1, 3], [2, 6], [8, 10], [15, 18]],)
Output: [[1, 6], [8, 10], [15, 18]]

Explanation: The first two intervals overlap and become [1, 6].

Example 2

Input: ([[1, 4], [4, 5]],)
Output: [[1, 5]]

Explanation: Closed intervals that touch at an endpoint still overlap.

Hints

1. Sort the intervals by their start value first.
2. As you scan left to right, only compare the current interval with the last merged interval.

Part 3: Top-k Most Frequent Elements with Deterministic Tie-Breaking

Given an integer array nums and an integer k, return the k values that occur most frequently. To make the result deterministic, order the answer by decreasing frequency. If two values have the same frequency, the smaller numeric value must come first.

Constraints

• 1 <= len(nums) <= 2 * 10^5
• Values fit in 32-bit signed integers
• 1 <= k <= number of distinct values in nums

Examples

Example 1

Input: ([1, 1, 1, 2, 2, 3], 2)
Output: [1, 2]

Explanation: 1 appears 3 times, 2 appears 2 times, and 3 appears once.

Example 2

Input: ([4, 4, 1, 1, 2, 2], 2)
Output: [1, 2]

Explanation: All three values appear twice, so the smaller values come first.

Hints

1. Count how many times each value appears before trying to choose the top k.
2. Once you know the frequencies, sort distinct values by frequency descending and value ascending.