← Goldman Sachs Interview Insights

Goldman Sachs·Machine Learning Engineer·Technical Phone Screen·Intermediate

Intermediate
Jun 2026

Summary

Goldman Sachs ML Engineer coding round, two back-to-back implementation problems covering decision tree logic and linear regression. Pretty standard stuff for the role but the details matter a lot and they're watching how you handle edge cases.

Questions Asked (2)

Q1

Implement a Gini impurity function and a best-split finder for a binary decision tree classifier, where the split minimizes weighted Gini impurity across all features and candidate thresholds.

Algorithms & Data StructuresTechnical Trade-offs
Author's notes

The gini function itself took me maybe two minutes.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clearly defining Gini impurity and the weighted Gini impurity for a split, then outline an efficient algorithm that sorts feature values and evaluates candidate thresholds. Emphasize computational complexity and practical optimizations like sorting once per feature and using cumulative sums.

Pro tip: Mention that for large datasets, you can avoid sorting by using histogram-based binning, which is common in production systems like XGBoost and LightGBM. Also, highlight that the best split should consider only midpoints between consecutive unique values to reduce redundant evaluations.

1. Define Gini Impurity

Explain the formula for Gini impurity for a single node: 1 - sum(p_i^2), where p_i is the proportion of class i. For binary classification, this simplifies to 2*p*(1-p).

2. Define Weighted Gini for a Split

For a split, compute the weighted average of the Gini impurities of the left and right child nodes, weighted by the number of samples in each child. This is the objective to minimize.

3. Outline the Best Split Algorithm

For each feature, sort the unique values, consider midpoints as candidate thresholds, and compute the weighted Gini for each. Track the minimum and the corresponding feature and threshold.

4. Optimize with Cumulative Statistics

Use cumulative sums of class counts to compute Gini for each threshold in O(n) after sorting, avoiding recomputation from scratch. This reduces overall complexity to O(n log n) per feature.

5. Discuss Complexity and Trade-offs

State the time complexity: O(d * n log n) for d features and n samples. Mention that for high-dimensional data, feature subsampling or histogram binning can be used to improve efficiency.

Key Points to Mention

  • Gini impurity formula and its interpretation as a measure of node purity.
  • Weighted Gini impurity for evaluating split quality.
  • Efficient computation using sorting and cumulative sums to avoid O(n^2) complexity.
  • Handling of categorical features (e.g., one-hot encoding or grouping by frequency).
  • Stopping criteria for tree growth (e.g., max depth, min samples per leaf) to prevent overfitting.
  • Trade-offs between exact greedy split finding and approximate methods like histogram binning.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.

Q2

Implement a single gradient descent update step for linear regression with mean squared error loss, returning the updated weights and bias.

Algorithms & Data StructuresTechnical Trade-offs
Author's notes

Easier than the first one but I fumbled the 1/n factor at first, wrote the gradient without averaging and had to correct it when they asked me to verify for n=1.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clearly defining the linear regression model and mean squared error loss, then derive the gradients with respect to weights and bias. Implement the update step using the gradients and a learning rate, and finally verify the update with a simple example.

Pro tip: Mention that in practice, you would use vectorized operations for efficiency and that the gradients can be computed in closed form for linear regression, but the same pattern applies to more complex models.

1. Define the model and loss

State the linear regression hypothesis: y_pred = Xw + b, and the MSE loss: L = (1/n) * sum((y_pred - y)^2).

2. Compute gradients

Derive the gradients of the loss with respect to weights and bias: dL/dw = (2/n) * X^T (y_pred - y), dL/db = (2/n) * sum(y_pred - y).

3. Update parameters

Apply the gradient descent update: w_new = w - learning_rate * dL/dw, b_new = b - learning_rate * dL/db.

4. Implement and verify

Write the code for the update step, ensuring correct matrix dimensions, and test with a small dataset to confirm the loss decreases.

Key Points to Mention

  • Mean squared error loss function and its gradient derivation
  • Vectorized implementation for efficiency
  • Learning rate as a hyperparameter
  • Handling of bias term (can be incorporated into weights by adding a column of ones)
  • Numerical stability considerations (e.g., scaling features)
  • Connection to stochastic gradient descent and mini-batch variants

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.