How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

What difficulty level is this interview question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Goldman Sachs.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at Goldman Sachs during technical interviews.

Complete decision tree and gradient descent functions

Q: Complete decision tree and gradient descent functions

This question evaluates implementation skills in supervised machine learning and numerical optimization, specifically computing Gini impurity and selecting optimal binary splits for a decision tree alongside deriving and applying a single-step gradient descent update for linear regression.

You are given partially implemented code and must complete key functions. Implement the missing parts with correct logic and reasonable efficiency.

Task A) Decision tree split function (classification)

You are building a binary decision tree classifier for tabular numeric features.

Implement:

gini(y) that computes the Gini impurity of labels y (binary labels 0/1).
best_split(X, y) that finds the best (feature_index, threshold) to split on.

Definitions/requirements:

X is an n x d matrix of floats.
y is length n , values in {0,1} .
A split is defined by (j, t) meaning:
- left child: samples with X[i][j] <= t
- right child: samples with X[i][j] > t
Choose the split that minimizes weighted Gini impurity :

$G_{split} = \frac{n_L}{n} G(y_L) + \frac{n_R}{n} G(y_R)$

If a split would produce an empty side, it is invalid.
Return None if no valid split exists.

Constraints:

1 <= n <= 2e4 , 1 <= d <= 50
Aim for ~ $O(nd \log n)$ or better.

Task B) Single-step gradient descent update (linear regression)

You are fitting linear regression with mean squared error:

$L(w,b) = \frac{1}{n}\sum_{i=1}^n (w^\top x_i + b - y_i)^2$

Implement:

gd_step(X, y, w, b, lr) that performs one gradient descent update and returns (new_w, new_b) .

Requirements:

X is n x d , y length n (real-valued).
w length d , b scalar.
Use the correct gradients for MSE (include the averaging over n ).
Must work for n=1 and d=1 .

Notes

You may assume Python-like pseudocode and basic numeric operations (no need for full training loop).
Handle edge cases cleanly (constant labels, identical feature values, etc.).

You are given partially implemented code and must complete key functions. Implement the missing parts with correct logic and reasonable efficiency.

Task A) Decision tree split function (classification)

You are building a binary decision tree classifier for tabular numeric features.

Implement:

gini(y) that computes the Gini impurity of labels y (binary labels 0/1).
best_split(X, y) that finds the best (feature_index, threshold) to split on.

Definitions/requirements:

X is an n x d matrix of floats.
y is length n , values in {0,1} .
A split is defined by (j, t) meaning:
- left child: samples with X[i][j] <= t
- right child: samples with X[i][j] > t
Choose the split that minimizes weighted Gini impurity :

$G_{split} = \frac{n_L}{n} G(y_L) + \frac{n_R}{n} G(y_R)$

If a split would produce an empty side, it is invalid.
Return None if no valid split exists.

Constraints:

1 <= n <= 2e4 , 1 <= d <= 50
Aim for ~ $O(nd \log n)$ or better.

Task B) Single-step gradient descent update (linear regression)

You are fitting linear regression with mean squared error:

$L(w,b) = \frac{1}{n}\sum_{i=1}^n (w^\top x_i + b - y_i)^2$

Implement:

gd_step(X, y, w, b, lr) that performs one gradient descent update and returns (new_w, new_b) .

Requirements:

X is n x d , y length n (real-valued).
w length d , b scalar.
Use the correct gradients for MSE (include the averaging over n ).
Must work for n=1 and d=1 .

Notes

You may assume Python-like pseudocode and basic numeric operations (no need for full training loop).
Handle edge cases cleanly (constant labels, identical feature values, etc.).

Complete decision tree and gradient descent functions

Quick Overview

Task A) Decision tree split function (classification)

Task B) Single-step gradient descent update (linear regression)

Notes

Comments (0)

Complete decision tree and gradient descent functions

Quick Overview

Task A) Decision tree split function (classification)

Task B) Single-step gradient descent update (linear regression)

Notes

Comments (0)