Goldman Sachs·Software Engineer·Technical Phone Screen·Senior

SeniorPrefer not to say

May 2026

Summary

Two-part technical interview for a quant engineering role at Goldman Sachs. The first half was a conceptual deep-dive into sampling methods, and the second half had me coding a biased random walk on a manifold live, which was a lot more involved than I expected.

Questions Asked (2)

Walk through the main methods for sampling from a target probability distribution, covering inverse CDF, rejection sampling, MCMC, and importance sampling. What are the trade-offs and when would you reach for each?

Technical Trade-offsAlgorithms & Data Structures

Author's notes

This part actually went okay.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Structure your answer by first categorizing the methods into direct sampling (inverse CDF), rejection-based, and approximate/iterative methods (MCMC, importance sampling). For each, briefly explain the core idea, then compare them on key dimensions like computational cost, ease of implementation, and applicability to different distributions. Finally, give concrete scenarios where each method shines, emphasizing practical trade-offs relevant to software engineering at a financial firm.

Pro tip: Mention that in practice, libraries like NumPy or SciPy often provide optimized implementations, but understanding the underlying algorithms helps debug performance issues and choose the right method for high-dimensional or complex distributions common in finance (e.g., risk models).

1. Inverse CDF (Inverse Transform Sampling)

Explain that it generates samples by inverting the cumulative distribution function: draw u ~ Uniform(0,1), then return F^{-1}(u). It's exact and efficient if F^{-1} is available in closed form.

2. Rejection Sampling

Describe how it samples from a simpler proposal distribution and accepts/rejects based on a ratio to the target density. It's exact but can be inefficient if the proposal is a poor fit, especially in high dimensions.

3. Markov Chain Monte Carlo (MCMC)

Introduce MCMC as a family of algorithms (e.g., Metropolis-Hastings, Gibbs sampling) that construct a Markov chain whose stationary distribution is the target. It's useful for complex, high-dimensional distributions but samples are correlated and require burn-in.

4. Importance Sampling

Explain that it doesn't generate samples from the target directly; instead, it draws from a proposal and reweights to estimate expectations. It's useful for variance reduction and rare-event simulation, but can suffer from high variance if the proposal is poor.

5. Trade-offs and Use Cases

Summarize trade-offs: inverse CDF is fast and exact but limited to invertible CDFs; rejection sampling is exact but can be slow in high dimensions; MCMC is flexible but computationally intensive and approximate; importance sampling is good for expectations but not for generating independent samples. Give examples: inverse CDF for exponential, rejection for truncated normals, MCMC for Bayesian posteriors, importance sampling for option pricing.

Key Points to Mention

Inverse CDF requires the inverse of the CDF, which may not exist in closed form; numerical inversion can be used but adds cost.
Rejection sampling's efficiency depends on the acceptance rate, which drops exponentially with dimension (curse of dimensionality).
MCMC methods produce correlated samples and need convergence diagnostics (e.g., trace plots, Gelman-Rubin).
Importance sampling can estimate expectations without sampling from the target, but the weights can have high variance if the proposal is not well-matched.
In practice, hybrid approaches exist (e.g., adaptive MCMC, sequential Monte Carlo) to mitigate issues.
For software engineers, consider implementation complexity, runtime, and memory; often use libraries but understand the algorithms for tuning and debugging.

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

Write a sampler for a biased random walk on a manifold (like a sphere or torus): how do you parameterize positions, propose steps that stay tangent to the manifold, apply a bias toward a target region, and handle accept/reject?

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

This one got me.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the manifold and target distribution, then outline a Metropolis-Hastings algorithm with a tangent-space proposal and a bias term. Emphasize numerical stability and geometric correctness, and discuss trade-offs between simplicity and efficiency.

Pro tip: Mention that the bias should be incorporated into the acceptance ratio to maintain detailed balance, and that using exponential map or retraction ensures proposals stay on the manifold without projection errors.

1. Parameterize the manifold

Choose a parameterization that covers the manifold (e.g., spherical coordinates for a sphere, or periodic coordinates for a torus). Ensure the parameterization is smooth and handles boundaries or singularities.

2. Propose tangent steps

At the current point, sample a direction in the tangent space (e.g., from a Gaussian) and map it to the manifold using the exponential map or a retraction. This keeps the proposal on the manifold.

3. Apply bias toward target

Modify the proposal distribution or the acceptance ratio to favor moves toward the target region. For example, add a drift term to the tangent step or include a bias potential in the acceptance probability.

4. Compute acceptance probability

Use the Metropolis-Hastings formula: accept with probability min(1, (target(x') * proposal(x|x') * bias(x')) / (target(x) * proposal(x'|x) * bias(x))). Account for the Jacobian of the parameterization if needed.

5. Handle accept/reject and iterate

Accept or reject the proposed point, and repeat. Monitor acceptance rate and tune step size for efficiency. Discuss potential issues like high rejection or slow mixing.

Key Points to Mention

Use of exponential map or retraction to move along the manifold
Metropolis-Hastings acceptance ratio with bias term
Handling of manifold boundaries and singularities in parameterization
Trade-offs between proposal complexity and acceptance rate
Numerical stability and computational cost of geometric operations
Ensuring detailed balance and ergodicity of the Markov chain

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