Autocoder

Goldman Sachs coding round questions with solutions

Last updated 2026-11-19

Goldman Sachs engineering assessments are commonly reported to combine coding problems with short maths, probability and CS questions. The problems below are practice in that style and difficulty: mostly medium arrays, strings and DP, with a few hard ones and a handful of MCQs. They are not recalled or past papers.

Each answer gives the approach, the complexity and the mistake that most often costs marks, with Python and Java code that is meant to run as written. Pair this with Goldman Sachs interview questions for the interview rounds.

StyleMedium DSA, plus probability, maths and CS MCQs
Languages herePython and Java
Problems8 coding, 3 MCQ-style
LevelEasy to hard

How to use this set

Attempt each problem for 20 to 25 minutes before reading the solution, since reported assessments give limited time per question. Write the brute force first, say its complexity, then improve it. If your first solution passes only some test cases, the cause is almost always an edge case: empty input, a single element, duplicates or negative numbers.

For the maths questions, practise setting up an equation for the expectation instead of enumerating cases. Reuse the topic guides on dynamic programming and probability when a pattern feels weak. Platform habits are covered in how to crack an online assessment and DSA coding rounds.

Goldman Sachs coding round questions with solutions: questions with worked answers

  1. 1

    Pairs with a given difference: count distinct pairs (a, b) in an array with a - b = k, for k >= 0.

    easy

    Put every value in a set (or a frequency map when k is 0). For each distinct value x, check whether x + k is present. For k = 0 a pair exists only if the value occurs at least twice. Time O(n), space O(n). Sorting plus two pointers gives O(n log n) with O(1) extra space. Common mistakes: counting the same pair twice by iterating over duplicates, and forgetting the k = 0 case.

    python
    from collections import Counter
    def count_pairs(a, k):
        c = Counter(a)
        if k == 0:
            return sum(1 for v in c.values() if v > 1)
        return sum(1 for x in c if x + k in c)
    java
    import java.util.*;
    class Solution {
        static int countPairs(int[] a, int k) {
            Map<Integer, Integer> c = new HashMap<>();
            for (int x : a) c.merge(x, 1, Integer::sum);
            int res = 0;
            for (int x : c.keySet()) {
                if (k == 0) { if (c.get(x) > 1) res++; }
                else if (c.containsKey(x + k)) res++;
            }
            return res;
        }
    }
  2. 2

    Longest substring without repeating characters.

    medium

    Sliding window with a map from character to its last index. Move the right edge one step at a time; if the character was last seen inside the current window, jump the left edge to one past that index. Track the maximum window length. Time O(n), space O(min(n, alphabet)). The classic bug is moving left backwards when the stored index is older than left, so always take the maximum of left and last+1. See also sliding window interview questions.

    python
    def longest_unique(s):
        last, left, best = {}, 0, 0
        for r, ch in enumerate(s):
            if ch in last and last[ch] >= left:
                left = last[ch] + 1
            last[ch] = r
            best = max(best, r - left + 1)
        return best
    java
    import java.util.*;
    class Solution {
        static int longestUnique(String s) {
            Map<Character, Integer> last = new HashMap<>();
            int left = 0, best = 0;
            for (int r = 0; r < s.length(); r++) {
                char ch = s.charAt(r);
                if (last.containsKey(ch) && last.get(ch) >= left) left = last.get(ch) + 1;
                last.put(ch, r);
                best = Math.max(best, r - left + 1);
            }
            return best;
        }
    }
  3. 3

    Merge overlapping intervals.

    medium

    Sort by start. Keep an output list; if the next interval starts at or before the end of the last output interval, extend that end to the maximum of the two ends, otherwise append it. Time O(n log n) for the sort, space O(n) for the output. Mistakes: not sorting, treating touching intervals such as [1,2] and [2,3] as separate when the problem says they merge, and replacing the end instead of taking the maximum (which breaks on [1,10] and [2,3]).

    python
    def merge(iv):
        iv.sort(key=lambda x: x[0])
        out = []
        for s, e in iv:
            if out and s <= out[-1][1]:
                out[-1][1] = max(out[-1][1], e)
            else:
                out.append([s, e])
        return out
    java
    import java.util.*;
    class Solution {
        static int[][] merge(int[][] iv) {
            Arrays.sort(iv, (a, b) -> Integer.compare(a[0], b[0]));
            List<int[]> out = new ArrayList<>();
            for (int[] cur : iv) {
                if (!out.isEmpty() && cur[0] <= out.get(out.size() - 1)[1])
                    out.get(out.size() - 1)[1] = Math.max(out.get(out.size() - 1)[1], cur[1]);
                else out.add(new int[]{cur[0], cur[1]});
            }
            return out.toArray(new int[0][]);
        }
    }
  4. 4

    Implement an LRU cache with O(1) get and put.

    hard

    Use an ordered hash map. In Python, OrderedDict with move_to_end on each access and popitem(last=False) on overflow. In Java, LinkedHashMap with accessOrder set to true and removeEldestEntry overridden. Both give O(1) per operation and O(capacity) space. Interviewers may ask you to build it with a doubly linked list and hash map, which is the same idea made explicit. A common mistake is forgetting that get must also refresh recency, and that put on an existing key must update the value as well as the order.

    python
    from collections import OrderedDict
    class LRU:
        def __init__(self, cap):
            self.cap, self.d = cap, OrderedDict()
        def get(self, k):
            if k not in self.d:
                return -1
            self.d.move_to_end(k)
            return self.d[k]
        def put(self, k, v):
            self.d[k] = v
            self.d.move_to_end(k)
            if len(self.d) > self.cap:
                self.d.popitem(last=False)
    java
    import java.util.*;
    class LRU extends LinkedHashMap<Integer, Integer> {
        private final int cap;
        LRU(int cap) { super(16, 0.75f, true); this.cap = cap; }
        int fetch(int k) { return super.getOrDefault(k, -1); }
        @Override protected boolean removeEldestEntry(Map.Entry<Integer, Integer> e) {
            return size() > cap;
        }
    }
  5. 5

    Find the k-th largest element in an unsorted array.

    medium

    Maintain a min-heap of size k: push each number and pop when the heap grows beyond k. The root is then the k-th largest. Time O(n log k), space O(k). Quickselect gives O(n) average but O(n^2) worst case. Sorting is O(n log n) and acceptable for small inputs, but state that you know the heap bound. A frequent off-by-one is confusing k-th largest with k-th smallest or using a max-heap of size n.

    python
    import heapq
    def kth_largest(a, k):
        h = []
        for x in a:
            heapq.heappush(h, x)
            if len(h) > k:
                heapq.heappop(h)
        return h[0]
    java
    import java.util.*;
    class Solution {
        static int kthLargest(int[] a, int k) {
            PriorityQueue<Integer> h = new PriorityQueue<>();
            for (int x : a) {
                h.offer(x);
                if (h.size() > k) h.poll();
            }
            return h.peek();
        }
    }
  6. 6

    Minimum cost climbing stairs: cost[i] is paid to step from stair i, and you may start at index 0 or 1 and take 1 or 2 steps. Find the minimum cost to reach the top.

    easy

    Let dp[i] be the minimum cost to stand on i. Then dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]), with dp[0] = dp[1] = 0, and the answer is dp[n]. Only the last two values are needed, so space is O(1) and time O(n). The usual mistake is returning dp[n-1], forgetting that the top is one position past the last stair. More patterns in dynamic programming interview questions.

    python
    def min_cost(cost):
        a = b = 0
        for i in range(2, len(cost) + 1):
            a, b = b, min(b + cost[i - 1], a + cost[i - 2])
        return b
    java
    class Solution {
        static int minCost(int[] cost) {
            int a = 0, b = 0;
            for (int i = 2; i <= cost.length; i++) {
                int c = Math.min(b + cost[i - 1], a + cost[i - 2]);
                a = b; b = c;
            }
            return b;
        }
    }
  7. 7

    Count the islands in a grid of '1' (land) and '0' (water), with four-directional connectivity.

    medium

    Scan every cell; on an unvisited land cell, increment the count and flood-fill its component with DFS or BFS, marking cells visited by overwriting them with '0'. Each cell is processed a constant number of times, so time is O(rows x cols); space is O(rows x cols) for the recursion in the worst case. Use an iterative stack if the grid can be large enough to overflow Python's recursion limit. Mistakes: allowing diagonal moves and failing to mark cells before pushing, which causes repeated work.

    python
    def num_islands(g):
        R, C, cnt = len(g), len(g[0]), 0
        for i in range(R):
            for j in range(C):
                if g[i][j] == '1':
                    cnt += 1
                    st = [(i, j)]
                    g[i][j] = '0'
                    while st:
                        x, y = st.pop()
                        for dx, dy in ((1,0),(-1,0),(0,1),(0,-1)):
                            a, b = x + dx, y + dy
                            if 0 <= a < R and 0 <= b < C and g[a][b] == '1':
                                g[a][b] = '0'
                                st.append((a, b))
        return cnt
    java
    import java.util.*;
    class Solution {
        static int numIslands(char[][] g) {
            int R = g.length, C = g[0].length, cnt = 0;
            int[][] d = {{1,0},{-1,0},{0,1},{0,-1}};
            for (int i = 0; i < R; i++)
                for (int j = 0; j < C; j++)
                    if (g[i][j] == '1') {
                        cnt++;
                        Deque<int[]> st = new ArrayDeque<>();
                        st.push(new int[]{i, j});
                        g[i][j] = '0';
                        while (!st.isEmpty()) {
                            int[] p = st.pop();
                            for (int[] k : d) {
                                int a = p[0] + k[0], b = p[1] + k[1];
                                if (a >= 0 && a < R && b >= 0 && b < C && g[a][b] == '1') {
                                    g[a][b] = '0';
                                    st.push(new int[]{a, b});
                                }
                            }
                        }
                    }
            return cnt;
        }
    }
  8. 8

    Trapping rain water: given bar heights, compute the water trapped.

    hard

    Two pointers from both ends with running maxima. The water above a bar is bounded by the lower of the tallest bar to its left and right, so advance the pointer on the shorter side: if height[l] < height[r], the left maximum decides the water at l. Time O(n), space O(1). The prefix and suffix maximum arrays solution is also O(n) time but O(n) space; mention it as the first idea. Mistake: using the global maximum for every bar.

    python
    def trap(h):
        l, r, lm, rm, water = 0, len(h) - 1, 0, 0, 0
        while l < r:
            if h[l] < h[r]:
                lm = max(lm, h[l]); water += lm - h[l]; l += 1
            else:
                rm = max(rm, h[r]); water += rm - h[r]; r -= 1
        return water
    java
    class Solution {
        static int trap(int[] h) {
            int l = 0, r = h.length - 1, lm = 0, rm = 0, water = 0;
            while (l < r) {
                if (h[l] < h[r]) { lm = Math.max(lm, h[l]); water += lm - h[l]; l++; }
                else { rm = Math.max(rm, h[r]); water += rm - h[r]; r--; }
            }
            return water;
        }
    }
  9. 9

    Probability MCQ: two cards are drawn without replacement from a 52-card deck. What is the probability that both are aces?

    easy

    The first card is an ace with probability 4/52 and, given that, the second is an ace with probability 3/51. Multiply: (4 x 3) / (52 x 51) = 12 / 2652 = 1/221. The error to avoid is using 4/52 twice, which assumes replacement and gives 1/169. Check: C(4,2) / C(52,2) = 6 / 1326 = 1/221.

  10. 10

    Expectation MCQ: a fair coin is tossed until two heads appear in a row. What is the expected number of tosses?

    hard

    Let E be the expectation from the start and F the expectation after one head. From the start: E = 1 + (1/2)F + (1/2)E. After a head: F = 1 + (1/2)(0) + (1/2)E, since a second head ends it and a tail restarts. Substituting F = 1 + E/2 into the first equation gives E = 1 + 1/2 + E/4 + E/2, so E/4 = 3/2 and E = 6. Options such as 4 are what you get by forgetting the restart.

  11. 11

    CS MCQ: what is the time complexity of: for i in 1..n: j = 1; while j < n: j = j * 2?

    easy

    The inner loop doubles j each time, so it runs about log2(n) iterations. The outer loop runs n times, so the total is O(n log n). If the outer loop also doubled i, it would be O(log^2 n). When the options include O(n) or O(n^2), check which variable is multiplied and which is added.

Frequently asked questions

What difficulty are Goldman Sachs coding questions?

They are commonly reported as medium, with occasional hard problems, on arrays, strings, hashing, DP and graphs. This set is written to that level as practice.

Are there MCQs in the Goldman Sachs online test?

Some cycles are reported to include maths, probability and CS multiple-choice questions alongside coding. Formats change, so confirm your invitation email.

Should I write Python or Java?

Either. Choose the language where you know the standard library best, since heaps, ordered maps and sorting with comparators save a lot of time.

Is this a previous question paper?

No. These are original practice problems in the style of the topics the round commonly covers.

Related guides

More in Company Interview Questions

See all in this section