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!
Original story