10 of the most difficult Leetcode problems you could see in a Goldman Sachs interview

It'd be a fools errand to try and predict exactly what Leetcode question will show up in a Goldman Sachs tech job interview. The bank has asked at least 260 unique questions according to the Leetcode site. If you want to work in technology or as a quant at Goldman, you therefore need to be ready for anything, including some of the more niche or difficult questions the bank is known to ask. 

💥Follow us on WhatsApp for news alerts.💥

Below are the 10 Goldman Sachs interview questions with the lowest acceptance rates. Acceptance is a synonym for successful answers on the Leetcode site - it does not mean acceptance by Goldman Sachs.

10. 132 Pattern

Question Number: 456

Submissions: 955.5k

Acceptance Rate: 34.9%

Responses to this question liken it to an even more difficult version of 'Trapping Rain Water' a famously hard question Goldman Sachs has been known to ask. You're tasked with looking through a series of numbers to find a '132 pattern' - where one high value integer has a lower valued integer on either side, and that the number on the right side is larger than the number on the left. This can be trickier than it looks because the numbers won't always appear directly next to each other; for example, the sequence (3, 5, 0, 3, 4) does contain a 132 pattern (3, 5, 4).

Responses say that you need to utilize a monotonic stack, a data structure used to keep a list of numbers sorted by value, to effectively solve this question. Using that, you can effectively rank the values of each integer before searching for the sequence within the array. 

You can see the top ranked solution here.

9. Reaching Points

Question Number: 780

Submissions: 240.1k

Acceptance Rate: 34.5%

This question focuses on moving from one point on a graph (sx, sy) to another (tx, ty) using just two potential operations: you must either add the value of your x co-ordinate to the value of your y co-ordinate or vice versa. Operations can be repeated as often as you want, and you must state whether it's possible to reach the second set of co-ordinates from the first using this method. 

The reason the acceptance rate is so low may be that people try to solve the problem moving forwards when, as discussion for the question state, you'd be better served working the opposite way around. With the end co-ordinate, you know that the smaller number has been added to the larger one as part of the operation; you can take it away and repeat this process to reduce it down until you can see whether the original co-ordinates were used in the process. 

There are also complaints about the memory constraints mandated in this question. In some cases, where one co-ordinate is much larger than the other, you could wast memory analyzing each individual operation when it is otherwise clear that the same operation has been repeated multiple times. To save memory in this instance, you could use the modulo operator (a math function that returns the remainder after a number has been divided by a specified numer) to figure out how many times a single operation has been consecutively completed.

A high-ranked sequence involving modulo can be seen here. 

8. Number of Perfect Pairs

Question Number: 3649

Submissions: 67.2k

Acceptance Rate: 34.4%

This question involves testing a series of numbers in an array to see if any two integers satisfy certain algebraic conditions. While there are three primary conditions you have to assess, the first of these can be bypassed to make your code more efficient. 

Condition one states that the second integer must be larger than the first. You can speed this up by sorting all the numbers by size before testing any sets of pairs.

Condition three essentially means that the two numbers must either both be positive or both be negative, therefore you can test for this first and disregard any pairs that don't meet this condition. The last condition means essentially that the larger number must less than twice the size of the smaller one; if it is then you can declare it a 'perfect pair' and continue testing the other numbers.

This question also appears to be liked by hedge funds; one commenter said they encountered it at Squarepoint Capital. You can see the highest ranked solution here.

7. Shortest Subarray with Sum at Least K

Question Number: 862

Submissions: 659.5k

Acceptance Rate: 32.9%

This question focuses on testing a continuous sequence of numbers within an array to see if they are equal to or greater than value K, then state the smallest number of numbers required to reach that value. The low acceptance rate on this question may come through hubris rather than difficulty; many responses stated that they hadn't considered the effect of negative numbers on their solution.

A rushed solution might use a 'sliding window' approach by continuously adding numbers along a sequence until the value of it is greater than K, then subtract the numbers from the start of the sequence until it falls below K to find the minimum amount of numbers required. This works for fully positive arrays but, if a negative number is involved, subtracting it from the total would increase the running total, essentialling increasing the value of K and potentially delegitimizing your solution.

You can find the highest ranked solution for this question here.

6. Find The Closest Palindrome

Question Number: 564

Submissions: 437.6k

Acceptance Rate: 32%

Martin Shoosterman, a senior engineer at Nasdaq, said he had solved 700 Leetcode problems before this one but described it as "by far the worst problem I have ever solved." You are given a number and asked to find the closest palindrome (a number that reads the same forwards and backwards) to that number.

In most cases the solution is simple enough. Since palindromes are determined by their first half, you can just take the first half of the number provided and fill out the remaining digits to complete your palindrome.

There are several edge cases that might trip you up, though. For example, you aren't allowed to return the number provided in the event that it is itself a palindrome. Because of this, you must take the first half of the number, add/minus one, then find the closest palindrome for each number, then find whichever is closest to the original. One of the trickiest edge cases is when a solution has a different number of digits to the original number (e.g. the closest palindrome to 99 is 101).

You can find the highest ranked solution here.

5. Longest Duplicate Substring

Question Number: 1044

Submissions: 278.6k

Acceptance Rate: 31.3%

This is a simple question hampered by its constraints. You are given a string of letters and tasked with finding the longest sequence of values that appears twice. In cases like 'banana', this is easy (ana). Other questions ask for essentially the exact same thing; however, the string can contain tens of thousands of individual letters, meaning a brute force approach would take far too long.

Solutions tend to use the Rabin-Karp algorithm, which turns chunks of letters into numeric fingerprints so duplicates can be spotted without comparing text letter by letter. To avoid testing every possible length, solutions often check a length in the middle, and use the result to rule out half the remaining possibilities. Repeating this quickly reveals the longest length that still has a duplicate.

You can find the highest ranked solution here.

4. Fraction to Recurring Decimal

Question Number: 166

Submissions: 1.2m

Acceptance Rate: 31.1%

Takes on this question range from "bonkers" to "11/10 rage bait." It's a relatively simple problem about turning a fraction into a decimal while isolating instances of recurring numbers. The issue is that the the constraints quietly permit extreme edge cases, tripping up what is an otherwise simple algorithm.

One of the edge cases that it tests is -2147483648, the most negative value that can be stored in a 32 bit integer, which the algorithm does not know how to properly respond to. Using a 64-bit integer instead solves the problem without much fuss, but it's such an extreme and particular edge case that the ragebait assertion seems apt.

You can see the highest ranked solution here.

3. Count Collisions of Monkeys on a Polygon

Question Number: 2550

Submissions: 92k

Acceptance Rate: 30.3%

This is a problem that can be solved in as little as four lines of code. That hasn't stopped it from having one of the worst acceptance rates among any question asked by Goldman Sachs... so what's the issue?

Some comments suggest that the problem is poorly designed; the premise is that each corner of a polygon of n sides has a monkey standing on it each of whom must move either to the left or right. You need to calculate how many different combinations of moves result in the monkeys colliding.

Most people work backwards and suggest that you first find all the ways that the monkeys can't collide, then subtract that from the total number of movement options. Comments suggest that the problem only sees two possible options for this (when the monkeys all move to the left or all move to the right). The wording for what constitutes a collision is criticised; commenters argue that for even-sided shapes, monkeys swapping in pairs never share a corner and so shouldn't count, but they are actually counted as monkeys crossing paths on an edge counts as a collision. The question is a testament to the importance of reading the rules very carefully.

You can find the highest ranked solution here.

2. Minimum Moves to Capture The Queen

Question Number: 3001

Submissions: 103.8k

Acceptance Rate: 22.6%

This question debuted as a live contest problem, which will have contributed to its particularly low acceptance rate, and suggests that a lot of people will trip up in a time-sensitive environment like an interview. A black queen, white rook and white bishop are placed at random squares on a chess board and you must calculate the minimum number of moves to reach the queen (which does not move) using the white pieces.

Some answers are obvious. If the queen lands directly in the movement line of either piece the answer is one. In most other cases, the rook can reach the queen in two moves by travelling up or down to its y co-ordinate, then across to its x. The main edge cases is when the rook, queen and bishop are all in a line, but the bishop is blocking the rook's path to the queen (or the inverse). You can't shortcut the solution here: simply checking whether the 3 pieces are all on the same line will backfire as there may be cases where the bishop is behind the queen and thus not obstructing the rook.

You can see the highest ranked solution here.

1. String to Integer (atoi)

Question Number: 8

Submissions: 11.9m

Acceptance Rate: 21.3%

This question is one of the most widely used in job interviews, particularly for Google and Amazon, so it's no surprise Goldman appreciates it too. The purpose is to take a string that may begin with a written number and convert that leading number into an integer. It's not hiding any twist, but it does have various interacting rules, all of which you need to implement exactly as described.

You can find the highest ranked solution here.

Have a confidential story, tip, or comment you’d like to share? Contact: WhatsApp: http://wa.me/442079977910 (+44 20 7997 7910), Telegram: @AlexMcMurray, Signal: @AlexMcMurrayEFC.88 Click here to fill in our anonymous form, or email editortips@efinancialcareers.com.

Bear with us if you leave a comment at the bottom of this article: comments are moderated intermittently by human beings. Sometimes these humans might be asleep, or away from their desks, so it may take a while for your comment to appear. You must take sole responsibility for comments you post on this site. We will take reasonable steps to weed out anything that we consider to be offensive or inappropriate.