Dec 1st, 4:00 pm. I had a paper that morning, on 'Object Oriented Modeling'. Didn't sleep last night preparing for the paper. So, my condition wasn't its best for the interview.
They called at ten past four in the evening. The interviewer wanted to start off with the interview (coding questions) right away. So did I.
He asked me what my favorite language was (C++, C#). He then gave me a problem -

'You are given a string of characters. You are required to calculate the frequencies of each distinct character in the string.'

The solution is quite simple. I proposed 2 solutions.

'There are 2 sorted lists of integers. You need to merge the 2 lists into a third larger list which should also be sorted.'

Solution to this problem is also quite simple. I gave him an array-based solution, O(m+n).
He asked me to write the solution using linked lists. I did that too.

'Now suppose there are k lists, all sorted, instead of 2. And you want to merge all of those lists into a single large list which should also be sorted. How will you do that?'

I began to think over. Within 30 secs, he dropped a hint and i picked it up instantly. Using his hint, i gave him a solution of O(k*n). He asked me if i could do it better. I tried and proposed a couple of other algorithms, some better than others, but none as good as O(k*n). The interviewer was actually testing as to whether i can think of alternative solutions. He told me that your first solution was optimal. I just wanted to check if you can give other solutions. I was happy i could think of 3-4 alternatives to the same problem.

Like other interviewers, he too asked me if i had questions. I asked him about the 'procedure of the interview process at Google', since this third phone screen was unexpected. He said,

"This is your 3rd phone screen right? So according to my feedback, they will be inviting you onsite very soon. You will have 2-4 rounds of interviews at Google office."

and i was like... :D
Yet, this time too, i was not satisfied with my performance. I wished i get another chance to do the same interview and i would do better..

End of this (final) phone screen.

Read on,
Onsite Interview @ Google, Hyderabad.

..signing off

Original story...