Hi Everyone,
I'm here to share my interview experience with Goldman Sachs for Associate SDE role.

Application
I applied through linkedIn without any referral and luckily got a call from recruiter the next day itself.
We had a discussion about my current role and day-to-day responsibilities that I handle currently in my role.
Then, she sent me a link for hackerrank online assessment and I took it two days later.

Suggestion : Always try to apply through referral.

Hackerrank Online Assessment
This test consisted of two DSA questions and I was given 90 mins to solve.
Both were leetcode medium. (I don't remember the exact questions. Feel free to skip this portion if you want.)

1. A question related to array and sum.
2. Question related string and hashing with timestamps.
   I solved both of them in 40 mins.

Got a call from recruiter 3 days later about moving through the further process and I had my first interview set up two days after that.

Round 1 : DSA :
This round went for 1 hour.
Expectation was to solve two questions and write the optimized code for both of them.
I did the same for first two and since 20mins were remaining, he asked me a third question and I coded it up as well.

1. https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/description/
2. https://leetcode.com/problems/palindromic-substrings/description/
3. https://leetcode.com/problems/meeting-rooms-ii/

Got a call from recruiter one day later. She told me that I'll be having four rounds on the same day.
I guess this is generally called super day (Have seen this is in other leetcode posts).
The upcoming rounds are elimination based.

Super day : Round 1 : DSA
This round went for 1 hour and I was asked 2 questions.

1. https://leetcode.com/problems/copy-list-with-random-pointer/ : I gave an O(n) time and space solution. Interviewer asked me to optimize the space to O(1) and I was able to give a breakthrough and code the O(1) space because of Striver's tutorial for this question.
2. The next question was similar to https://leetcode.com/problems/132-pattern/. : I was able to explain the solution and he was okay with it. He gave a follow up asking to count the # of such pairs, to which I gave an O(n * n) solution.
   This question was more of a discussion and I wasn;t asked to code it up.

Super day : Round 2 : DSA
1 hour round yet again.

1. I was asked https://leetcode.com/problems/fraction-to-recurring-decimal/. Interviewer added another constraint saying that division operator should not be used. (Use binary search to find the quotient of a/b) -> (Interviewer hinted me on this).
2. You are given a long string and a prefix. Output the indices at which the prefix occurs in a specific word..

	indices	  0 2   6  9   13  17
e.g. : doc = "A BCD AB CDE DEF AGH"                   prefix = "A"
output : {0, 6, 17}

Solution :
Traversing the string and finding the prefix would've done the work.
O(m * n) time and O(1) space. m = size of doc and n = len of prefix

But I was hasty and jumped to trie.
He hinted me that no trie is needed and I gave him the above solution.
I wasn't asked to code it.
He followed up with why I was thinking of Trie and what is the advantage and disadvantages of using it.
I told him the following after thinking for sometime:
1. 	Disadvantage : Too much memory
2.	Advantage : Imagine I'm given a query of prefixes instead of one prefix. The doc is immutable as well.
	Then, using trie would be advantageous :

I was asked to code trie solution. PFB the approach :
1.	Put the word, index pair in a vector.
	for above eg., : {{A, 0}, {BCD, 2}, {AB, 6}, {CDE, 9}, {DEF, 13}, {AGH, 17}} (I did not code this part)
2.	create a trie struct with List of Indices as an additional element.
	A : {0, 6, 17}
	A -> B : {6}
	A -> G : {17}
	A -> G -> H : {17}
	like this.
3.	For a prefix, just go through the nodes of the trie and get the list.
	prefix = "AG"
	start from root :
	root -> A -> G
	And get the list if the node exists.
Assuming q queries Time = O(m + q * n) and Space = O(m)	
The first solution would've given Time = O(q * m * n) and space = O(1)

Super day : Round 3 : Design
This was more of a discussion round.

1. https://leetcode.com/discuss/interview-question/algorithms/125015/first-non-repeating-character-in-a-string : follow up was on how you would implement in single machine, multiple threads and multiple machines, multiple threads.

Single machine, Single thread :
Let's say len of the input is 'n'.
Have a frequency map<char, pair<int, int>> where pair.first is count and pair.second is last occuring index.

eg. abacdde
Iterate every character of the string and create the above map.
=> map = { {a, {2, 2}}, {b, {1, 1}},  {c, {1, 3}}, {d, {2, 5}}, {e, {1, 6}} }.
Then, iterate this map and cosider those characters with freq == 1 and take the minimum index.
This will give you the first non repeating character.

Time : O(n + 26)

Single machine, multiple threads:
Let's say there are 4 threads.
Split the string into 3 parts and feed it into 3 threads in parallel.
4th thread will act like a load balancer getting heartbeat signals and catch exceptions from the other 3 threads.
Each thread will have its own map, like map1, map2 and map3.
We can concatenate them and form a master map 'map' and do. the same thing above to find the first such character.

Multiple machine, multiple threads:
4 machines, 4 threads.
Split the string into 3 parts and feed it onto 3 machines.
4th machine acts like a load balancer.
Now, the problem boils down Single machine, multiple threads with len = n / 3.
And each machine will return it's own master map.
And we can concatenate all these master maps in the 4th machine to get the final map.

In case of exception or failure, the 4th machine or thread will attempt to retry the process again.

Note : This was purely a discussion and I wasn't asked to code it. The interviewer seemed satisfied with the above explanation that I gave.

2. Design LRU cache and a follow up on the same. : I don't remember the follow up, but I kind of messed it up.

Super day : Round 4 : HM
I was asked to explain one of my projects.
Some instances on my leadership abilities.
This round went for only 15 mins.

The recruiter reached out to me two weeks later and I had to attend one final round.

Final Round : Design + HM
I was asked to explain one of my projects.
And I was asked a design question based on that.
This round went for 30 mins.

I had a compension call with the recruiter and I was given the offer (This took approximately 7 weeks after the final round).

Some additional info :
Every round happened on coder pad.
Two interviewers were there in each round except Round 1 : DSA and Super day : Round 4 : HM

Tips to crack:
Practice neetcode 150, take notes and revise. (This is the foundation)
Attend leetcode contests and upsolve.
For design rounds, know your resume (Do not bluff in your resume)
For each round, think out loud explaning your thought process and it''s fine to ask hints from the interviewer.

Please feel free to post any questions and suggest if I missed anything to add.

System Design Resources :
I took a mentorship in preplaced to learn system design.
But the topics that were taught to me are covered in the below links.
Go for a mentor if you can as they are very good at resolving doubts.

https://github.com/donnemartin/system-design-primer
https://github.com/ashishps1/awesome-system-design-resources

Update : Comp details : https://leetcode.com/discuss/interview-question/4881928/Goldman-Sachs-or-SDE-2

Other interview experiences :
https://leetcode.com/discuss/interview-question/4882958/Google-or-SDE-III-(L4)-or-Rejected