Implement a Decision Tree Classifier and a Bagging Ensemble from Scratch
Company: Pinterest
Role: Machine Learning Engineer
Category: Machine Learning
Difficulty: easy
Interview Round: Online Assessment
Implement a decision tree classifier from scratch, then use it to build a bagging ensemble. This was the second of two from-scratch ML algorithm implementations in a timed, 75-minute online assessment for a machine learning engineering internship, so the goal is correct, readable code you can test quickly, not a complete library.
The report names the task only as "decision tree + bagging". The interface below is an assumption that makes it concrete: both models take a numeric feature matrix `X` with `n` rows and `d` columns and a label vector `y` of length `n`, and both expose `fit(X, y)` and `predict(X)`.
### Constraints and Clarifications
- Not reported: the split criterion, the stopping rules, the number of trees, how the ensemble combines votes, the input sizes, and whether NumPy is allowed. Ask, or state your assumptions.
- Assume numeric features with no missing values, and class labels that can be sorted.
### Clarifying Questions
- Classification only, or regression as well?
- Should results be reproducible through a seed parameter?
- May I use NumPy, and roughly how large are `n` and `d`?
### Part 1 — Decision tree classifier
Implement a binary decision tree. Each internal node tests one feature against a threshold and sends a row left or right; each leaf predicts a class. `fit` grows the tree greedily from the training data; `predict` routes each row from the root to a leaf.
```hint One pass per feature
Count how often your split search touches each row at a single node. Can all candidate thresholds for one feature be scored in one pass over that feature's sorted values?
```
#### Clarifying Questions for this Part
- Which impurity measure, Gini or entropy?
- Which stopping rules: a maximum depth, a minimum number of rows to split, a minimum impurity decrease?
- How should a leaf break a tie between equally common classes?
#### What This Part Should Cover
- An impurity measure and a threshold search per feature that never splits between equal values
- Stopping rules and the class stored in each leaf
- The cost of training and of predicting one row
### Part 2 — Bagging ensemble
Train `B` decision trees, each on a bootstrap sample of the training data, and predict by combining the trees' votes. The ensemble must give identical results for a fixed seed.
```hint Not every tree sees every class
A bootstrap sample can miss a class entirely. Make sure each tree's vote is still counted against the right class when the ensemble adds the votes up.
```
#### Clarifying Questions for this Part
- Is each bootstrap sample the same size as the training set, and drawn with replacement?
- A majority vote of predicted classes, or an average of the trees' class probabilities? How is a tied vote broken?
- Should the ensemble report an out-of-bag accuracy estimate?
#### What This Part Should Cover
- Seeded bootstrap sampling and training of each tree
- Vote aggregation with consistent class indexing across trees and a deterministic tie rule
- Why bagging reduces variance, which base trees benefit from it, and the out-of-bag estimate
### What a Strong Answer Covers
- States the criterion, stopping rules, voting and tie rules before coding
- Correct, deterministic code with one `fit`/`predict` interface shared by both models
- The time complexity of growing a tree, training the ensemble and predicting
- Edge cases: a pure node, a constant feature, a single training row, a class missing from a bootstrap sample
- Small, hand-checkable tests for each part
### Follow-up Questions
- What would you change to turn the bagging ensemble into a random forest, and why does that usually generalize better?
- Should the trees in a bagging ensemble be deep or shallow, and why is the answer different for boosting?
- How would you adapt both parts to regression?
- How would you estimate feature importance from the trained ensemble?
Overview: Implement a decision tree classifier from scratch and build a bagging ensemble of those trees, a hand-coding task from a machine learning engineering internship online assessment. It tests impurity-based threshold search, stopping rules, seeded bootstrap sampling, vote aggregation across trees, out-of-bag evaluation, and complexity.
Community answers
Answer by shbeni
an answer
Answer by ri164
class BaggingClassifier:
def init(self, n_estimators=10, max_depth=None, seed=0):
self.n_estimators = n_estimators
self.max_depth = max_depth
self.rng = random.Random(seed) # PROVIDED: use only this
self.trees = []
def bootstrap(self, X, y):
# implement this
X_samples = []
Y_samples = []
for i in range(len(X)):
index = self.rng.randrange(len(X))
X_samples.append(X[index])
Y_samples.append(y[index])
return X_samples, Y_samples
def fit(self, X, y):
self.trees = []
for i in range(self.n_estimators):
X_samples, Y_samples = self.bootstrap(X, y)
tree = DecisionTree(max_depth=self.max_depth)
tree.fit(X_samples, Y_samples)
self.trees.append(tree)
return self
def predict(self, X):
# implement this
all_tree_preds = []
for t in self.trees:
all_tree_preds.append(t.predict(X))
result = []
for row in range(len(X)):
counts = {}
for preds in all_tree_preds:
label = preds[row]
counts[label] = counts.get(label, 0) + 1
top = max(counts.values())
winners = []
for label in counts:
if counts[label] == top:
winners.append(label)
result.append(min(winners))
return result