Goldman Sachs Data Structures and Algorithms Interview Questions & Answers
Curated interview practice questions with answers. These are practice scenarios, not a verified list of past interview questions.
About Goldman Sachs hiring for Data Structures and Algorithms roles
Goldman Sachs is a global investment banking, securities and asset management firm. Its Bengaluru and Hyderabad offices are major engineering and operations centres supporting trading, risk, compliance and consumer platforms. It hires in India for software engineers, quality engineers, data engineers, quantitative strategists and risk or operations analysts.
For Data Structures and Algorithms roles, this Goldman Sachs practice set focuses most on Graphs and Graph Algorithms (6), Complexity Analysis and Recursion (6), Dynamic Programming (4), Heaps, Priority Queues and Greedy (3). It has 3 easy, 26 medium, 1 hard questions, so you can start easy and work up to the harder ones.
Company type
Banking & finance
Headquarters
New York, USA
Main India offices
Bengaluru, Hyderabad, Mumbai
Goldman Sachs Data Structures and Algorithms interview process
Online assessment (coding + quant + aptitude)
Technical round 1 (DSA)
Technical round 2 (design or CS fundamentals)
Hiring manager round
HR or culture round
Typical pattern based on public candidate experiences. Rounds vary by role, team and year.
Solved for Goldman SachsStart practicing
3 QUESTIONS FREESign up to unlock the full question bank and track your progress.Unlock every question and answer, then continue practising company-wise and package-wise.
import heapq
def merge_k_lists(lists):
heap = []
for i, node in enumerate(lists):
if node:
heapq.heappush(heap, (node.val, i, node)) # i breaks ties
dummy = tail = ListNode()
while heap:
val, i, node = heapq.heappop(heap)
tail.next = node
tail = node
if node.next:
heapq.heappush(heap, (node.next.val, i, node.next))
return dummy.next
# O(N log K) for N total nodes
A topological order lists the vertices of a DAG so every edge goes from earlier to later, such as an order to take courses. Kahn's algorithm computes in-degrees, pushes zero in-degree vertices into a queue and repeatedly removes them while decreasing neighbours' in-degrees; if not all vertices are output, a cycle exists. The DFS method adds a vertex to a list after visiting its descendants and reverses the list. Both are O(V plus E).
03
A build system hangs because some services depend on each other in a loop. How would you detect and report the cycle?
Model services as a directed graph and run DFS with three colours. When DFS reaches a node that is still on the current stack, it has found a back edge, and walking the parent pointers from the current node back to that node gives the exact cycle to report, such as A to B to C to A. Running this check in CI before every build prevents the problem, and Kahn's algorithm can list all nodes involved.
04
What is the time complexity of an outer loop from 0 to n with an inner loop where j starts at 1 and doubles until it reaches n?
The outer loop runs n times. In the inner loop j takes values 1, 2, 4, 8 and so on until it reaches n, which is about log base 2 of n iterations. Because the inner loop does not depend on the outer index, the total is n times log n, so the complexity is O(n log n). If instead the inner loop ran from 0 to i, the total would be n squared over 2, which is O(n squared).
05
How does Dijkstra's algorithm work and why does it fail with negative edge weights?
Dijkstra keeps a min-heap of tentative distances. It repeatedly pops the closest unvisited vertex, marks its distance final and relaxes its outgoing edges, giving O((V plus E) log V). It relies on the fact that once a vertex is popped, no shorter path can appear later. A negative edge breaks that assumption because a longer path could later become cheaper. For negative weights use Bellman-Ford.
06
A recursive DFS in Python crashes with RecursionError on a deep input. How do you fix it?
CPython limits recursion depth to about 1000 by default. Raising the limit with sys.setrecursionlimit works for moderate depth but can crash the interpreter on very deep inputs because the C stack is limited. The reliable fix is to rewrite the DFS iteratively with an explicit stack, pushing nodes and processing them in a loop. In Java the same issue appears as StackOverflowError and has the same solution.
07
Implement Dijkstra's algorithm with a priority queue.
A hash table computes a hash of the key and maps it to a bucket index, giving average O(1) insert, lookup and delete. A collision happens when two keys map to the same bucket. Separate chaining stores a list or tree in each bucket, which Java HashMap uses and converts to a tree after 8 entries. Open addressing probes other slots, which Python dict uses. Tables resize when the load factor grows too high.
10
What is dynamic programming, and what are overlapping subproblems and optimal substructure?
Dynamic programming solves a problem by combining solutions of smaller subproblems and storing them so each is computed only once. It applies when a problem has overlapping subproblems, meaning the same smaller problems repeat, as in Fibonacci, and optimal substructure, meaning the best answer can be built from best answers to subproblems, as in shortest paths. DP often turns exponential brute force into polynomial time.
11
How do you recognise a DP problem and define its state?
Signals include asking for a minimum, maximum, count of ways or whether something is possible, with choices at each step that affect later options. Start from brute-force recursion and ask what parameters fully describe a subproblem, such as index, remaining capacity or last chosen item; those become the state. Then write the transition between states, the base cases and the order of computation, and check the state count times transition cost fits limits.
12
Find the first and last position of a target in a sorted array.
from bisect import bisect_left, bisect_right
def search_range(nums, target):
lo = bisect_left(nums, target) # first index >= target
if lo == len(nums) or nums[lo] != target:
return [-1, -1]
hi = bisect_right(nums, target) - 1 # last index <= target
return [lo, hi]
# [5,7,7,8,8,10], 8 -> [3, 4]; two binary searches: O(log n)
13
Implement a data structure that returns the median of all numbers added so far.
def power(x, n):
if n < 0:
x, n = 1 / x, -n
result = 1
while n > 0:
if n & 1: # odd bit set: multiply current base in
result *= x
x *= x # square the base
n >>= 1 # move to next bit
return result
# power(2, 10) == 1024; use % mod after each multiply for modular power
15
An interviewer asks you to reduce your solution's extra space from O(n) to O(1). How do you approach it?
I check what the extra structure stores and whether the input itself can hold that information. Common techniques: use two pointers instead of a hash set on sorted data, keep only the last few DP values instead of a full table, modify the input in place, such as marking visited indices by negating values, or use bit manipulation like XOR to find a missing number. I state any trade-offs, such as mutating input.
16
Packages with given weights must be shipped in order within D days. How do you find the minimum ship capacity?
The capacity lies between the heaviest package and the total weight, and if a capacity works, any larger one also works, so binary search the answer. For a candidate capacity, greedily load packages day by day, starting a new day when the next package does not fit, and count days. If the days are within D, try smaller; otherwise try larger. Time is O(n log of total weight).
17
A trading application needs a stack that also returns the current minimum in O(1). How would you design it?
Keep a second stack of minimums. On push, push the value onto the main stack and push the smaller of the value and the current minimum onto the min stack. On pop, pop both. getMin returns the top of the min stack in O(1). To save space, push onto the min stack only when the new value is less than or equal to the current minimum, and pop it only when the popped value equals it.
18
Write a function to validate a binary search tree.
def is_valid_bst(root, low=float('-inf'), high=float('inf')):
if not root:
return True
if not (low < root.val < high):
return False
return (is_valid_bst(root.left, low, root.val) and
is_valid_bst(root.right, root.val, high))
# Passing bounds checks the whole-subtree property, not just children.
# O(n) time, O(h) space.
Sort meetings by start time and keep a min-heap of end times for rooms in use. For each meeting, if the earliest ending room is free by its start time, pop it; then push this meeting's end time. The heap size at the end, or its maximum, is the answer. This is O(n log n). An alternative sorts start and end times separately and sweeps with two pointers, counting overlaps.
21
What is the Union-Find data structure and what optimisations make it fast?
Union-Find, or disjoint set union, tracks which elements belong to the same group with find, returning a representative, and union, merging two groups. Path compression makes every node on a find path point directly to the root, and union by rank or size attaches the smaller tree under the larger. Together they give nearly constant amortised time, the inverse Ackermann function. It is used in Kruskal and dynamic connectivity.
22
What is amortised analysis? Explain it with dynamic array append.
Amortised analysis averages the cost of an operation over a long sequence, even if a few individual operations are expensive. A dynamic array such as Java ArrayList or Python list doubles its capacity when full, which costs O(n) for that append. But doubling happens rarely, and the total copying over n appends is under 2n, so each append costs O(1) amortised. Hash table resizing works the same way.
23
Detect whether a linked list has a cycle and return the node where the cycle begins.
def detect_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast: # cycle found
slow = head
while slow is not fast: # move both one step
slow = slow.next
fast = fast.next
return slow # start of the cycle
return None
# O(n) time, O(1) space
Edit distance, or Levenshtein distance, is the minimum number of insertions, deletions and substitutions to turn one string into another. dp[i][j] is the distance between the first i characters of A and the first j of B; if characters match, take dp[i-1][j-1], otherwise 1 plus the minimum of the three neighbouring cells. It runs in O(m times n) and is used in spell checkers, fuzzy search, DNA alignment and plagiarism detection.
25
What is tail recursion and do Java and Python optimise it?
A call is tail recursive when the recursive call is the very last action, so nothing remains to be done after it returns, as in a factorial that carries an accumulator. Some languages reuse the same stack frame for such calls, turning recursion into a loop. Neither Java nor CPython performs tail call optimisation, so deep tail recursion still overflows; convert it to a loop manually.
26
Design a simple scheduler that gives each job a fixed time slice in turn.
Round-robin scheduling fits a queue. Put all jobs in a FIFO queue. Repeatedly dequeue a job, run it for one time slice, and if it is not finished, enqueue it at the back with its remaining time. Each step is O(1). For priorities, keep one queue per priority level or use a priority queue. A circular buffer works well if the number of jobs is bounded, avoiding allocations.
27
An array of size 100000 must answer 100000 queries asking for the sum between two indices. What approach would you use?
Recomputing each sum is O(n) per query, about 10 to the power 10 operations in total, which is too slow. Since the array does not change, I would build a prefix sum array once in O(n) and answer each query in O(1) as pre[r+1] minus pre[l], giving O(n plus q) overall. If the array also receives updates, I would switch to a Fenwick tree or segment tree for O(log n) updates and queries.
28
You must build autocomplete for a search box over one million product names. Which data structure would you use?
I would use a trie where each node stores, besides children, the top few most popular completions under that prefix. Then typing a prefix walks L nodes and returns precomputed suggestions instantly, without exploring the whole subtree. Memory can be reduced with a compressed radix trie. For typo tolerance or ranking by many signals, a search engine with prefix indexes is more practical at large scale.
29
A sorted array has been rotated at an unknown point. How can you still search it in O(log n)?
At every step of binary search, at least one half around mid is sorted. Compare nums[low] with nums[mid]: if the left half is sorted and the target lies within its range, search left, otherwise search right. If the right half is sorted, apply the same check on the right. This keeps O(log n). With duplicates allowed, equal values can hide which half is sorted, and the worst case becomes O(n).
30
A metro app must find the route with the fewest stations between two stops. Which algorithm would you use?
If every hop counts equally, the network is an unweighted graph and BFS from the source gives the minimum number of stations in O(V plus E). I would store a parent for each visited station to reconstruct the path. If the goal changes to minimum travel time with different segment durations or interchange penalties, I would switch to Dijkstra with those weights, adding interchange cost as edges between line nodes.
Tips to crack the Goldman Sachs Data Structures and Algorithms interview
Practise probability and quantitative aptitude questions, which commonly appear in Goldman Sachs online assessments.
Learn basic financial concepts such as equities, bonds, derivatives and risk, especially for strats and data roles.
Prepare clear stories about teamwork and integrity, as Goldman Sachs emphasises its business principles and client focus.
Keep a one-minute story ready for every project on your CV: problem, your part, tools, result.
Practise the hard questions on this page aloud; Goldman Sachs interviewers usually ask follow-ups on your first answer.
Frequently asked questions
How many rounds are there in the Goldman Sachs Data Structures and Algorithms interview?
Candidates usually go through 5 stages: Online assessment (coding + quant + aptitude); Technical round 1 (DSA); Technical round 2 (design or CS fundamentals); Hiring manager round; HR or culture round. The exact rounds change with the role, team, location and your experience, so confirm the process with the recruiter.
Which topics should I prepare for the Goldman Sachs Data Structures and Algorithms interview?
This practice set leans on Graphs and Graph Algorithms (6), Complexity Analysis and Recursion (6), Dynamic Programming (4), Heaps, Priority Queues and Greedy (3). Revise those first, then practise explaining one or two of your own projects end to end, because most Goldman Sachs interviewers ask you to walk through real work.
Are these the exact questions asked at Goldman Sachs?
No. These are curated practice questions that match the skills and difficulty usually tested in banking & finance interviews like Goldman Sachs's. They are not a leaked or verified list of past questions.
Where does Goldman Sachs hire Data Structures and Algorithms professionals in India?
Goldman Sachs has large teams in Bengaluru, Hyderabad, Mumbai. Openings and locations change often, so check the Goldman Sachs careers page and filter by city and experience.
Data Structures and Algorithms questions for similar companies