Implement bagging with decision trees
Company: Pinterest
Role: Machine Learning Engineer
Category: Machine Learning
Difficulty: hard
Interview Round: Take-home Project
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.
Quick Answer: 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.