Google Software Development Engineer Interview Questions and Answers

Round: Test
Experience: The written round was based entirely upon Algorithms and Data Structures. 
Complexity of various operations were asked and a few aptitude questions were present. 
Nothing much was asked about Databases etc.

Round: Interview
Experience: The interview was 3 rounds of pure technical stuff. The questions were tough. Typically 2 or more questions were asked in each interview (atleast one of which would be a coding question which you had to solve and code within the time limit of 45 minutes for both questions).
I was initially asked about the Euler Tour and how I would code up a solution. I gave the standard graph theory solution for the same. The interview realized that I knew about the problem and switched the problem statement and gave me a problem that I had not encountered before. The idea was to give you an unseen problem and see how you cracked it. 

The problem was:- Given a series of overlapping intervals, generate all the event points and the set of intervals that were currently overlapping the event point. eg. for the intervals (1 3) (2 6) (2 4) (3 7)(8 9) the event points would be (1 - (1 3)) (2 - (1 3) (2 6)(2 4))(3 - (1 3)(2 6)(2 4)(3 7))(4 - (2 6)(2 4)(3 7))(6 - (2 6)(3 7))(7 - (3 7))(8 - (8 9))(9 - (8 9)). After solving this problem, I was asked about some general questions about designing distributed databases for a high volume application and distributed data centers and how to adjust for geographically distributed queries.

Round: Interview
Experience: In the 2nd technical interview round, the first question was an analytical one about proving or disproving a statement involving a grid of size 2^n by 2^n. The question asked whether it was possible to tile the grid using an L shaped tile of size 2x2 leaving just one square empty. The second question was to code up the delete node operation on a BST.

Round: Interview
Experience: This one was relatively easier where the question involved adding 2 numbers of equal number of base 10 digits stored as a singly linked list of digits. 
Allowed operations were only forward traversal of the linked list with O(1) extra space and a time better than 2 traversals of the linked list.

General Tips: Study hard (especially Algorithms, Graph Theory and Data Structures) for
the interviews. They don't care about HR stuff and they look for high CG candidates.
Skill Tips: Primary preparation was from 2 sources:
1) In the early stages (about 2 months before Day 0 of placements) - I read through Cormen et al
(Algorithms - MIT Press) and solved problems from Codechef and other sources. I also read through the TopCoder tutorials on Dynamic Programming, Graph Algorithms and Tree Based problems.
2) In the later stages (15 days before Day 0) - I read through the book "Algorithms for Interviews". It has a number of tough problems on DP, Graph theory and specialized algorithms for specific problems (eg. O(n) solutions for certain cases). Also, I went through the past year interview questions of all the CS companies available - MS, Adobe, Amazon etc. A few days before Day 0, I also went through my previous year notes on Operating Systems, Databases etc.
3) One thing that I neglected was implementing the code for basic data structures (Tree insert, delete etc.) but I should have done that as part of the preparation as I was caught off guard by one question about my basics. I would recommend reading C++ Data Structures and Algorithms by Lippman. (Some others also recommend C by Kerninghan and Ritchie as a way to brush up your language skills).
College Name: IIT-ROORKEE