Katkat
Back

Implement K-means and solve interval/frequency tasks

AmazonApplied Scientist · Onsite
MediumApplied ScientistOnsiteCoding & Algorithms

Last updated

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 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