I just finished my google interviews. Verdict: Reject
Mock interview: Given a binary search tree, and a range [L, R], find all keys that lie within the range.
Solution: Run a recursive inorder traversal and if the key you are exploring, doesn't lie in range, don't go to right.
Followup: Write an interative approach.
Verdict: Strong Hire (Coded and interviewer said it works)
Screening: Q1 Given an array of integers, and you can jump to arr[arr[i]] from arr[i]. Find the minimum cost to reach n-1.
Solution: Wrote a DP solution. (Coded and interviewer said, he is fine with the solution and it works)
Q2. Given an array of integers representing the height of fences and a paint brush able to make horizontal and vertical strokes. 1 stroke is counted as not lifting the brush from the fence. Find the minimum number of strokes to paint the fence.
Solution: If any fence height is 0 then array breaks into two parts at that point. Find the minimum of (max height of each such part, size of that subarray).
Verdict: Strong hire (Coded and interviewer said, he is fine with the solution and it works)
Onsite 1: Imagine you have an RPC server that produces log of entries and we're analyzing it offline. There are two entries for each call, one when the RPC starts and one when the RPC finishes processing. We'd like to know as soon as possible if there's an RPC that took too much time / timed out given a threshold.
Followup: If multiple request at same time stamp. Start and end times are not unique.
SOLUTION: Use a list and map<int, list::iterator>
Verdict: Hire (Coded and interviewer said, he is fine with the solution and it works)
I fumbled a bit initially and suggested using a queue instead of a list but finally was able to write a working code.
Onsite 2: Given 12 tiles, each with a color and a number. Find if 4 winning hands exist. 1 winning hand consists of 3 tiles, and is decided by either all tiles are same (both colour and number) or (color is same but number are consecutive)
Solution: backtracking
Verdict: Not hire (Coded and interviewer said she is not sure if it works well. I tried proving that backtracking would always yield the correct answer. Implemented some pruning as well.)
Is there a better solution for this one? She was arguing that why would backtracking work well, which really felt like a stupid question because backtracking is exhaustive search, it just tries out all possibilitites.
Onsite 3: Make an ad server, that given some ads with content and a score, build an insert ad and serverAd(this serves best ad). The higher the score, the better the ad. We have to take care to not serve same ad consecutively.
Solution: use a max heap of scores and store the ad served previously.
Follow up: Now each ad also contains a delay(let's say 5, possibly different for each ad) with it which represents we can't server that ad until the next 5 ads. The previous question was a case with delay as 1 for each ad.
Solution: Use two heaps. After serving an ad, insert that in the new heap as insert the delay + ads served so far. And before serving any ad, check if any of the ads from the second heap can be inserted back in heap1 (basically the ads whose delay period has ended).
Verdict: Not hire (Coded and interviewer said, she is fine with the solution and it works).
NOT HIRE came as a shock to me. I coded it properly, no syntax errors. If she was not satisfied then why did she say that it was fine.
Googlyness and Leadership: Some questions about how I deal with my managers, my juniors. How would I deal with stressful situations, etc.
Verdict: Hire
Not feeling good at all right now. Gave my complete 3 months of time without any lapses. This was my best interview performance so far. I came up with the solution of all questions and was able to code and also dry run and show how it works. I am still unable to belive onsite 3 result. onsite 2 I knew already i was getting rejected. If onsite 3 had went fine, there might still be some hope but right now 3 months of effort down the drain.