After having applied online, I got an email asking for dates to set up a phone interview. A week later, I had two back to back phone interviews of 45 minutes each with a 15 minutes break in between. Both the interviewers were extremely polite and pleasing. In the first interview the problem statement was, "Given a string containing just Rs and Gs, design an algorithm such that the output of the algorithm is a string which has all Rs in the beginning and all Gs after the Rs. The number of flips from Rs to Gs or otherwise should be minimum. The number of Rs and Gs in the beginning need not be the same as that in the end. However, the total length of the string needs to be the same." I started with a brute force solution, and improved on it. He asked me to explain the order of time and space complexity of the algorithm. I guess he was not very satisfied with the complexity I was able to achieve. I was then asked to write the code and read it.
The second interview was pretty standard with questions like write the code for finding the height of a BST. There was also one question involving hash tables.
