Associate Analyst Goldman Sachs interview experience

Interview rounds

Round

Medium

Online Coding Interview

Duration60 minutes

Interview date7 Apr 2022

Coding problem2

This round was the online coderpad round. This round was based on easy and medium level DS and Algo based problems.
I was able to solve the problems in optimised way.

1. Most Frequent Word

Easy

0/40

Asked in companies

You are given a paragraph that may have letters both in lowercase and uppercase, spaces, and punctuation. You have also given a list of banned words. Now your task is to find the most frequent word which is not in the list of banned words. There will always be a solution, and the solution will be unique.

While comparing words, you can ignore whether the letter is lowercase or uppercase. For example, ‘AsK’ and ‘aSK’ are the same. The words will always contain only alphabets or we can say words will be separated by spaces or punctuation. The answer will be in uppercase letters.

The words in the banned list will always be in upper letters and free from punctuation and spaces.

For example :

Paragraph = ‘It's a square SqUare. It's a FLAT flat.’ 
Banned =[FLAT, IT, S]. 
So we can see these words [IT, S, SQUARE, FLAT ]  are most frequent.
Now we will look at to banned list and we can see 3 of the words are banned.
So we have a unique answer SQUARE which has a frequency of 2 and not on the banned list.

Problem approach

I gave the Hashmap bases solution.

static char getMaxOccurringChar(String str)
{
// Create array to keep the count of individual
// characters and initialize the array as 0
int count[] = new int[ASCII_SIZE];

// Construct character count array from the input
// string.
int len = str.length();
for (int i=0; i count[str.charAt(i)]++;

int max = -1; // Initialize max count
char result = ' '; // Initialize result

// Traversing through the string and maintaining
// the count of each character
for (int i = 0; i < len; i++) {
if (max < count[str.charAt(i)]) {
max = count[str.charAt(i)];
result = str.charAt(i);
}
}
return result;
}

Try solving now

2. Gas Station

Moderate

10m average time

90% success

0/80

Asked in companies

You have been given a circular path. There are 'N' petrol pumps on this path that are numbered from 0 to N - 1 (Both inclusive). Each petrol pump has two values associated with it:

1)The amount of petrol that is available at this particular petrol pump.
2)The distance to reach the next petrol pump.

You are on a truck having an empty tank of infinite capacity. You can start the tour from any of the petrol pumps. Your task is to calculate the first petrol pump from where the truck will be able to complete the full circle or determine if it is impossible to do so.

You may assume that the truck will stop at every petrol pump and it will add the petrol from that pump to its tank. The truck will move one kilometre for each litre of petrol consumed.

Problem approach

public int canCompleteCircuit(int[] gas, int[] cost) {
int sumGas = 0;
int sumCost = 0;
int index = 0;
int rem = 0;
for(int i=0; i sumGas+= gas[i];
sumCost += cost[i];
rem+= gas[i];
rem -= cost[i];
if(rem < 0){
rem = 0;
index = i+1;
}
}
if(sumGas < sumCost ) return -1;
return index;
}

Try solving now

Round

Medium

Video Call

Duration60 minutes

Interview date21 Apr 2022

Coding problem2

HR called for the interview availability. This round was set up during day time. This round was elimination round and based on DS and Algorithm problem.Overall the interview experience was really great. I was able to provide optimised solution for both DS Algo problem.

1. Longest Increasing Subsequence

Moderate

0/80

Asked in companies

'N' students are standing in a row. You are given the height of every student standing in the row. Your task is to find the longest strictly increasing subsequence of heights from the row such that the relative order of the students does not change.

A subsequence is a sequence that can be derived from another sequence by deleting zero or more elements without changing the order of the remaining elements.

Problem approach

Step1: I solved the problem using the recursion
Step2: Interviewer asked me to optimise
Step: Then I solution using dynamic programming approach since I have already solved this problem on leetcode:
public int lengthOfLIS(int[] nums) {
int n = nums.length;
int[]LIS = new int[n];
int ans = Integer.MIN_VALUE;
for(int i = n-1; i>=0; i--){
int tempAns = 1;
for(int j = i+1; j nums[i]){
tempAns = Math.max(tempAns, 1+LIS[j]);
}
}
LIS[i] = tempAns;
ans = Math.max(ans, tempAns);
}
return ans;
}

Try solving now

2. Trapping Rain Water

Moderate

15m average time

80% success

0/80

Asked in companies

You have been given a long type array/list 'arr’ of size 'n’.

It represents an elevation map wherein 'arr[i]’ denotes the elevation of the 'ith' bar.

Print the total amount of rainwater that can be trapped in these elevations.

Note :

The width of each bar is the same and is equal to 1.

Example:

Input: ‘n’ = 6, ‘arr’ = [3, 0, 0, 2, 0, 4].

Output: 10

Explanation: Refer to the image for better comprehension:

Note :

You don't need to print anything. It has already been taken care of. Just implement the given function.

Problem approach

Step1: First I solved the problem with brute force approach by checking for each element max element in it's left and right and then calculating the water contained at that particular position.
Step2: Interviewer asked me to optimise the solution, So gave the solution by storing the left and right max in extra array and calculating the water contained live below:
public int trap(int[] height) {
int n = height.length;
int left[] = new int[n];
left[0] = 0;
for(int i=1; i=0; i--){
right[i] = Math.max(right[i+1], height[i+1]);
}
int ans = 0;
for(int i=0; i 0) ans+= temp;
}
return ans;
}

Try solving now

Round

Medium

Video Call

Duration60 minutes

Interview date5 May 2022

Coding problem1

1. Subarrays With At Most 'K' Distinct Values

Moderate

15m average time

85% success

0/80

Asked in companies

You are given an array ‘ARR’ having ‘N’ integers. You are also given an integer ‘K’. The task is to count the number of subarrays that have ‘K’ distinct values.

Subarray: A consecutive sequence of one or more values taken from an array.

For Example :

‘N’ = 4, ‘K’ = 2
‘ARR’ = [1, 1, 2, 3]

There are ‘3’ subarrays with ‘2’ distinct elements, which are as follows: [1, 2], [2, 3], [1, 1, 2].
Thus, you should return ‘3’ as the answer.

Problem approach

Step1: I gave the brute force approach for this problem. Including the solution below:
public int subarraysWithKDistinct(int[] nums, int k) {
Map map = new HashMap();
int ans = 0;
int i=0; int j=0;
while(j < nums.length){
// add the element in the map
map.put(nums[j], map.getOrDefault(nums[j], 0) + 1);
//window size greater than k then remove or update the freq of element in the map
while(map.size() > k){
map.put(nums[i], map.get(nums[i])-1);
if(map.get(nums[i]) == 0) map.remove(nums[i]);
i++;
}
if(map.size() == k ){
Map tempMap = new HashMap(map);
int start = i;
while(tempMap.size() == k ){
ans++;
tempMap.put(nums[start], tempMap.get(nums[start])-1);
if(tempMap.get(nums[start]) == 0) tempMap.remove(nums[start]);
start++;
}
}
j++;
}
return ans;
}

Step2: Interviewer asked me to optimise the solution and I couldn't provide the optimised solution.

Try solving now

Associate Analyst

Interview preparation journey

Are you ready for your Dream Job?

Interview rounds

1. Most Frequent Word

While comparing words, you can ignore whether the letter is lowercase or uppercase. For example, ‘AsK’ and ‘aSK’ are the same. The words will always contain only alphabets or we can say words will be separated by spaces or punctuation. The answer will be in uppercase letters.

The words in the banned list will always be in upper letters and free from punctuation and spaces.

For example :

2. Gas Station

You have been given a circular path. There are 'N' petrol pumps on this path that are numbered from 0 to N - 1 (Both inclusive). Each petrol pump has two values associated with it:

You are on a truck having an empty tank of infinite capacity. You can start the tour from any of the petrol pumps. Your task is to calculate the first petrol pump from where the truck will be able to complete the full circle or determine if it is impossible to do so.

You may assume that the truck will stop at every petrol pump and it will add the petrol from that pump to its tank. The truck will move one kilometre for each litre of petrol consumed.

1. Longest Increasing Subsequence

'N' students are standing in a row. You are given the height of every student standing in the row. Your task is to find the longest strictly increasing subsequence of heights from the row such that the relative order of the students does not change.

2. Trapping Rain Water

You have been given a long type array/list 'arr’ of size 'n’.

It represents an elevation map wherein 'arr[i]’ denotes the elevation of the 'ith' bar.

Print the total amount of rainwater that can be trapped in these elevations.

Note :

Example:

Note :

1. Subarrays With At Most 'K' Distinct Values

You are given an array ‘ARR’ having ‘N’ integers. You are also given an integer ‘K’. The task is to count the number of subarrays that have ‘K’ distinct values.

Subarray: A consecutive sequence of one or more values taken from an array.

For Example :