**The overall assessment was mainly focused on Data Structures and Algorithms. **

**Round 1 (Hackerrank): **

There were two problem statements and I was expected to solve both. My preferred language was JAVA.

Below are the links of the question asked:

1. https://leetcode.com/discuss/interview-question/625140/goldman-sachs-oa-2020-array-burst-problem-birthday-party (Second question)

2. https://leetcode.com/discuss/interview-question/334671/goldman-sacks-july-2019-hackerrank-2

**Round 2 (Coderpad):**

A coderpad link was shared between the interviewer and me. There were two questions. The interviewer explained the question thoroughly after which I proceeded to solve it. After I was done the interviewer asked me to compile and run. All the test cases passed successfully. The interviewer added some custom test cases and ran the program again to further check the code. The same process was repeated for the second question also.

Below are the links of the question that I was asked.

1. https://www.geeksforgeeks.org/josephus-problem-set-1-a-on-solution/

2. https://www.geeksforgeeks.org/minimum-length-subarray-sum-greater-given-value/

**In person Interview**

There were two interviewers in all the technical rounds. All the interviewers were 7-8 experienced mostly serving at the VP level. Every round started with brief introduction followed by questions on my experience, past and current projects etc. Mainly the rounds comprised of coding questions based on data structures and algorithms. Few language oriented questions were there.

The last round was of the hiring manager. The hiring manager briefed about his team, the technology they work on, its general impact on the organisation’s business etc. Unlike other rounds, I wasn’t asked to code in this one. It mostly comprised of in depth discussions and counter questions.

**Round 1 (Technical round):**

1. Given a sequential input of integers in an array, find the missing number.

Test Case: I was given 76 77 79 80 81 as an array input and was expected to return 78.

Expected time complexity: O(logn)

After discussing different approaches, I solved the problem using binary search principle in O(logn).

Here is a variation of the problem asked https://www.geeksforgeeks.org/find-the-only-missing-number-in-a-sorted-array/?ref=rp. The difference being the integers need not be in the range 1 to n-1. It can start from any integer.

2. Candy crush problem: For a stream of integers, all consecutive same numbers appearing more than 3 times would get cancelled out. At the end return the remaining sequence of integers.

I was asked about the kind of data structure that I would use. Expected time complexity was O(n).

Solution: I discussed the approach using stack and keeping track of the top of the stack, I was able to solve it in O(n).

Here is the link to the problem: https://medium.com/algorithm-and-datastructure/candy-crush-remove-repeating-numbers-1020e3bddfb

3. Given an array of integers and a number k, find all the pairs whose difference is divisible by k.

Test case: [3, 7, 11] k=4

Ans: 3

Explanation: I transformed the array by replacing each element with its modulo by k(%k). Then calculated frequency of each element in the modified array. Finally adding all the frequencyC2 would result in the answer.

https://www.geeksforgeeks.org/count-pairs-in-an-array-whose-absolute-difference-is-divisible-by-k/

I was asked an additional question of probability.

4. A cube of size 3X3X3 meters is painted on all the sides. If the cube is cut into 1X1X1 size small cubes and selecting one small cube at random. What is the probability that the selected small cube doesn’t have any side painted?

Solution: There is only one small cube of size 1X1X1 in the middle of the bigger cube which won’t be painted. The total number of smaller cubes is 27. Hence the probability = 1/27.

**Round 2 (Technical round):**

The round started with brief introduction followed by discussion on my projects. I was asked project related questions such as: What’s the difference between authorization and authentication? What do you mean by integration testing? What is REST?

1. Given two integer arrays, find the max path sum across two arrays provided you can jump from one array to the other array at common elements.

Test case: Array 1=> [1 4 5 99 100 ] Array 2 => [ 3 5 8 99 101]

Ans: 218

Solution: [(1+4) > (3)] + 5 + [(8) > (0)] + 99 + [(101) > (100)] = 5 + 5 + 8 + 99 + 101 = 218

I solved this using the greedy approach in O(m+n) where m, n is the number of elements in the first and second array respectively.

https://www.geeksforgeeks.org/maximum-sum-path-across-two-arrays/

2. In a 2-d matrix find all possible paths from bottom left to bottom right with the constraint that you can travel only east, north east and south east.

Solution: I solved this using dynamic programming approach, calculating cost of path for (i,j) to (i+1,j+1), (i-1, j+1) and (i, j+1)

dp[i][j] = dp[i-1][j-1] + dp[i+1][j-1] + dp[i][j-1]; where all the cells [i-1][j-1], [i+1][j-1] and [i][j-1] are valid cells ( non negative and not exceeding matrix row-column limit).

The base case is dp[row-1][0] = 1;

The calculation should be done for each column starting from bottom to top and left to right as can be seen from the equation that it depends upon the previous column data.

I couldn’t find any exact link for the same problem available anywhere.

3. Given two integers n1 and n2 find the minimum number of operations required to form n2 from n1 using only two operations :multiplication by 2 and subtraction by 1.

Test Case: n1 = 5, n2 = 7

Ans: 3

Explanation:

5-1 = 4

4*2 = 8

8-1 = 7

Solution: I came up with a solution of forming a binary tree as n1 as root and filling the levels of by performing operations * by 2 and -1 on parent nodes. Then, finding the shortest path from n1 to n2. After pondering over the problem, I realised we do not even need to construct a tree, a mere use of a queue basically bfs would work.

https://www.geeksforgeeks.org/minimum-number-operation-required-convert-number-x-y/

**Round 3 (Technical Round):**

1. Given n trains with their arrival and departure time, find the minimum number of platforms required to accommodate all the trains.

Time complexity: O(nlogn)

https://www.geeksforgeeks.org/minimum-number-platforms-required-railwaybus-station-set-2-map-based-approach/

2. Given an array of integers, find maximum number using the array elements (https://www.geeksforgeeks.org/given-an-array-of-numbers-arrange-the-numbers-to-form-the-biggest-number/ )

Test Case: [7, 4, 90, 3]

Ans: 90743

Solution: I solved this by assuming the array elements as String and sorting them lexicographically. The interviewer wanted to know why wouldn’t the sorting of integer work here? I gave the interviewer a counter example and proceeded with the solution based on the custom comparator in Java. I was asked a lot of follow up questions related to Comparator, Anonymous class, Java 8, Lambda Expression as one thing lead to another.

3.Design a data structure that supports prefix-search. For example when we type any word in google.com, we get suggestions based on our typed word.

Solution: I underwent a lot of discussion and gradually in steps I was able to come up with a data structure that could serve the purpose. In functionality, the data structure was none other than Trie itself which I wasn’t aware of until then. The interviewer was fine with me coming up till there and I wasn’t asked to code it as I didn’t know Trie previously.

(https://www.geeksforgeeks.org/trie-insert-and-search/)

4. Longest Common Subsequence

I was asked this question since we still had time remaining. We just discussed the approach and pseudo code for this one.

(https://www.geeksforgeeks.org/longest-common-subsequence-dp-4/ )

After this there was a Hiring Manager round , where some design questions were asked.

I cleared all the rounds!