I had my Google interview last year. The HR called and scheduled the phone call. The initial phone screen was a LC medium problem in merge intervals. I was able to crack it with the follow up questions. Then by the time onsite interview are scheduled, Google announced hiring freeze. After 3-4months I contacted the HR and he forwarded my resume to other teams and got call for onsite rounds.
First Round - Technical Coding
The question was similar to this:
https://leetcode.com/problems/employee-free-time/. Its LC Hard. But instead of time its days. There is another input "count" that mention number of free days required and have to return "count" days in an array.
0: ((1,3),(6,8))
1:((5,7))
count: 5
Result: (4, 9, 10, 11, 12)
Discussed the solution with interviewer and he asked me to proceed with implementation. The solution was to store the free days from first employee to a vector. From second employee onwards, delete the element in vector if he is not free at that day. At the end if the result is not of size then, add the rest after max day till it reach count.
The interviewer said he is happy with the solution. He siad he doesn't have any follow-up question. There was no time to discuss complexities. Actually I forgot about it and he didn't ask as we have only 2 minutes left at the end.
Second Round - Technical Coding
The question was to book a table in restaurants. Its LC Medium with a LC hard follow-up. This is like a design question. He asked me which all APIs I provide and what data structures. Then he said he is satisfied the way I designed but don't need that much information. So we will proceed with adding 3 interfaces: add a booking, delete a booking, assign a booking.
I used a map with customer size and vector of booking ids. When a table is free,
get lower_bound of map which will return the vector booking ids.
If the map entry size is greater than table size, return the prev map entry.
Pop the front of vector and return it.
This solution was accepted and he asked me to proceed with coding. The follow-up was how to do if table size is also configured. I suggested to keep an availability list and free list as well. So we can assign the best one based on the customer size.
In this round as well, we didn't discuss about time complexities. There was enough time at the end but I forgot to mention about time complexity and he too didn't ask about it.
Third Round - Behavioral
This was about my past experiences and how to handle different situations. It was a feel good round.
Fourth Round - Technical Coding
By this time, I was super exhausted. The question was same as this: https://leetcode.com/problems/remove-k-digits/
This was rated as LC Medium here but I felt it as LC hard. I suggested a recursive solution but the interviewer needs an iterative one. I was not able to think anything and seems super saturated. After a lot of discussions, did something that will remove the first digit. I still asked him for a recursive option but he said its good to proceed in an iterative way. This round was a disaster.
One thing I felt is, it should have been good if I split the interview over 2 days. That way, we will be fresh for both interviews and didn't feel exhausted.
The first two rounds i was quite happy the only drawback being not able to discuss time complexities. I had a small ray of hope. I expected 3 Hires and a No Hire.
Feedback: Rejected. Good reviews from the team but the algorithm can be better for coding rounds. Behavioral round was very good.
Btw, Is there any other way to do these problems?
Hope my experience will help you guys. Best wishes.
Thanks.