Goldman Sachs Software Developer Intern Interview Questions, Process, and Tips

Round duration - 90 minutes
Round difficulty - Medium

This round was scheduled in the evening hours at the Hackerrank platform which is a very famous platform known for conducting coding tests. All the participants were required to fill a form which was shared 2 days prior to the test date. This form was filled out probably for the security reasons and to ensure that no one disinterested participant gives the test.

Q1. 
Maximum Sum of Non-Adjacent Nodes in a Binary Tree
Given a binary tree with integer values assigned to each node, select nodes such that their sum is maximum, ensuring no two adjacent nodes are picked.
I...read more
Ans. 
Find the maximum sum of non-adjacent nodes in a binary tree.
• Use dynamic programming to keep track of the maximum sum at each node considering whether to include or exclude the current node.

• Recursively traverse the binary tree while keeping track of the maximum sum of non-adjacent nodes.

• Consider the cases where the current node is included in the sum or excluded from the sum to calculate the maximum possible sum.
Answered by AI
Add your answer
Q2. 
Validate Binary Search Tree (BST)
You are given a binary tree with 'N' integer nodes. Your task is to determine whether this binary tree is a Binary Search Tree (BST).
BST Definition:
A Binary Search Tr...read more
Ans. 
Validate if a given binary tree is a Binary Search Tree (BST) or not.
• Check if the left subtree of a node contains only nodes with data less than the node's data.

• Check if the right subtree of a node contains only nodes with data greater than the node's data.

• Recursively check if both the left and right subtrees are also binary search trees.

• Example: For a node with data 4, left subtree nodes should be less than 4 and righ
Answered by AI
Add your answer

Round duration - 45 minutes
Round difficulty - Medium

There were two interviewers for this round, one male and one female. Both of them were very helpful and energetic. They continuously thrown tricky questions/situations towards me and then were giving feedback as well on my answers and were talking about the pros and cons of each and every event. To be honest I felt very happy after talking to them. And yes it seemed to be quiet difficult during the initial minutes but then later on, everything was easy.

Q1. 
Ways To Make Coin Change
Given an infinite supply of coins of varying denominations, determine the total number of ways to make change for a specified value using these coins. If it's not possible to make...read more
Ans. 
The task is to find the total number of ways to make change for a specified value using given denominations.
• Use dynamic programming to solve this problem efficiently.

• Create a 2D array to store the number of ways to make change for each value up to the specified value.

• Iterate through each denomination and update the array accordingly.

• The final answer will be in the last cell of the array.

• Example: For N=3, D=[1, 2, 3], V...read more
Answered by AI
Add your answer

Round duration - 135 Minutes
Round difficulty - Medium

The platform was HackerRank with tab proctoring and webcam proctoring enabled. 
Timings were during day time around 10 am

Q1. 
Largest Rectangle in Histogram Problem Statement
You are given an array/list HEIGHTS of length N, where each element represents the height of a histogram bar. The width of each bar is considered to be 1.
...read more
Ans. 
Compute the area of the largest rectangle that can be formed within the bounds of a given histogram.
• Iterate through the histogram bars and maintain a stack to keep track of increasing heights.

• Calculate the area of the rectangle by considering the current height as the height of the rectangle and the width as the difference between the current index and the index at the top of the stack.

• Update the maximum area found so
Answered by AI
Add your answer
Q2. 
Find the Longest Palindromic Substring
Given a string ‘S’ composed of lowercase English letters, your task is to identify the longest palindromic substring within ‘S’.
If there are multiple longest palin...read more
Ans. 
Find the longest palindromic substring in a given string, returning the rightmost one if multiple substrings are of the same length.
• Use dynamic programming to check for palindromes within the string.

• Start by checking for palindromes of length 1 and 2, then expand to longer substrings.

• Keep track of the longest palindromic substring found so far and return the rightmost one if multiple substrings are of the same length.
Answered by AI
Add your answer

Round duration - 30 Minutes
Round difficulty - Medium

During day time
Platform: Zoom
The round starts with some introduction of mine, followed by my interests in life and what should I see in the company where I want to work

Q1. 
Smallest Window Problem Statement
Given two strings S and X containing random characters, the task is to find the smallest substring in S which contains all the characters present in X.
Input:
The first...read more
Ans. 
Find the smallest substring in a given string that contains all characters from another string.
• Use a sliding window approach to find the smallest window in S that contains all characters in X.

• Keep track of the characters in X using a hashmap.

• Move the right pointer to expand the window until all characters in X are found, then move the left pointer to shrink the window while maintaining the condition.

• Return the smallest...read more
Answered by AI
Add your answer

Round duration - 135 minutes
Round difficulty - Easy

-> The test had 5 sections and the duration is 2 hours 15 minutes. All sections are mandatory.
-> The Coding section had 2 programming questions and the duration was 30 mins.
-> The CS multiple-choice section had 7 MCQs and the duration was 25 mins.
-> The Problem Solving multiple-choice section had 8 MCQs and duration was 20 mins.
-> Each MCQ earns you 5 marks for the correct answers and -2 for incorrect answers.
-> The Advanced section had 1 programming question and the duration was 45 mins.
-> The Subjective section had 2 questions and the duration was 15 mins.

Q1. 
Rearrange Odd and Even Places
Given the head of a singly linked list, your task is to group all the nodes with odd indices together followed by the nodes with even indices, and then return the reordered l...read more
Ans. 
Rearrange nodes in a singly linked list by grouping odd and even indices together while maintaining relative order.
• Create two separate linked lists for odd and even nodes

• Traverse the original list and append nodes to respective odd/even lists

• Connect the last node of odd list to the head of even list

• Return the head of the rearranged list
Answered by AI
Add your answer
Q2. 
LCA in a Binary Search Tree
You are given a binary search tree (BST) containing N nodes. Additionally, you have references to two nodes, P and Q, within this BST.
Your task is to determine the Lowest Com...read more
Ans. 
Find the Lowest Common Ancestor (LCA) of two nodes in a Binary Search Tree (BST).
• Traverse the BST from the root node to find the LCA of nodes P and Q.

• Compare the values of nodes P and Q with the current node's value to determine the LCA.

• If both nodes are on the same side of the current node, move to that side; otherwise, the current node is the LCA.

• Handle cases where one node is the ancestor of the other or when one of
Answered by AI
Add your answer
Q3. 
Smallest Window Problem Statement
Given two strings S and X containing random characters, the task is to find the smallest substring in S which contains all the characters present in X.
Input:
The first...read more
Ans. 
Find the smallest substring in a given string that contains all characters from another given string.
• Use a sliding window approach to find the smallest window in S that contains all characters in X.

• Keep track of the characters in X using a hashmap.

• Slide the window to the right until all characters in X are found, then shrink the window from the left to find the smallest window.

• Return the smallest window found.

• Example: ...read more
Answered by AI
Add your answer

Round duration - 90 Minutes
Round difficulty - Easy

This was a technical interview. The interviewer was very helpful and he gave me hints for a solution. He asked me 2 coding questions. Some others questions were:
Explain deadlock
Explain what is Hashmap and linked list. Why we use them? And where do we use them?
Why we prefer linked list over array?
What are the time complexity of various operations in both data Hashmap and linked list?
What do I like about GS more and why do I want to be the part of GS.

Q1. 
Excel Column Number Conversion
Given a column title as it appears in an Excel sheet, your task is to return its corresponding column number.
Example:
Input:
S = "AB"
Output:
28
Explanation:
The seq...read more
Ans. 
Convert Excel column title to corresponding column number.
• Map each letter to its corresponding value (A=1, B=2, ..., Z=26)

• Iterate through the input string from right to left, calculate the value of each letter based on its position and add it to the result

• Multiply the result by 26 for each additional letter to the left
Answered by AI
Add your answer
Q2. 
Excel Sheet Column Number Problem Statement
You are provided with a string STR representing a column title in an Excel Sheet. Your task is to determine the corresponding column number.
Example:
A typica...read more
Ans. 
Given a string representing an Excel column title, determine the corresponding column number.
• Iterate through the characters of the string from right to left

• Calculate the corresponding value of each character based on its position and multiply by 26^position

• Sum up all the values to get the final column number
Answered by AI
Add your answer

Round duration - 60 Minutes
Round difficulty - Medium

One coding question medium level.
The second was a puzzle. I wasn’t familiar with this puzzle at that time. So interviewer saw all my thinking processes.
puzzle was: 
We have two water jugs, one measures 4 Gallons (4G) while the other measure 9 Gallons (9G). But there is no measuring label mentioned on either of these two jugs i.e. we cannot know the exact amount filled in the jug. Now, assuming there is an infinite amount of water supply, can we measure all 1G, 2G, 3G…….. upto 9G using these unmarked jugs.
Hint: We can empty the jugs, and transfer water from one jug to other.
Then the interviewer asked about my project like what is the concept of the project, technologies used, etc.

Q1. 
Merge Overlapping Intervals Problem Statement
Given a specified number of intervals, where each interval is represented by two integers denoting its boundaries, the task is to merge all overlapping interv...read more
Ans. 
Merge overlapping intervals and return sorted list of merged intervals.
• Identify overlapping intervals by comparing start and end times.

• Merge overlapping intervals to form new intervals.

• Sort the merged intervals in ascending order of start times.
Answered by AI
Add your answer

Round duration - 65 minutes
Round difficulty - Hard

It was around 6 pm and was held on Hackerrank. Having switched on WebCam during the entire duration was mandatory. We were required to solve 2 questions under 65 mins. Solving one problem completely, along with some of the test cases of another, was enough for getting shortlisted.

Q1. 
Rearrange Words in a Sentence
You are provided with a sentence 'TEXT'. Each word in the sentence is separated by a single space, and the sentence starts with a capital letter. Your task is to rearrange th...read more
Ans. 
Rearrange words in a sentence based on increasing order of their length.
• Split the sentence into words and calculate the length of each word.

• Sort the words based on their lengths, keeping the original order for words with the same length.

• Join the sorted words back into a sentence.
Answered by AI
Add your answer
Q2. 
Sudoku Solver Problem Statement
You are provided with a 9x9 2D integer matrix MAT representing a Sudoku puzzle. The empty cells in the Sudoku are denoted by zeros, while the other cells contain integers f...read more
Ans. 
Implement a function to solve a Sudoku puzzle by filling empty cells with valid numbers.
• Iterate through each empty cell and try filling it with a valid number (1-9) that satisfies Sudoku rules.

• Use backtracking to backtrack and try different numbers if a cell cannot be filled with a valid number.

• Check rows, columns, and 3x3 sub-grids to ensure each digit appears only once in each.

• Recursively solve the puzzle by filling
Answered by AI
Add your answer

Round duration - 40 minutes
Round difficulty - Medium

The interview started with my brief introduction, and the interviewer then proceeded to ask some questions. I was asked to write a code for these two questions:
1. Find the distances between two given nodes of a binary tree.
2. Find the next greater number with the same set of digits.
After I was able to solve both questions, he proceeded to ask some questions about my projects. He seemed interested in the ML project and asked some basic questions regarding the same. We had a brief discussion on how Machine learning can be used in the mechanical Engineering field. He asked me why I was aspiring to become a software engineer despite having a Mechanical engineering background. The round ended with me asking him about the types of projects interns are provided to work on at Goldman

Q1. 
Next Greater Number Problem Statement
Given a string S which represents a number, determine the smallest number strictly greater than the original number composed of the same digits. Each digit's frequenc...read more
Ans. 
The task is to find the smallest number greater than the given number with the same set of digits.
• Iterate from right to left to find the first digit that can be swapped with a smaller digit to make the number greater.

• Swap this digit with the smallest digit to its right that is greater than it.

• Sort all digits to the right of the swapped digit in ascending order to get the smallest number.
Answered by AI
Add your answer