Nov 3rd, 5:00 pm. I was a little nervous. As for pre-interview preps, i took all my important papers (projects, semester mark sheets, etc) and placed them on my table. I had also some of my codes opened on my laptop screen for quick reference, if needed. Though, none of such preps ever was of any use.
Finally the phone rang. It was a female interviewer.
"Hi, is this Rajat?".. and the interview began.
First question she asked was about my recent academic projects. I talked about one or two projects of mine. She then asked me what programming activities i involve myself in, other than college courses'. I mentioned TopCoder, GCJ, SPOJ and other such contests. She showed some interest in my standings in these contests.
Next, she asked a problem and wanted me to code on that.

'Given a set of integers, how would you find out the 2nd maximum element?'

I gave two solutions to this question, the second one being optimal. But i wont talk about it here right now, since it will kill readers' imagination. I wrote a code for the same and dictated it back to her. The code had a small bug. It wouldn't run for a corner case. I dont know if she noticed that bug. Next question was,

'There is a town with N people numbered 0 to N-1. Some people of this town knows some other people. The relation between them is not necessarily symmetric. i.e. If a knows b, doesn't mean b knows a. This town needs a mayor. The requisite for being a mayor is that he should be famous and impartial. Being famous means that he should be known to everyone in the town. Being impartial means that he should not know anyone in the town. Consider a function knows(i, j) that return true if i knows j or false otherwise. Write a program to return the list of people who are eligible for the mayor's post.'

In google interviews, for every question, we are supposed to first propose the logic/algorithm to solve the question, and then write code for it. So was the case for this question too. I proposed an algorithm to solve this problem. She guided me through indirect hints(by asking questions that would lead me to her hint) to arrive at an almost optimal solution. I say 'almost' because even at the end of the interview, she kept on saying that there's a small bug in the code (and never revealed what it was), which i had not been able to figure out yet! Guess, it was one of the Google's interview pattern - say there is a bug even if there isn't any, to confuse the interviewee.

The interivew lasted for around 1hr 5 mins. She asked me if i had any questions. I asked about work culture at Google. Quite expected. She wished me best and advised to continue with coding at Topcoder and GCJ, and solving puzzles. She also said that the HR people will get back to me soon. With that it ended..

I was expecting a 'Thank you' call from Google, given the kind of average perfomance i had shown at the interview. Really wished i had a chance to give this interview once more and i would give my best this time.

To my surprise, i got a call for my second phone interivew on 7th Nov. :-)

Read on,
Second Phone Screen with Google.

Original story...