Implement bagging with decision trees
Company: Pinterest
Role: Machine Learning Engineer
Category: Machine Learning
Difficulty: hard
Interview Round: Online Assessment
Implement a simple **bagging (bootstrap aggregating) classifier** that uses decision trees as base learners.
You are given a template with a `DecisionTree` class that supports at least:
- `fit(X, y)`
- `predict(X)`
Implement these methods for a `BaggingClassifier` (do **not** use NumPy; use Python lists and the standard library):
1) `bootstrapping(X, y, seed=None)`: sample `n=len(X)` training examples **with replacement** and return `(X_sample, y_sample)`.
2) `fit(X, y)`: for `n_estimators` trees, create a bootstrap sample and train one tree per sample.
3) `predict(X)`: aggregate predictions from all trees and output the final prediction per row (e.g., **majority vote** for classification). Specify how you break ties.
Assume `X` is a list of feature vectors and `y` is a list of class labels.
Overview: This question evaluates a candidate's competency in ensemble learning and practical implementation skills, including bootstrap sampling, decision tree base learners, aggregation via majority voting with tie-breaking, and managing data using pure Python lists and standard library routines.
Read the full Pinterest Machine Learning Engineer interview experience this question came from
Community answers
Answer by swemleds
import random
from collections import Counter
class BaggingClassifier:
def init(self, n_estimators=10, seed=None):
self.n_estimators = n_estimators
self.seed = seed
self.trees = []
def bootstrapping(self, X, y, seed=None):
n = len(X)
# Create a local random generator for reproducibility
rng = random.Random(seed)
# Sample n indices WITH replacement
indices = [rng.randrange(n) for _ in range(n)]
# Select corresponding features and labels
X_sample = [X[i] for i in indices]
y_sample = [y[i] for i in indices]
return X_sample, y_sample
def fit(self, X, y):
# Reset previously trained trees
self.trees = []
for i in range(self.n_estimators):
# Generate a different bootstrap sample per tree
sample_seed = None if self.seed is None else self.seed + i
X_sample, y_sample = self.bootstrapping(
X, y, seed=sample_seed
)
# Create and train a new decision tree
tree = DecisionTree()
tree.fit(X_sample, y_sample)
# Store the trained tree
self.trees.append(tree)
return self
def predict(self, X):
if not self.trees:
raise ValueError("The classifier has not been fitted.")
# Collect predictions from every tree
# Shape: (n_estimators, n_samples)
all_predictions = [tree.predict(X) for tree in self.trees]
final_predictions = []
# Combine predictions for each sample
for votes in zip(*all_predictions):
counts = Counter(votes)
# Find the maximum number of votes
max_votes = max(counts.values())
# Collect classes tied for the most votes
winners = [
label for label, count in counts.items()
if count == max_votes