The Goldman Sachs SDE VO is not the kind of interview where you one-shot a Hard and walk out. Its style is very consistent: optimize step by step from a brute-force solution to the optimal one, and explain the time/space complexity at every step. The interviewers are friendly and will drop hints, but you must show a clear chain of reasoning.
This article fully debriefs one candidate's four VO rounds - the real problem, the solution, the space-optimization point, and the narration structure for each round.
Four-Round Overview
| Round | Content | Focus |
|---|---|---|
| Round 1 | Distinct Subsequences + in-place sort | DP + space optimization + algorithm choice |
| Round 2 | Maximal Square + large-file external sort | 2D DP + massive-data handling |
| Round 3 | Maze BFS (30min) + Splitwise LLD (30min) | shortest path + object-oriented design |
| Round 4 | system design + design patterns (1h) | architecture + tradeoffs in tech choices |
Round 1: Distinct Subsequences + In-Place Sort
Problem 1: Distinct Subsequences (classic DP)
Given strings s and t, count the subsequences of s that equal t.
Write the 2D DP first, then optimize space when asked.
def numDistinct(s, t):
n, m = len(s), len(t)
# dp[j] = number of subsequences in the current prefix of s equal to t[:j]
dp = [0] * (m + 1)
dp[0] = 1
for i in range(1, n + 1):
# roll right to left so dp[j-1] is not polluted before this round uses it
for j in range(m, 0, -1):
if s[i-1] == t[j-1]:
dp[j] += dp[j-1]
return dp[m]
Space optimization key: when collapsing 2D to a 1D rolling array, the inner loop must run right to left, otherwise dp[j-1] gets updated early and contaminates the current round. This is the interviewer's favorite follow-up.
Problem 2: In-place sort (no extra space)
The interviewer asked quicksort or heapsort; the candidate chose quicksort. The key is to optimize step by step from brute force to optimal and clearly state time/space complexity: quicksort averages O(n log n), is in-place, worst case O(n^2) (mitigated with a random pivot).
Round 2: Maximal Square + Large-File External Sort
Problem 1: Maximal Square (2D DP)
Find the area of the largest all-1 square in a 0/1 matrix.
def maximalSquare(matrix):
if not matrix:
return 0
n, m = len(matrix), len(matrix[0])
# dp[i][j] = side length of the largest square with (i,j) as bottom-right corner
prev = [0] * (m + 1)
best = 0
for i in range(1, n + 1):
cur = [0] * (m + 1)
for j in range(1, m + 1):
if matrix[i-1][j-1] == '1':
cur[j] = min(prev[j], cur[j-1], prev[j-1]) + 1
best = max(best, cur[j])
prev = cur
return best * best
Transition core: dp[i][j] = min(top, left, top-left) + 1. When asked to optimize space, use a rolling array down to O(m).
Problem 2: Large-file external sort
2GB file, 250MB memory - how do you sort it?
Framework: external sort -
- Read in chunks; sort each chunk (around 200MB) in memory and write it back to disk.
- k-way merge: use a min-heap to manage the current element of each chunk, popping the smallest into the output each time.
import heapq
def k_way_merge(sorted_chunks):
# sorted_chunks: several already-sorted iterators
heap = []
iters = [iter(c) for c in sorted_chunks]
for idx, it in enumerate(iters):
v = next(it, None)
if v is not None:
heapq.heappush(heap, (v, idx))
out = []
while heap:
v, idx = heapq.heappop(heap)
out.append(v)
nv = next(iters[idx], None)
if nv is not None:
heapq.heappush(heap, (nv, idx))
return out
When asked about merge-phase details, stressing "use a min-heap to manage each chunk's current element" is the standard answer.
Round 3: Maze BFS + Splitwise LLD
First 30 minutes DSA: Maze 2 (BFS shortest path + optimization)
Standard grid BFS - mind the visited marking and the queue. Optimizations: bidirectional BFS, or A* if a heuristic is provided.
Last 30 minutes LLD: design Splitwise
LLD truly tests well-rounded skill. A structured approach:
- Clarify requirements: who owes whom how much, split methods (equal / exact / percent), groups, settlement.
- Core class design:
class User:
def __init__(self, uid, name):
self.uid, self.name = uid, name
class Expense:
def __init__(self, paid_by, amount, split_type, splits):
self.paid_by = paid_by # User
self.amount = amount
self.split_type = split_type # EQUAL / EXACT / PERCENT
self.splits = splits # {user: share}
class BalanceSheet:
def __init__(self):
# balances[a][b] = how much a owes b
self.balances = defaultdict(lambda: defaultdict(float))
def add_expense(self, expense):
share = self._compute_shares(expense)
for user, owed in share.items():
if user != expense.paid_by:
self.balances[user][expense.paid_by] += owed
- Extension discussion: debt simplification, concurrent settlement, edge cases (paying yourself).
Key: clarify requirements first -> define classes and interfaces -> discuss scalability and edge cases last. Time is tight; full code is not required, but the structure must be clear.
Round 4: System Design + Design Patterns (hardest)
One hour in two parts, a deep discussion of your current project's architecture plus the application of design patterns / OOP principles.
- The interviewer asks you to draw the current project's architecture and probes each tech choice's rationale.
- When you mention using a message queue to decouple services, you get asked how you handle message loss and duplicate consumption:
- Message loss: producer ack + persistence + retry.
- Duplicate consumption: idempotent consumer (dedup by unique ID / idempotency table).
- Design patterns: tie them to the project - Strategy (split methods), Factory (object creation), Observer (event notification) - in real use, not by reciting definitions.
Preparation Advice
- The step-by-step optimization narrative: brute force first, then optimize, reporting complexity at each step - this is the core GS scoring dimension.
- Space optimization is a frequent follow-up: for DP problems, have the rolling-array "right to left" detail ready.
- LLD must be structured: requirements -> class design -> interfaces -> scalability, a fixed four-part flow.
- System design ties to your project: message-queue reliability (loss/duplication) is almost always asked.
FAQ
Q1: How many rounds is the GS SDE VO? Usually a 4-round superday covering DSA, LLD, system design, and project deep dives.
Q2: How hard are the algorithm questions? Mostly LeetCode Medium, but heavily weighted on step-by-step optimization plus complexity analysis - AC alone is not enough.
Q3: Do you write full code for LLD? Not required. Focus on class design, relationships, and interfaces; when time is short, just make the structure clear.
Q4: Does system design use standard prompts (like design Twitter)? More commonly they deep-dive the projects on your resume, asking you to explain architecture and tech choices - harder to prepare than standard prompts.
Preparing for the Goldman Sachs SDE interview?
If you are stuck on "can AC but can't explain the optimization path," "no framework for LLD," or "panic when system design gets probed," let's talk through a full interview support plan: focused walkthroughs of all four rounds + timed mocks + full real-time support + per-round debrief.
Contact
Need real interview questions and a tailored prep plan? Message WeChat Coding0201 now, get the question bank.
Email: [email protected] Telegram: @OAVOProxy