Google Phone Interview

I had my first Phone Interview for Internship with Google yesterday. I was shortlisted for the Interview by Google, based on my CV and aggregate percentage. I was pleasantly surprised 4 days back when I received a call from Google Bangalore Office informing me of the Interview. So I started preparing for the Technical Phone Interview by revising the fundas of Data Structures, Algorithms and Language subtleties.

I came across a very good resource for coding and programming practice: TopCoder which helped me a lot in getting the fundas right practically.

Finally yesterday evening the phone came, and I was a hell lot nervous. The interviewer was checking my Resume and exclaimed about my Internship Project at NEC HCL (last summer). He asked me about the details of the project, like what enhancements I did and how it helped, which I could very happily explain.....

Then to programming stuff, I was given a problem where I had a large Integer Array and a given sum 'k'. I had to determine whether any two numbers from the Array would add up to k. He gave me various scenarios like the Array is sorted, unsorted and lot of extra storage space or not etc. I used Hash Table for the extra storage space case. I tried using Binary Search method for the In-Place case but could not optimize it for sorted Array, so I asked a teeny weeny bit of Hint and then the "Two Pointers Method" struck. He seemed satisfied with the responses.

I had to write all the above stuff in terms of code and read it out to him, which was pretty exciting :)

Next came another Question, I had a Binary Search Tree, given two nodes, I had to find the Nearest Common Ancestor. It seemed easy and I came up with the solution in just a Minute. He then Twisted the question a bit and generalized the Tree to a General Binary Tree. I asked for availability of parent pointer and he gave me choice. I came up with a recursive O((lg N)^2) algorithm if parent pointer was available. (Just after the Interview, when I was discussing with my Friend, I just got a better optimum O(lg N) algo (See Comments); I better hope these divine thought come during Interviews).
Then as it was obvious, he asked for the general case of no parent pointer. Just few minutes of thinking and a recursive solution was there. (Which I again had to code and read out to him :) ) After his call for optimization, I just applied some Dynamic Programming ideas and Voila!!

So, this was my 1 Hour 13 mins. long Interview which I enjoyed every bit of. Hoping for Selection into Round 2!!!
Now my Mid Sems are just 2 days away and I have not even read a word....So, I better go and start with some DataBases......

Á la procháine, Au Revoir!