I got a referral from a friend at GS. After clearing the online assessment, there was an initial / screening round on Coderpad.

After more than a week of that, they scheduled the Superday wherein I was told that there would be 4 rounds back-to-back.

R1:

1. Given an input string, find out the first non-repeating character and replace further characters with it till it's occurrence is found, put # if none.
   e.g, input : aabcbaf, output : a#bbccc

• I used HashMap to count the frequency and Queue to maintain the current non-repeating character.

2. Given a linked list, find out if it is palindrome. Do it with O(1) space complexity.

• Using the two pointers (fast & slow), I reached to the middle of the list and reversed the list from there.
• Kept a tail pointer at the end and checked if the nodes from head and tail are same or not.
• 1 -> 2 -> 4 -> 6 <- 4 <- 2 <- 1

R2:

1. Given a list of 2n size. Let's say that the first half (0 to n-1 elements) of the array is a subarray A and the second half (n to 2n-1 elements) of the array is a subarray B. Shuffle the array such that it becomes like this: [A1, B1, A2, B2, A3, B3, ..., An-1, Bn-1]
   I gave a solution which was using an extra array. The interviewer asked me to optimize it by using O(1) space.

2. Given a BST, find the Kth largest element from it.
   I traversed the tree in this fashion: right -> root -> left and maintained a counter counting the no. of elements visited.When the counter hits K, current element will be returned.

   As a follow-up, the interviewer asked me what if the tree is just a binary tree and not a BST. By the time, I could provide an optimized solution, the time was up.

R3:
This round was mostly revolved around my past experience and fundamentals. They asked me 1-2 questions regarding some common problems in system design:

1. You have a platform wherein you have some 'prime' users and others are normal users. You have to design a system which can prioritize the orders from the 'prime' users but should not altogether avoid the orders from the normal users.
2. You are running a news portal and there are various types of news (Political, Sports, Cinema, International, etc.) that you are getting from various sources. How would you design a system which can send the notification to the users who have subscribed to a particular topic if a news related to that topic arrives?

R4:
This was the last round and was scheduled after I successfully cleared the previous rounds. All the questions were typical behavioral in nature and related to learnings from my current job.

After half an hour, I got a call from HR that I was selected.