My second official telephone interview from Google was with Sanjay Jain, an engineer in
Google, India. He telephoned me at 7.30 P.M PST. And the interview lasted for an hour and thirty minutes on the phone. Actually he had to phone me at 4.30 P.M but due to his travel schedule he missed. So he phoned me at the new time. He sounded an awesome guy who has some 14 years of industry experience. I was quite amazed that he was too agile in thinking and very good at algorithms.

Traditionally he started by asking me what I have done so far. So I explained him my projects and talked about my education and professional experience. He then started the technical questions. The first question that he asked me was about “Coin Denomination Problem.” (Yes the same coin denomination problem that I posted on my blogs). He asked me if I have heard of the problem. I told him that yes I have heard of it. He then explained me the problem again and then asked me to give the first solution that come to my mind. Instantly I gave him the greedy solution which is too trivial. He then inquired of any problem with my solution. I told him the problem and was asked to resolve the issue. Sanjay is a superb interviewer he gave me small hints from time to time, though I was at ease with this problem. I tried to figure out the recursive solution and formalize the recursion, but I was not able to do it quickly. It costed me much time to figure out the solution and I finally reached to the recursion. Now he said me to give the Dynamic Programming solution, which I did in the end.

He then asked me the traditional Google question. Yes the question was based on distributed computing problem. He asked me that there are random arrays on ‘n’ computer. Each of size of RAM of it’s computer. The arrays are not sorted. The problem was to sort the arrays. Now this is a tough question from implementation point of view. One has to take care about a lot of things. Any ways, I started by some old tricks to handle the problem. I came up with many solutions and many ideas, but Sanjay found minor or major problem in most of them. In end we agreed on that we will have to sort them logically, means the problem now remain of intelligently retrieving information instead of actually sorting the arrays. Its was a nice problem indeed.

Then he asked me if I liked puzzles. I said yups! I like them. He asked me that the puzzle he is gonna ask is a tough one and very few have solved it.(Btw I solved the puzzle and have never heard of it before). The puzzle he asked was, “You have some nuts and some bolts in random order. You cannot compare nuts with nuts and bolts with bolts. It is guaranteed that a nut will fit in one or more bolts. Now you have to sort both nuts and bolts separately in minimum complexity. ” I kept quiet for some time, thinking extremely about the puzzle. He asked me after some time if I comprehend the puzzle. I said, I am thinking yet. And instantly like a divine thought the solution came to my mind. I used quick sort approach and sorted both in n * log (n). (The exact solution I am not posting it, quick sort is a hint). He was happy with the solution.

At this point I felt some what accomplished and about 1 hour 20 mins have passed. He asked many things about Techlogix, my interviews at Microsoft. He advised me to try at Yahoo and other good companies. He sounded very stable, intelligent and witty in his approach. I talked too much things about Google. He told me that Google India is an exact copy of Google USA and told that he would like to meet me in India if am selected for an offer. On this happy tone this excellent interview ended.

Haroon