Katkat
Back

Implement local maxima, bagging, and k-means

TikTokMachine Learning Engineer · Online Assessment
HardMachine Learning EngineerOnline AssessmentCoding & Algorithms

Last updated

This problem tests your ability to implement a sliding window peak detector, a bootstrapping ensemble sampler, and a centroid-based clustering algorithm from scratch.

Part 1: Local Maxima in a Stream

Given a stream of numbers, implement a function find_local_maxima(stream, window_size) that returns the indices of all local maxima. A local maximum is defined as an element that is strictly greater than its neighbors within a window of size k (i.e., arr[i] is a local maximum if arr[i] > arr[j] for all j in [i-k, i+k] where j != i).

Part 2: Bootstrap Aggregation (Bagging)

Given a list of n training samples and an ensemble size m, implement a function get_bootstrap_samples(data, m) that returns m datasets, each of size n, sampled with replacement. Each sample must return the data points chosen for that bootstrap iteration.

Part 3: K-Means Clustering

Implement a k_means(data, k, iterations) function that performs K-means clustering on a 2D dataset. Start with the first k points in the dataset as the initial centroids. Return the final centroid coordinates after the specified number of iterations.

Constraints

  • stream length: up to 10^5.
  • data points: 2D coordinates (x, y).
  • k < number of points.

Example

# Local Maxima
stream = [1, 5, 2, 4, 3]
window_size = 1 # Only immediate neighbors
# Output: [1, 3] (indices of values 5 and 4)

# Bagging
# If data = [A, B, C], m=2, a possible output:
# [[A, A, C], [B, C, B]]

Hints

Hint 1

For local maxima, use a sliding window approach or a monotonic queue to keep track of the maximum within the current range efficiently.

Hint 2

For bagging, use a random number generator to pick indices from the input range [0, n-1] independently for each of the n spots in a bootstrap sample.

Hint 3

For K-means, update centroids by calculating the mean of all points assigned to the nearest existing centroid in each iteration.

Follow-up questions

  • How would you optimize the K-means implementation if the number of dimensions is very high?
  • What is the time complexity of the local maxima detection, and can you improve it if the window size is constant?
  • How does the choice of k and the number of bootstrap samples affect the bias-variance tradeoff in an ensemble model?