YOE: 5+ years
I recently interviewed for Google. This is my experience
Round1(Elimination)(45 minutes)
https://leetcode.com/discuss/interview-question/1681277/google-phone-card-suit
I initially came up with sorting based solution for this. O(nlogn). After discussing with interviewer, I figured he wanted O(n) solution. After thinking a bit, I went ahead with Counting sort like technique as number of cards in a suit is only 13. I coded the solution in time.
Verdict: Strong hire.
Round 2(45 minutes)
This was the hardest round for me. The question asked was very similar to this
https://leetcode.com/problems/maximum-score-of-a-node-sequence/
This question caught me off-gaurd completely. I initially started with Multi Source BFS. but interview hinted that complexity of that would be too much and asked me to come up with something else as there were only 4 nodes in a sequence. kept on discussing with interviewer and he kept dropping hints. Maybe it was my good day but the solution just clicked in my mind. For every edge(u,v), I just have to find one node connected to 'u'(lets name it x) and one node connected to 'v'(lets name it y). this would give me sequence of 4 nodes. I made the mistake of not considering the case where x and y are same, but interviewer pointed that case out and i was able to solve it. I was able to further optimize it, thinking that for every node we can sort connected edges in descending order of their value to process nodes greedily. Finally I was able to code it in time.
Verdict: Lean/Strong Hire
Round 3(45 minutes)
Design a Rate Limiter which has a Minute based and Hour based Limit. (hour based limiter is not 60 times minute based)
I designed the class for it and discussed basic methods in the class. After we agreed on a model of class, I proceeded with implementation.
I came up with a 2 deque based solution which was pretty straight forward.
Follow Up: What if you are getting millions of request every minute.
I thought about it a bit, and interviewer dropped a small hint. Problem with my original solution was redundant entries in queue. I realized even if i am getting millions of hits, It is only possible if I am getting multiple hits for same timestamp. So i used a map to keep the count in case I had multiple hits for same timestamp. This way the minute deque can have atmost 60 elements at any point of time and hour deque can have only 3600.
Interviewer seemed satisfied :)
Verdict: Strong Hire.
Round 4(~55 minutes)
Interviewer started with simple question. Print leaves of a tree.
I was able to implement it.
Follow Up: Then she asked given 2 trees. return true if traversal of leaves is same for both trees.
https://leetcode.com/problems/leaf-similar-trees/
I was able to do both of them in 15 minutes or so. :)
She then asked me this question:
Given a parking lot with parking space from 0 to 10000. We need to check if a car can be parked. We would first call canPark(location) method with a location (eg. 12.4). Each car would take (location - 0.5, location + 0.5) space. If car cannot be parked, simply return false. If yes, call the park(location) method to park it. Implement these methods.
bool canPark(double location)
void park(double location)This is basic variation of insert intervals problem.
https://leetcode.com/problems/insert-interval/
I coded this one pretty fast.
Follow up:
Implement one more method isSpaceAvailable() which would return true if there is any slot left for a car to park in whole parking strip.
bool isSpaceAvailable()I was able to implement this in O(n) in time left. This round was a bit longer due to sheer amount of questions.
Verdict: strong hire :)
Got a call from recruiter saying my googlyness and behavioural round is to be scheduled in coming days as feedback is positive from all rounds.
Fingers crossed.