Bagging Classifier with Supplied Decision Trees

Implement the bagging part of a classification model. You are given floating-point feature matrices xTrain and xTest, integer training labels yTrain, the number of supplied base classifiers nEstimators, and a reproducible random seed. Row xTrain[i] has label yTrain[i].

The complete templates below create the supplied classifier array and random generator. Complete the marked sections to perform these three operations:

1. Build one bootstrap training sample for each classifier by drawing training rows with replacement. Keep each selected row paired with its original label.
2. Train each supplied classifier on its own bootstrap sample by calling its fit method.
3. Predict every test row with every trained classifier. Return one integer label per test row in its original order: choose the most frequent predicted label, and choose the smaller label when votes tie.

Use the provided helper implementations unchanged. You are implementing bagging, so you do not need to implement decision-tree training or the random generator. Do not add external libraries. Replace a minimal generated editor stub with the complete template for your language below before filling the marked sections.

Deterministic practice rules

For this exercise, assume each bootstrap sample contains exactly n = xTrain.length rows. Process classifiers in array order. Use one random generator initialized once with seed; for each sampled row call its next-index method exactly once with n. Do not reset the generator between classifiers, deduplicate sampled rows, or shuffle training data.

The supplied generator replaces its state with (48271 * state) mod 2147483647 and then returns state mod n. Its code already handles the required integer width.

For this exercise, assume the supplied base learners are deterministic depth-one CART decision trees. The provided fit method considers the midpoint between every pair of adjacent distinct values in each feature and sends values less than or equal to the midpoint left. It selects the split with the largest strictly positive decrease in weighted Gini impurity; equal-quality splits prefer the smaller feature index and then the smaller threshold. If no split improves impurity, it uses a single leaf. A leaf predicts the most frequent label in its training sample, breaking ties toward the smaller label. Duplicate sampled rows count separately.

Gini impurity is 1 - sum(p[c] * p[c]), where p[c] is the fraction of rows with class c. A split's impurity is the row-count-weighted average of its two children. These details define the supplied helper's behavior; the helper is already complete.

For this exercise, assume an empty xTest returns an empty array. Class labels may be negative and need not be consecutive.

Supplied templates

Choose one complete template. Only replace the marked bagging sections and any placeholder return; keep the supplied tree and random-generator code.

Python

class SuppliedTree:
    # Supplied deterministic depth-one CART tree. Do not edit.
    def fit(self, rows, labels):
        def majority(values):
            counts = {}
            for value in values:
                counts[value] = counts.get(value, 0) + 1
            return min(counts, key=lambda value: (-counts[value], value))
        def squares(values):
            counts = {}
            for value in values:
                counts[value] = counts.get(value, 0) + 1
            return sum(count * count for count in counts.values())
        self.label = majority(labels)
        self.feature = -1
        n = len(rows)
        best_num, best_den = squares(labels), n
        for feature in range(len(rows[0])):
            values = sorted(set(row[feature] for row in rows))
            for index in range(len(values) - 1):
                threshold = (values[index] + values[index + 1]) / 2
                left = [labels[i] for i in range(n) if rows[i][feature] <= threshold]
                right = [labels[i] for i in range(n) if rows[i][feature] > threshold]
                a, b = len(left), len(right)
                num = squares(left) * b + squares(right) * a
                den = a * b
                if num * best_den > best_num * den:
                    best_num, best_den = num, den
                    self.feature, self.threshold = feature, threshold
                    self.left, self.right = majority(left), majority(right)
    def predict(self, row):
        if self.feature == -1:
            return self.label
        return self.left if row[self.feature] <= self.threshold else self.right

class SuppliedRng:
    # Supplied cross-language RNG. Do not edit.
    def __init__(self, seed):
        self.state = seed
    def next_index(self, size):
        self.state = (48271 * self.state) % 2147483647
        return self.state % size

class Solution:
    def baggingPredict(self, xTrain, yTrain, xTest, nEstimators, seed):
        rng = SuppliedRng(seed)
        classifiers = [SuppliedTree() for _ in range(nEstimators)]
        # Implement this: sample n paired rows with replacement for each classifier.
        # Implement this: fit each classifier on its own sample.
        # Implement this: predict and vote for every test row, breaking ties downward.
        return []

Java

// Supplied deterministic depth-one CART tree. Do not edit.
class SuppliedTree {
    int label, feature = -1, left, right;
    double threshold;
    int majority(int[] labels) {
        java.util.TreeMap<Integer,Integer> counts = new java.util.TreeMap<>();
        for (int value : labels) counts.put(value, counts.getOrDefault(value, 0) + 1);
        int answer = labels[0], best = -1;
        for (java.util.Map.Entry<Integer,Integer> entry : counts.entrySet())
            if (entry.getValue() > best) { best = entry.getValue(); answer = entry.getKey(); }
        return answer;
    }
    long squares(int[] labels) {
        java.util.HashMap<Integer,Integer> counts = new java.util.HashMap<>();
        for (int value : labels) counts.put(value, counts.getOrDefault(value, 0) + 1);
        long result = 0;
        for (int count : counts.values()) result += (long) count * count;
        return result;
    }
    void fit(double[][] rows, int[] labels) {
        label = majority(labels); feature = -1;
        int n = rows.length;
        long bestNum = squares(labels), bestDen = n;
        for (int f = 0; f < rows[0].length; f++) {
            java.util.TreeSet<Double> unique = new java.util.TreeSet<>();
            for (double[] row : rows) unique.add(row[f]);
            Double[] values = unique.toArray(new Double[0]);
            for (int k = 0; k + 1 < values.length; k++) {
                double t = (values[k] + values[k + 1]) / 2;
                int a = 0;
                for (double[] row : rows) if (row[f] <= t) a++;
                int b = n - a, li = 0, ri = 0;
                int[] ly = new int[a], ry = new int[b];
                for (int i = 0; i < n; i++) {
                    if (rows[i][f] <= t) ly[li++] = labels[i];
                    else ry[ri++] = labels[i];
                }
                long num = squares(ly) * b + squares(ry) * a;
                long den = (long) a * b;
                if (num * bestDen > bestNum * den) {
                    bestNum = num; bestDen = den;
                    feature = f; threshold = t; left = majority(ly); right = majority(ry);
                }
            }
        }
    }
    int predict(double[] row) {
        return feature == -1 ? label : row[feature] <= threshold ? left : right;
    }
}
// Supplied cross-language RNG. Do not edit.
class SuppliedRng {
    long state;
    SuppliedRng(int seed) { state = seed; }
    int nextIndex(int size) {
        state = (48271L * state) % 2147483647L;
        return (int) (state % size);
    }
}

public int[] baggingPredict(double[][] xTrain, int[] yTrain, double[][] xTest, int nEstimators, int seed) {
    SuppliedRng rng = new SuppliedRng(seed);
    SuppliedTree[] classifiers = new SuppliedTree[nEstimators];
    for (int i = 0; i < nEstimators; i++) classifiers[i] = new SuppliedTree();
    // Implement this: sample n paired rows with replacement for each classifier.
    // Implement this: fit each classifier on its own sample.
    // Implement this: predict and vote for every test row, breaking ties downward.
    // write your code here
}

C++

// Supplied deterministic depth-one CART tree. Do not edit.
struct SuppliedTree {
    int label, feature = -1, left, right;
    double threshold;
    int majority(const vector<int>& labels) {
        map<int,int> counts;
        for (int value : labels) counts[value]++;
        int answer = labels[0], best = -1;
        for (auto item : counts) if (item.second > best) {
            best = item.second; answer = item.first;
        }
        return answer;
    }
    long long squares(const vector<int>& labels) {
        map<int,int> counts;
        for (int value : labels) counts[value]++;
        long long result = 0;
        for (auto item : counts) result += 1LL * item.second * item.second;
        return result;
    }
    void fit(const vector<vector<double>>& rows, const vector<int>& labels) {
        label = majority(labels); feature = -1;
        int n = rows.size();
        long long bestNum = squares(labels), bestDen = n;
        for (int f = 0; f < (int) rows[0].size(); f++) {
            set<double> unique;
            for (const auto& row : rows) unique.insert(row[f]);
            vector<double> values(unique.begin(), unique.end());
            for (int k = 0; k + 1 < (int) values.size(); k++) {
                double t = (values[k] + values[k + 1]) / 2;
                vector<int> ly, ry;
                for (int i = 0; i < n; i++)
                    (rows[i][f] <= t ? ly : ry).push_back(labels[i]);
                long long a = ly.size(), b = ry.size();
                long long num = squares(ly) * b + squares(ry) * a, den = a * b;
                if (num * bestDen > bestNum * den) {
                    bestNum = num; bestDen = den;
                    feature = f; threshold = t; left = majority(ly); right = majority(ry);
                }
            }
        }
    }
    int predict(const vector<double>& row) const {
        return feature == -1 ? label : row[feature] <= threshold ? left : right;
    }
};
// Supplied cross-language RNG. Do not edit.
struct SuppliedRng {
    long long state;
    SuppliedRng(int seed) : state(seed) {}
    int nextIndex(int size) {
        state = (48271LL * state) % 2147483647LL;
        return (int) (state % size);
    }
};

class Solution {
public:
    vector<int> baggingPredict(vector<vector<double>> xTrain, vector<int> yTrain, vector<vector<double>> xTest, int nEstimators, int seed) {
        SuppliedRng rng(seed);
        vector<SuppliedTree> classifiers(nEstimators);
        // Implement this: sample n paired rows with replacement for each classifier.
        // Implement this: fit each classifier on its own sample.
        // Implement this: predict and vote for every test row, breaking ties downward.
        return {};
    }
};

Go

// Supplied deterministic depth-one CART tree. Do not edit.
type SuppliedTree struct {
    label, feature, left, right int
    threshold float64
}
func treeMajority(labels []int) int {
    counts := map[int]int{}
    for _, value := range labels { counts[value]++ }
    answer, best := labels[0], -1
    for value, count := range counts {
        if count > best || (count == best && value < answer) { answer, best = value, count }
    }
    return answer
}
func treeSquares(labels []int) int64 {
    counts := map[int]int{}
    for _, value := range labels { counts[value]++ }
    result := int64(0)
    for _, count := range counts { result += int64(count) * int64(count) }
    return result
}
func (tree *SuppliedTree) Fit(rows [][]float64, labels []int) {
    tree.label, tree.feature = treeMajority(labels), -1
    n := len(rows)
    bestNum, bestDen := treeSquares(labels), int64(n)
    for f := 0; f < len(rows[0]); f++ {
        values := []float64{}
        for _, row := range rows { values = append(values, row[f]) }
        // Insertion sort avoids additional imports in the supplied template.
        for i := 1; i < len(values); i++ {
            for j := i; j > 0 && values[j] < values[j-1]; j-- { values[j], values[j-1] = values[j-1], values[j] }
        }
        for k := 0; k+1 < len(values); k++ {
            if values[k] == values[k+1] { continue }
            threshold := (values[k] + values[k+1]) / 2
            leftLabels, rightLabels := []int{}, []int{}
            for i, row := range rows {
                if row[f] <= threshold { leftLabels = append(leftLabels, labels[i])
                } else { rightLabels = append(rightLabels, labels[i]) }
            }
            a, b := int64(len(leftLabels)), int64(len(rightLabels))
            num, den := treeSquares(leftLabels)*b+treeSquares(rightLabels)*a, a*b
            if num*bestDen > bestNum*den {
                bestNum, bestDen = num, den
                tree.feature, tree.threshold = f, threshold
                tree.left, tree.right = treeMajority(leftLabels), treeMajority(rightLabels)
            }
        }
    }
}
func (tree *SuppliedTree) Predict(row []float64) int {
    if tree.feature == -1 { return tree.label }
    if row[tree.feature] <= tree.threshold { return tree.left }
    return tree.right
}
// Supplied cross-language RNG. Do not edit.
type SuppliedRng struct { state int64 }
func (rng *SuppliedRng) NextIndex(size int) int {
    rng.state = (48271*rng.state) % 2147483647
    return int(rng.state % int64(size))
}

func baggingPredict(xTrain [][]float64, yTrain []int, xTest [][]float64, nEstimators int, seed int) []int {
    rng := SuppliedRng{state: int64(seed)}
    classifiers := make([]SuppliedTree, nEstimators)
    _ = rng
    _ = classifiers
    // Implement this: sample n paired rows with replacement for each classifier.
    // Implement this: fit each classifier on its own sample.
    // Implement this: predict and vote for every test row, breaking ties downward.
    return []int{}
}