Goldman Sachs | SDE(Analyst) | Bangalore | [Offer]

My journey began with a referral from a friend at Goldman Sachs. With 1.5 years of experience at a customer-based company and a B.Tech + M.S. in CS from a Tier-1 college, I was applying for an SDE (Analyst) position. The entire interview process was quite extensive, stretching over 5-6 months and comprising 7 distinct rounds, mostly conducted over Zoom.

Round 1: HackerRank (1.5 hrs)

This was an online coding round with two questions. I quickly solved both within 15-20 minutes:

• An easy mathematical formula-based problem (too vague to extract).
• A medium DP-based problem to find the total increasing subsequences of a given size 'k'.

Round 2: Coderpad + Telephonic (1 hr)

This round also had two questions, and I cleared both with all test cases within the allotted time:

• Maximum Water Trap: I solved this using a stack, though I later learned there was an easier two-pointer approach.
• Maximum Tree Size in a Forest: Given a set of disjoint graphs, I had to find the graph with the maximum number of nodes. I used BFS on all nodes while keeping track of visited ones.

We also discussed work-life and other aspects of Goldman Sachs.

Round 3: Face2Face over Zoom (1 hr)

Two interviewers asked a total of four questions. I wasn't asked to code but had thorough discussions on each, including complexities and relevant data structures:

• Sorting with Limited APIs: Sort an array using only two provided APIs: one to get the index of the maximum element, and another to reverse the array from index 0 to `i`.
• O(1) Min in Stream: Implement a data structure to get the minimum element in O(1) time, allowing push and pop operations. I used a stack of pairs to track the minimum.
• K Stacks in One Array: Create 'k' stacks using a single array of a specific size. This took some time and hints to find the best solution.
• Tree Validation: Check if a given structure is a valid tree, including checks for back-edges and cycles.

I felt this round went 'good', maybe a bit below due to the third question.

Round 4: Face2Face over Zoom (1 hr)

Again, two interviewers. After a brief intro about their team and my work, they asked three questions. I wasn't asked to write code but was confident I could if needed:

• Limited Size Transaction Queue: A variation of a limited-size queue to process transactions within a time limit. I used a normal queue approach, and while a circular queue was hinted at, my solution was satisfactory.
• LRU Cache: The problem was posed differently but through discussion, it was identified as a standard LRU cache design problem.
• Search in Rotated Sorted Array: Search for an element in a sorted but rotated array. I explained the standard binary search approach with tweaks for rotation and convinced the interviewer with dry runs and test cases.

This round went very well, making me positive about proceeding further.

There was a long wait of 3 months after this round.

Round 5: Face2Face over Zoom (1 hr)

Two interviewers, starting with brief introductions. This round involved coding questions followed by CS fundamentals:

• O(1) Insert, Remove, GetRandom: Design a data structure for O(1) insert, remove, and `getRandom()`. I used a map to store values and their indices in an array, and `rand()%size_of_array` for random access. I coded this part.
• First Unique Character (with Multithreading Follow-up): Find the first unique character in a string. I solved both the simple and multithreaded (discussion only) approaches.

After the coding, the other interviewer delved into various CS subjects:

• Types of storage in C++.
• `Integer` vs `int` in Java.
• Understanding memory leaks and their occurrence (stack or heap).
• TCP vs UDP.
• Debuggers and their usefulness.
• Garbage collection.

We also had an in-depth discussion about my projects. Overall, this round was good, though I wasn't highly confident in some of the CS questions. The interviewers were very friendly and helpful.

Round 6: Face2Face over Zoom (1 hr)

This round was with two interviewers from London and New York. After discussing my work and tech stack, they asked why I was transitioning from a research profile to an SDE/Analyst role. We covered two main questions, and I was asked to code one:

• Unique Paths (with Diagonal Follow-up): Calculate unique paths from top-left to bottom-right, allowing down/right movement. I discussed DP with O(m*n) and space-optimized O(n) solutions. The follow-up extended to allowing diagonal-down movement, which I also approached with standard and space-optimized methods.
• XOR of All Bits of a Number: Find the XOR of all bits of a number. I presented an O(n) approach (n: number of bits). The interviewer challenged me to optimize it, hinting at an O(log n) solution which I couldn't come up with. The discussion on my tree approach for this question seemed to confuse the interviewer, and I later realized it was still O(n). There's a trick to this one that I hadn't encountered before.

They also shared insights about the global team and the analyst role's expectations.

Round 7: Special Offline Exercise (3 hrs)

This was a take-home assignment given to be solved and submitted within three hours. It focused on evaluating my OOP knowledge, code quality, test case writing, handling edge cases, and choice of optimized data structures. I also had to provide a README and descriptions of different code parts. This was a general assessment, not a specific question to extract.

Overall, it was a very tiring and stretched interview process, but receiving the offer made it all feel worthwhile.