Hi,

Sharing my onsite experience with Google. This was my first invite at Google onsite interview.

Telephonic round:
Already posted here: Google Telephonic

Onsite sound:

1. [Difficulty: Medium] Calculate number of subarray of only 0's possible in a given string consisting of only 1's and 0's. Constraint is that each occurance of 1's seperates out the 0's subarray.
   Example 1: if given [0,0,0], number of subarray possible are 6 which is [0], [0], [0], [0,0], [0,0], [0,0,0]
   Example 2: If given [0,1,0], number of subarray possible are 2 which is [0] and [0] (for the first and the last position).
   Example 3: if given [1,1,0], number of subarray possible are 1 which is only [0]
   Example 4: if given [1,1,1,1] number of suarray possible are 0, since there are no 0's.

Advanced, Follow-up:
Calculate the same 0' subarray for 2D matrix.
**Example: **
[[0,0,0,0,0]
[1,0,0,1,0]
[1,0,0,0,0]
[0,0,1,1,1]]

2. [Difficulty: Easy] Object Oriented design: Given an XML document. Parse the document into an objects of tag.

3. [Difficulty: Medium] Variation of Course Schedule III Given list of schedule, with start time and end time, return the scheduled grouped by over lapped of schedule.
   Example:

Input:
[[5,9],
[5,10],
[7,11],
[11, 12],
[3,4],
[2,5]]

Output:
[
[[5,9],[5,10],[7,11],[11, 12]],
[[3,4], [2,5]]
]

4. [Difficulty: Medium] Given a Binary Tree and given N, you need to find out if Nth index element is existing in Tree or Not. You need to do that in O(logN) time. Output is in True or False.

5. [Difficulty: Medium] Given a list of points in the 1st Quadrent of coordinate plane, you need to return the list of points that covers all other points.

Example:
Input: (1,2),(4,5),(6,7),(5,6),(8,9),(6,15),(1,12),(2,6),(9,9),(1,9),(4,6),(8,8),(9,8),(9,10),(8,10),(10,9),(11,9),(19,1),(15,3),(12,5),(14,4),(1,20),(20,1)
Output:(1,20), (6,15),(8,10),(9,10),(10,9),(11,9),(12,5),(14,4),(15,3),(19,1),(20,1)
See visually here

Overall Interview Experience:
It was a very easy interview round for me. The questions that were asked to me were within my capability and I was never stressed out during the interview. I had a lot of time to discuss alternative solutions.

Only point where I made a big tragic mistake was I was calculating 3 - 2 = 0, and this was pivotal in making a choice for a solution for question 3. I was thinking out loud, and miscalculating loud and neither my interviewer nor I corrected this mistake. And by the time I found what mistake I was making I ran out of time to code. But I explained my interviewer my approach.

I also took more than required time to understand question 4, but then came up with correct answer really quick. I felt like interviewer intentionally obfuscated the question.

Overall feedback:
Interviewers after Round 2 and Round 5 said they would love to work with me. During round 5, my interview was over at 3:00pm, but I was discussing my solution for more than an hour after interview because interviewer said he has never seen such solutions. He was trying hard to break my code, but all the test-cases passed his test. We together worked on a mathematical proof of my solution, and he was very delighted with our discussion.

Recruiter said that my 3rd round hit me hard. It was a very close call.
Round 4, I got feedback I could have used a better Data structure.
Extra appreciation for writing clean codes. They want me to try next time again.

Will try next time again.

My key priorities for preparing coding interviews:

1. Write clean code.
2. Don't waste time in Dynamic Programming. Dynamic Programming is an optimization technique, and you don't solve problems with dynamic programming. You only optimize solved code. A clean solution can easily be converted to dynamic programming optimization.
3. Heaps and Priority Queues are critical Data structures.
4. Learn reusable solutions and coding techniques, and use them as frequently as possible as building blocks. You need many well tested building blocks during coding interview to attack any problem.
5. Re-evaluate your solutions and make them as clean as possible.
6. Don't handle edge cases, avoid them all together (whenever possible). If there are lot of edge cases in a solution, then be sure you are in the wrong direction.

My solutions coming soon.