How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

What difficulty level is this interview question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Coinbase.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at Coinbase during technical interviews.

Implement local maxima, bagging, and k-means | Coinbase Interview Question

Q: Implement local maxima, bagging, and k-means

This set of tasks evaluates algorithmic problem-solving and implementation skills across array processing (local maxima), ensemble methods (bagging classifier), and clustering (k-means), testing competencies in data structures, statistical resampling, numerical computation, and scalable code in the Coding & Algorithms and Machine Learning domains.

You have 70 minutes for three programming tasks.

Task 1 — Find local maxima

Given an integer array a of length n (1 <= n <= 2e5), return all indices i that are local maxima.

Definition:

For 0 < i < n-1 : a[i] is a local maximum if a[i] > a[i-1] and a[i] > a[i+1] .
For endpoints: i = 0 is a local maximum if n==1 or a[0] > a[1] ; i = n-1 is a local maximum if a[n-1] > a[n-2] .

Output the indices in increasing order.

Task 2 — Implement a bagging classifier

Implement a BaggingClassifier that trains M base classifiers on bootstrap samples and predicts by majority vote.

You are given a BaseClassifier object with:

fit(X, y)
predict(X) which returns a label for each row of X

Your BaggingClassifier should support:

constructor parameters: n_estimators=M , sample_size (default = len(X) ), random_seed
fit(X, y) that trains M independent base models on bootstrap samples (sample with replacement)
predict(X) that returns the majority-vote label per example; if there is a tie, return the smallest label.

Constraints: N = len(X) <= 2e5, M <= 200.

Task 3 — Implement k-means clustering

Implement k-means clustering given:

X : N x D array of floats
k : number of clusters
dist(p, q) : provided distance function between two points
max_iter (e.g., 100)

Requirements:

Initialize centroids using the first k points of X (deterministic).
Repeat until convergence or max_iter :
- Assign each point to the nearest centroid (break ties by choosing the smallest centroid index).
- Recompute each centroid as the mean of its assigned points.
- If a cluster becomes empty, keep its centroid unchanged.

Return final centroids and the cluster assignment for each point.

(You may assume 1 <= k <= N, D <= 50.)

You have 70 minutes for three programming tasks.

Task 1 — Find local maxima

Given an integer array a of length n (1 <= n <= 2e5), return all indices i that are local maxima.

Definition:

For 0 < i < n-1 : a[i] is a local maximum if a[i] > a[i-1] and a[i] > a[i+1] .
For endpoints: i = 0 is a local maximum if n==1 or a[0] > a[1] ; i = n-1 is a local maximum if a[n-1] > a[n-2] .

Output the indices in increasing order.

Task 2 — Implement a bagging classifier

Implement a BaggingClassifier that trains M base classifiers on bootstrap samples and predicts by majority vote.

You are given a BaseClassifier object with:

fit(X, y)
predict(X) which returns a label for each row of X

Your BaggingClassifier should support:

constructor parameters: n_estimators=M , sample_size (default = len(X) ), random_seed
fit(X, y) that trains M independent base models on bootstrap samples (sample with replacement)
predict(X) that returns the majority-vote label per example; if there is a tie, return the smallest label.

Constraints: N = len(X) <= 2e5, M <= 200.

Task 3 — Implement k-means clustering

Implement k-means clustering given:

X : N x D array of floats
k : number of clusters
dist(p, q) : provided distance function between two points
max_iter (e.g., 100)

Requirements:

Initialize centroids using the first k points of X (deterministic).
Repeat until convergence or max_iter :
- Assign each point to the nearest centroid (break ties by choosing the smallest centroid index).
- Recompute each centroid as the mean of its assigned points.
- If a cluster becomes empty, keep its centroid unchanged.

Return final centroids and the cluster assignment for each point.

(You may assume 1 <= k <= N, D <= 50.)

Implement local maxima, bagging, and k-means

Quick Overview

Task 1 — Find local maxima

Task 2 — Implement a bagging classifier

Task 3 — Implement k-means clustering

Comments (0)

Implement local maxima, bagging, and k-means

Quick Overview

Task 1 — Find local maxima

Task 2 — Implement a bagging classifier

Task 3 — Implement k-means clustering

Comments (0)