My first official telephone interview from Google was with Lawrence IP, an engineer in Google, U.S.A. He telephoned me at 11.00 P.M PST. And the interview lasted for an hour on the phone. He started by asking me about my graduation and then came straight to my work in Techlogix. He asked me about the application that I made for Nestle Pakistan. Asked general things and then asked about the most challenging thing in the project. After done with that he came to the technical questions. The first thing that he asked me was, “What do you think essentially happen, when you will write ‘Haroon Saeed’ in the Google Search Engine and hit search.” Now that was a very open ended question, and I can talk too much on it. So I started by exactly what is written in exact abridged version of the paper of Sergey Brin and Larry Page( Co-CEOs of Google). Well then he asked a more proper question that “Haroon Saeed” will be broken in tokens and then a document id list for ‘Haroon’ will be retrieved and similarly an document id list for ‘Saeed’ will be retrieved separately. Now how can we find those id’s which contain both Haroon and Saeed. He asked me to give an algorithm with minimum possible complexity. I gave an algorithm of n1 * log( n2 ). And he then said to improve it, so I tried and then gave an algorithm of complexity ( n1 + n2 ). At this point there was a lot of distortion in the telephone line, but we had to go with that. He said that’s a fine solution and moved on to next question.
Next question that he asked me was even more open ended and one of very strange question as I wasn’t able to understand a single word of him, because of distortion and noise. What I understood in end was, suppose you have a web page url like that of your blogs. Now this particular blog has many other pages and links. He then asked, “Given a certain site’s page url how can you find the rule the site is using to generate url for that very page”. Now this is a weird question to ask ( in my view ). I came up with a tree sort of solution and a recursive solution, but he wasn’t able to comprehend it well. At this point 55 mins had passed and he said, that he is ending the technical interview here. He told me to ask some thing about Google. I asked him that why Google has not been able to convert most of it’s test products from BETA to a standard product. He laughed a bit and then said he himself don’t know why. He gave me his official e-mail to share with him any good puzzle or programming question, and said he will tell the recruiter to keep me updated and ended the call.
It was not a very good interview from my point of view. He was in hurry and didn’t ask me much. I wasn’t sure he will get a positive picture of me. So that is it for the first interview. I will write about the next Google Phone interview which is more exciting and one of my career’s best interview that I have ever took.
If you iterate through the list of docs containing “Haroon” and generated a subset of docs which has “Saeed” in it, you will get the list of docs containing both “Haroon” and “Saeed”. Thats O(n1). Does that sound right?
By: raster on January 6, 2007
at 9:19 am
It is reply to raster’s comment.
I think raster is wrong to conclude the complexity O(n1). It may be O(n2) if Saeed has more docs than that of Haroon. So, O(n1+n2) represent the complexity in a right way.
By: Muhammad Rizwan Asghar on March 21, 2007
at 7:13 am
isn’t the problem equal to: given two lists of integers (document id). find the ids that appear in both lists. ?
By: ThanhSon on April 7, 2007
at 12:06 am
Thanks for this post. Many interview questions can be found at http://www.technical-interview.com
By: Lee on May 2, 2007
at 12:43 pm
hi is the answer to hash???
By: ntrphanikumar on May 3, 2007
at 5:17 am
The answer is, assuming the integers are sorted, to walk them at the same time:
List l1, l2;
List ans = /*new List*/;
byte toInc=3; /*Bitmask*/
int lastRead1;
int lastRead2;
for (int pos1=0,pos2=1,n1=l1.size(), n2=l2.size(); pos1 < n1 && pos2 < n2; ) {
if ((1&toInc) != 0) {
lastRead1 = l1[pos1++];
}
if ((2&toInc) != 0) {
lastRead2 = l2[pos2++];
}
if (lastRead1 == lastRead2) {
ans.push(lastRead1);
toInc=3;
} else if (lastRead1 < lastRead2) {
toInc=1;
} else {
By: Michael on September 3, 2007
at 12:37 pm
Yeah – can’t edit.
The answer is, assuming the integers are sorted, to walk them at the same time:
List l1, l2;
List ans = /*new List*/;
byte toInc=3; /*Bitmask*/
int lastRead1;
int lastRead2;
for (int pos1=0,pos2=1,n1=l1.size(), n2=l2.size(); pos1 < n1 && pos2 < n2; ) {
if ((1&toInc) != 0) {
lastRead1 = l1[pos1++];
}
if ((2&toInc) != 0) {
lastRead2 = l2[pos2++];
}
if (lastRead1 == lastRead2) {
ans.push(lastRead1);
toInc=3;
} else if (lastRead1 < lastRead2) {
toInc=1;
} else {
toInc=2;
}
}
return ans;
}
Probably better to only store offsets into an existing list too and to count backwards if order is not important.
By: Michael on September 3, 2007
at 12:38 pm
plz tell me what do they ask on telefone ….i have applied for soft. engg., as a fresher graduate.
By: tanay on September 10, 2007
at 2:14 pm
You cant run though both lists at the same time cause there are not ordered.
By: Marcus on November 17, 2007
at 2:35 pm
[...] http://haroonsaeed.wordpress.com/2006/07/17/google-phone-interview-part-1-2/ [...]
By: One Fab Fit Mom - Weight Loss Success! » Want to interview at Google? Check out these unbelievable… on January 23, 2008
at 10:18 pm
The coin denomination solution that you’ve posted isn’t correct…
here is a better version:
http://cmonkeyfreeware.blogspot.com/2008/02/coin-denomination-problem.html
By: Cmonkey on February 27, 2008
at 6:05 pm
Hi, I’m T. Naren from India. I’m pursuing PG diploma in IT. I want to do MS(IT) and then I want to join in Google. Could you please tell me how to prepare for the Technical round. If possible tell me what kind of questions they will ask.
Thank you.
By: Naren on January 28, 2009
at 7:50 am
Hi,
I had my interview with Google for associate product manager .. you can read the interview here
http://ferozeh.com/Interviews/Google/google.php
hope it is useful to others..
By: jhon on June 26, 2009
at 12:41 am