Bird
Raised Fist0

Implement Random Forest - Bagging, Feature Sampling

CODINGintermediateInterview freq: medium
Choose your preparation mode6 modes available
LearnTraceDebugTrade-offChallenge
🎯
Implement a Random Forest Classifier with Bagging and Feature Sampling
30 min · mid
mid

You are tasked with implementing a Random Forest classifier from scratch using NumPy. The dataset is large, with 1 million samples and 100 features. The model must handle missing values and be optimized for inference speed. You have 30 minutes to complete the implementation.

Given Info
  • Dataset size: 1 million samples, 100 features
  • Must handle missing values
  • Optimize for inference speed
  • Use NumPy only, no sklearn or other libraries
  • Focus on bagging and feature sampling
📋
Guided Steps
1/4
Step 1
Understanding Bagging
How will you implement bagging in your Random Forest?
💡 Hint
Consider how you can create multiple subsets of your data for training.
Key Decision
Use bootstrapping to create diverse training subsets because it reduces overfitting.
Interviewer Expectation
Mid: Implements basic bootstrapping. Senior: Explains how bootstrapping increases model diversity and reduces variance.
⚠️Common Wrong Answer
Using the entire dataset for each tree, leading to overfitting and lack of diversity.
Step 2
Feature Sampling Strategy
How will you implement feature sampling in your Random Forest?
💡 Hint
Think about how reducing the number of features can help with model variance.
Key Decision
Randomly select a subset of features for each tree because it decorrelates the trees.
Interviewer Expectation
Mid: Randomly selects features. Senior: Justifies the number of features chosen and its impact on model performance.
⚠️Common Wrong Answer
Using all features for each tree, which doesn't reduce correlation between trees.
Step 3
Handling Missing Values
How will you handle missing values in your dataset?
💡 Hint
Consider simple imputation strategies that can be applied during tree training.
Key Decision
Use mean/mode imputation because it is simple and effective for tree-based models.
Interviewer Expectation
Mid: Implements basic imputation. Senior: Discusses impact of imputation on model bias and variance.
⚠️Common Wrong Answer
Ignoring missing values, which can lead to errors during training.
Step 4
Optimizing Inference Speed
What strategies will you use to optimize inference speed?
💡 Hint
Think about how you can reduce computation during prediction.
Key Decision
Use pre-computed decision paths because it reduces computation at inference time.
Interviewer Expectation
Mid: Implements basic prediction. Senior: Optimizes prediction by caching decision paths.
⚠️Common Wrong Answer
Recomputing decision paths for each prediction, leading to slower inference.
📊
Scoring Rubric
▼ Show
Must Have - 60%
  • Implements bootstrapping for bagging
  • Randomly selects features for each tree
  • Handles missing values appropriately
  • Optimizes for inference speed
Good to Have - 30%
  • Explains the impact of bootstrapping on variance
  • Justifies the number of features chosen for sampling
  • Discusses the trade-offs of different imputation strategies
  • Implements caching for faster inference
Bonus - 10%
  • Quantifies the impact of feature sampling on model performance
  • Discusses potential improvements for handling missing values
  • Explains the theoretical basis for bagging and feature sampling
✅
Model Answer
▼ Reveal

The ideal solution implements a Random Forest classifier using bootstrapping for bagging and random feature sampling to reduce overfitting and improve model diversity. Missing values are handled through simple imputation, and inference speed is optimized by caching decision paths.

Key Decisions
  • Implemented bootstrapping to create diverse training subsets, reducing overfitting.
  • Randomly selected a subset of features for each tree to decorrelate the trees.
  • Used mean/mode imputation to handle missing values, maintaining model robustness.
  • Optimized inference speed by caching decision paths, reducing computation during prediction.
Anti-patterns
Using the entire dataset for each tree, leading to overfitting.
Using all features for each tree, resulting in correlated trees.
Ignoring missing values, causing errors during training.
Recomputing decision paths for each prediction, slowing down inference.

Practice

(1/5)
1. 
import numpy as np

def iou(box1, box2):
    x1 = max(box1[0], box2[0])
    y1 = max(box1[1], box2[1])
    x2 = min(box1[2], box2[2])
    y2 = min(box1[3], box2[3])
    intersection = max(0, x2 - x1) * max(0, y2 - y1)
    area1 = (box1[2] - box1[0]) * (box1[3] - box1[1])
    area2 = (box2[2] - box2[0]) * (box2[3] - box2[1])
    union = area1 + area2 - intersection
    return intersection / union

box1 = [1, 1, 3, 3]
box2 = [2, 2, 4, 4]
print(iou(box1, box2))
easy
A. 0.5
B. 0.25
C. 0.14285714285714285
D. 0.3333333333333333

Solution

  1. Step 1: Calculate intersection and union areas

    Intersection area is 1, union area is 7.

  2. Step 2: Compute IoU

    IoU = 1/7 = 0.14285714285714285.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Intersection over Union formula [OK]
Hint: Intersection over Union formula [OK]
Common Mistakes:
2. What is the time complexity of computing the softmax function for an input array of size n?
easy
A. O(n^2)
B. O(n log n)
C. O(1)
D. O(n)

Solution

  1. Step 1: Analyze operations

    Softmax involves computing exponentials and a sum, both linear in n.

  2. Step 2: Determine complexity

    Each operation is O(n), so overall complexity is O(n).

  3. Final Answer:

    Option D -> Option D

  4. Quick Check:

    Softmax is linear in input size [OK]
Hint: Softmax is linear in input size [OK]
Common Mistakes:
3. In a decision tree, how would you handle a dataset with continuous features?
medium
A. Ignore continuous features.
B. Use one-hot encoding for continuous features.
C. Discretize continuous features into bins.
D. Use continuous features directly without modification.

Solution

  1. Step 1: Consider handling continuous features

    Discretizing into bins allows decision trees to handle continuous data effectively.

  2. Step 2: Eliminate wrong options

    One-hot encoding (A) is for categorical data; ignoring (C) loses information; using directly (D) can lead to overfitting.

  3. Final Answer:

    Option C -> Option C

  4. Quick Check:

    Continuous? Discretize into bins [OK]
Hint: Continuous? Discretize into bins [OK]
Common Mistakes:
4. You need to apply non-max suppression on a batch of images. Which approach is most efficient?
medium
A. Apply non-max suppression independently on each image.
B. Concatenate all boxes from all images and apply non-max suppression once.
C. Apply non-max suppression on the image with the highest number of boxes only.
D. Apply non-max suppression on images with scores above a certain threshold.

Solution

  1. Step 1: Consider independence of images

    Each image's boxes are independent, so process them separately.

  2. Step 2: Evaluate efficiency

    Concatenating boxes would mix unrelated data, and focusing on one image or thresholding scores misses other valid boxes.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Process each image independently [OK]
Hint: Process each image independently [OK]
Common Mistakes:
5. In the context of implementing linear regression with gradient descent, how would you handle a dataset with missing values?
medium
A. Impute missing values using the mean of each feature.
B. Ignore missing values during training.
C. Replace missing values with zeros.
D. Remove any samples with missing values.

Solution

  1. Step 1: Consider impact of missing values

    Ignoring or zero-filling can bias results; removing samples reduces data.

  2. Step 2: Choose appropriate imputation

    Mean imputation is a common strategy that maintains dataset size and reduces bias.

  3. Final Answer:

    Option A -> Option A

  4. Quick Check:

    Mean imputation balances bias and data retention. [OK]
Hint: Mean imputation balances bias and data retention. [OK]
Common Mistakes:
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard