Goldman Sachs·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

May 2026

Summary

Quant Engineer interview at Goldman Sachs, technical round focused on dynamic programming. One problem, but they pushed hard on the optimization follow-ups which is where things got interesting.

Questions Asked (1)

Given an m by n grid of non-negative integers, find the minimum-sum path from the top-left to the bottom-right cell, moving only right or down. Implement a solution in O(m*n) time using dynamic programming, then discuss how you'd optimize space using in-place modification or a rolling array.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

Got the base DP working fine, that part was almost muscle memory.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the problem constraints and edge cases, then explain the dynamic programming recurrence: dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]). Implement the O(m*n) solution, then discuss space optimization by either modifying the grid in-place or using a rolling array of size n, highlighting trade-offs.

Pro tip: At Goldman Sachs, interviewers value clean, efficient code and awareness of real-world constraints. Mention that in-place modification saves memory but mutates input, while a rolling array preserves input but uses O(n) extra space—choose based on whether the input can be modified.

1. Clarify and Define

Restate the problem, confirm movement directions (right/down only), and discuss edge cases like empty grid or single row/column.

2. DP Recurrence

Derive the recurrence: dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]), with base cases for first row and column.

3. Implement O(m*n) Solution

Code the DP using a 2D array, ensuring time and space complexity are O(m*n). Walk through a small example.

4. Space Optimization

Explain two approaches: in-place modification of the grid (O(1) extra space) or a rolling array of size n (O(n) extra space). Discuss trade-offs.

5. Analyze and Conclude

Summarize time and space complexity, mention potential follow-ups (e.g., obstacles, larger grids), and confirm solution correctness.

Key Points to Mention

Dynamic programming recurrence and base cases
Time complexity O(m*n) and space complexity O(m*n) for basic DP
In-place modification: overwrite grid cells, O(1) extra space but mutates input
Rolling array: use 1D array of size n, O(n) extra space, preserves input
Trade-offs: memory vs. input preservation, and potential for parallelization
Edge cases: empty grid, single row/column, large values (overflow considerations)

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