Java Developer Goldman Sachs interview experience

Interview rounds

Round

Medium

Video Call

Duration45 minutes

Interview date22 Feb 2021

Coding problem2

Technical Interview round with questions on DSA.

1. Next Greater Element

Moderate

20m average time

90% success

0/80

Asked in companies

You are given an array arr of length N. You have to return a list of integers containing the NGE(next greater element) of each element of the given array. The NGE for an element X is the first greater element on the right side of X in the array. Elements for which no greater element exists, consider the NGE as -1.

For Example :

If the given array is [1, 3, 2], then you need to return [3, -1, -1]. Because for 1, 3 is the next greater element, for 3 it does not have any greater number to its right, and similarly for 2.

Problem approach

The brute force solution is to use two loops. The outer loop picks all the elements one by one. The inner loop looks for the first greater element for the element picked by the outer loop. If a greater element is found then that element is printed as next, otherwise, -1 is printed.
Time Complexity: O(N2)
Auxiliary Space: O(1)
The above approach can be optimised using stack data structure.
Steps :
Push the first element to stack.
Pick rest of the elements one by one and follow the following steps in loop.
1. Mark the current element as next.
2. If stack is not empty, compare top element of stack with next.
3. If next is greater than the top element, Pop element from stack. next is the next greater element for the popped element.
4. Keep popping from the stack while the popped element is smaller than next. next becomes the next greater element for all such popped elements.
• Finally, push the next in the stack.
• After the loop in step 2 is over, pop all the elements from the stack and print -1 as the next element for them.

Try solving now

2. Find Peak Element

Easy

15m average time

85% success

0/40

Asked in companies

You are given an array 'arr' of length 'n'. Find the index(0-based) of a peak element in the array. If there are multiple peak numbers, return the index of any peak number.

Peak element is defined as that element that is greater than both of its neighbors. If 'arr[i]' is the peak element, 'arr[i - 1]' < 'arr[i]' and 'arr[i + 1]' < 'arr[i]'.

Assume 'arr[-1]' and 'arr[n]' as negative infinity.

Note:

1.  There are no 2 adjacent elements having same value (as mentioned in the constraints).
2.  Do not print anything, just return the index of the peak element (0 - indexed).
3. 'True'/'False' will be printed depending on whether your answer is correct or not.

Example:

Input: 'arr' = [1, 8, 1, 5, 3]

Output: 3

Explanation: There are two possible answers. Both 8 and 5 are peak elements, so the correct answers are their positions, 1 and 3.

Problem approach

Naive Approach: The array can be traversed and the element whose neighbours are less than that element can be returned.
Time complexity: O(n).
Space Complexity: O(1).

Efficient Approach: Divide and Conquer can be used to find a peak in O(Logn) time. The idea is based on the technique of Binary Search to check if the middle element is the peak element or not. If the middle element is not the peak element, then check if the element on the right side is greater than the middle element then there is always a peak element on the right side. If the element on the left side is greater than the middle element then there is always a peak element on the left side. Form a recursion and the peak element can be found in log n time.

Algorithm:

Create two variables, l and r, initialize l = 0 and r = n-1
Iterate the steps below till l <= r, lowerbound is less than the upperbound
Check if the mid value or index mid = (l+r)/2, is the peak element or not, if yes then print the element and terminate.
Else if the element on the left side of the middle element is greater then check for peak element on the left side, i.e. update r = mid – 1
Else if the element on the right side of the middle element is greater then check for peak element on the right side, i.e. update l = mid + 1

Try solving now

Round

Medium

Video Call

Duration45 minutes

Interview date22 Feb 2021

Coding problem2

Technical round with questions on DSA.

1. Shortest Common Supersequence

Moderate

30m average time

70% success

0/80

Asked in companies

You are given a sequence ‘primary’ and a sequence of sequences ‘secondary.’ The sequence ‘primary’ is a permutation of numbers from 1 to N. You need to find if the sequence ‘primary’ is the only shortest common supersequence of sequences in ‘secondary’.

The shortest common supersequence of two sequences, ‘A’ and ‘B’, is the shortest sequence such that ‘A’ and ‘B’ are subsequences of it.

Note :

The range of elements in the ‘secondary’ sequence varies from 1 to N.

For Example :

If primary = [ 1, 2, 3 ] and secondary = [ [ 1, 2 ], [ 1, 3 ] ]
[ 1, 2, 3 ] is shortest common supersequence of [ 1, 2 ] and [ 1, 3 ]. But [ 1, 3, 2 ] is also a shortest common super sequence of [ 1, 2 ] and [ 1, 3 ]. As [ 1, 2, 3 ] is not the only shortest supersequence, you need to return false.

Problem approach

This problem is closely related to longest common subsequence problem.
Steps:
1) Find Longest Common Subsequence (lcs) of two given strings.
2) Insert non-lcs characters (in their original order in strings) to the lcs found above, and return the result.

How does this work?
We need to find a string that has both strings as subsequences and is shortest such string. If both strings have all characters different, then result is sum of lengths of two given strings. If there are common characters, then we don’t want them multiple times as the task is to minimize length. Therefore, we first find the longest common subsequence, take one occurrence of this subsequence and add extra characters.
Length of the shortest supersequence
= (Sum of lengths of given two strings) - (Length of LCS of two given strings)

Try solving now

2. Shortest Path in a Binary Matrix

Moderate

37m average time

65% success

0/80

Asked in companies

You have been given a binary matrix of size 'N' * 'M' where each element is either 0 or 1. You are also given a source and a destination cell, both of them lie within the matrix.

Your task is to find the length of the shortest path from the source cell to the destination cell only consisting of 1s. If there is no path from source to destination cell, return -1.

Note:

1. Coordinates of the cells are given in 0-based indexing.
2. You can move in 4 directions (Up, Down, Left, Right) from a cell.
3. The length of the path is the number of 1s lying in the path.
4. The source cell is always filled with 1.

For example -

1 0 1
1 1 1
1 1 1
For the given binary matrix and source cell(0,0) and destination cell(0,2). Few valid paths consisting of only 1s are

X 0 X     X 0 X 
X X X     X 1 X 
1 1 1     X X X 
The length of the shortest path is 5.

Problem approach

Algorithm :
1. Start from the source cell and call BFS procedure.
2. Maintain a queue to store the coordinates of the matrix and initialize it with the source cell.
3. Also, maintain a Boolean array visited of same size as the input matrix and initialize all its elements to false.
4. LOOP till queue is not empty :
Dequeue front cell from the queue
Return if the destination coordinates have reached.
For each of its four adjacent cells, if the value is 1 and they are not visited yet, we enqueue it in the queue and also mark them as visited.

Try solving now