Status: Currently employed with 3.5 years of experience at a product based company
Education: B.Tech CSE

Date of Interviews: The interview process ran for 2 months from November - December 2021. Google recruiters are really nice and they give you ample amount of time and resources to prepare.

Round 1: Technical Screening (45 mins)
Given an array, Find the maximum sum possible when you have to remove k elements from either end of the array.
eg. (3, 100, 1, 1 and k = 2 ) output = 103 (remove 3rd and 4th element).
There was a follow up question where a cost factor was associated with every array element and then we had to find out maximum sum where [sum = (arr value * cost factor)]. This was a small tweak to the original problem.

The expectation was to take the interviewer through entire thought process and present working code for both the approaches.

Round 2 : Onsite Technical 45 mins
Create a complete binary search tree (BST) using singly sorted linked list.
The problem was left open ended and interviewer wanted me to ask clarifying questions and present working code. Here we need to utilise the property of a complete tree and a BST

Round 3: Onsite Technical 45 mins
Warm up question: Given a text, you need to fit it into a page of fixed width. Return the minimum number of lines needed on that page so that word integrity is maintained (words are not broken into lines, leave the space if word is not fitting).
Main question:
Given two strings of data that you would like to put into a two column table on a fixed width page. Find the column sizes that minimises the overall height of the table.
(Example: consider creating a two column table in MS word, you can move the partition line between 2 columns so that table height is impacted. You need to return the index of that partitioning line which minimizes the overall size of the table).

Round 4: Onsite Technical 45 mins
Design a scheduler that can acceptTask, removeTask for all users and getNextScheduledTask. The Task will have an associated dueTime by which it needs to be completed (Ambiguous question, needs to ask a lot of questions to the interviewer).

The expectation was to write nice modular workable code which is optimal.

Round 5: Onsite Googlyness 45 mins
Introduction (2 mins), What is the favourite problem that you solved and were you satisfied by the end result? Many follow ups on the mentioned . How did you team up with different teams. Were they willing to help you? If you weren’t getting the help you needed how did you resolve this?
What would you do if your peer is feeling left out
Have you ever had trouble managing your work? Have you ever been stressed out?
Have you ever pushed back on to your manager?

After these 5 rounds, the recruiter told me that I had 3 positives (2 forL3 rather than L4 and 1 for L4) and 1 negative interview feedback. She told me that she'll build up my application and send it over to GHC for review. She sent me a whole form to collect data about my qualification and current role. I filled it up and after one week I was told that the committee wants to conduct 2 more technical rounds before taking their decision. And if I make through these 2 rounds, then I will be selected for L3 and not L4.

Round 6: Technical 45mins
This was a graph question, please refer the image to get more context.

Part 1: Given an input category (electronic, wireless, telephone etc), return all the transitive parents of that category:
(Input: Iphone (Category: Smartphone) Output: (1,2,3,4,5) (all the transitive parents of that catefory))

Part 2: Given a filter, You need to model it and return the answer
Filter example: 1) Mark down all the telephones that are not wireless device
2) Mark down all communication device except wireless device
The interviewer wanted me to design and model this filter class and how will I convert it. This was more of a design subproblem rather than focussed on coding I felt.

Round 7: Technical Round 45 mins
Part 1: Given a graph structure with a source and a treasure node. Some of the graph nodes are locked. It takes one unit of time to move from 1 node to another. You cannot move via locked nodes. Return minimum amount of time taken to reach the treasure.

Part 2: lets say you cannot reach the treasure. Now you have to unlock minimum number of locked nodes so that you can reach the destination. (Time is not a factor anymore)
Hint given: Min cost to reach source to destination where cost is the number of locked rooms in the path

I implemented workable code for both the parts.

Final Verdict: Reject
After these 2 rounds, I got a call after almost 2 weeks and the recruiter informed me that I got 1 strong hire for L3 and 1 partial/ neutral hire and the committee has decided not to pursue my candidature further.

All in all the interviewers were experienced, they know what questions they were asking. It was a good problem solving session with each one of them. The recruiter used to provide me updates as soon as she had any with as much detailed feedback about the interviews as possible.

Downside is that they downleveled the designation and even didn't hire for L3 after 7 rounds. Anyways, I hope this post helps other candidates who are preparing!

Hints below: skip it if you dont want to read!

1. Standard knapsack pattern DP problem
2. Dont work your brain to modify the single linked list into a complete BST, rather than create a complete BST structure first with dummy data and then fill it with the data from singly linked list
3. First part is simple, for second one, use binary search to get the optimal partitioning index which will give minimum height of the table
4. I modelled the problem by taking and clarifying assumptions about the nature of the task, User and the APIs that needs to be implemented. I presented a solution which used a Map<String(userId), PriorityQueue> data structure as a scheduler with implementations of all the APIs.
5. No hint as such, just be transparent with the interviewer
6. Part 1 was simple DFS (just store the parent links in adjaceny list instead of childern). For part 2 I did give some java class representations with several classes but the interviewer didn't seem to be satisfied.
7. Part 1 is simple via BFS, and part 2 can be done with the help of dijkstra's algorithm