Sunday, January 20, 2008

Google Interviews Part III

This continues from my first Google interview described here In overall, the second one was harder in terms of questions and expectations. I was called again from Mountain View sharply at the time we had arranged.

The conversation began with an interesting question: "What would you change in the Java programming language?" This has more than one questions embedded and it is educating listening to all possible answers. For example, one of my suggestions was having 'mechanisms' much like the properties fields in C# to ease development (programming get/set methods seems very tiring to me)Since the question was referring to the language and not to the Virtual Machine anything you find tiring or absent in Java is probably a valid answer.

We next proceeded to a C programming question. My interviewer knew that I was not a C-guru so he was gentle on that. The question was something like this. What is the output of this C program?
main() {
char X[500] = "Hello World";
printf("%s",X+5);
}

I knew it had to do something with memory allocation but I was not succinct on that. I said that the output would be blank and I guess I was right (the interviewers never tell you directly if you are right or wrong) So we said OK and moved on.

The 3rd question was about creating random functions. It is the type of questions where given a function randX that provides uniformly numbers from 1 to X, to generate a another randY. The actual question was about making rand8 from rand6. It is easy to establish how to get a rand2 from rand6. Then you can get rand8 from rand2.

This was a straightforward case. However, this problem appears very often in such situations and deserves some attention. You may find unlimited nonsense by searching for 'create rand7 from rand5' which is also a frequent question. Trying these forums/blogs etc you will get endless efforts of shifting from one rand to another using common arithmetic functions (addition, mod etc). This is nonsense. You will have to shift to elementary analysis for a while to get some good results.

In the general case consider you have to generate randX from randY where Y > X. Now consider that this yields the division: Y = n*X+r So, you can one group of Y elements into X groups of n elements and one more group with r elements. Now number the X groups as 1,2,3..X Then, create a 'machine' that uses the algorithm:
m = randY();
IF m belongs to one of the X groups return its number
ELSE restart the machine

The probability in every run of the algorithm to return one specific value from 1 to X is a =n/Y and the probability that the algorithm restarts is b = r/Y. So, the overall probability that the machine will output one number from 1 to X is :
P = a+a*b+a*b*b+a*b*b*b+... = a*(1+b+b*b+...) = a/(1-b).
By substitution we get, P = 1/X

In other words, we have generated the function randX
Now, if we wish to increase the rand range, for example get rand7 from rand5 you can create rand25 from rand5 (two rand5 calls) and then use the above method. Shifting to infinity is inevitable in some cases and all other efforts are in vain.

Back to the interviews, the final question had to do with designing and analyzing an algorithm. This had to calculate all representations of an integer as a sum of cubes. You can find many similar examples in algorithms textbooks so presenting this story here is trivial. What is interesting is that, we started a discussion on an incident that was directly related to the problem. This is usually called as the 'cab number story'. Back in the days when Ramanujan was in Cambridge and was working with G.H. Hardy, he had frequent health problems. One day, Hardy visited Ramanujan to the hospital and to start a discussion he mentioned the number of the taxi cab that brought him there. He said something like "..The cab number was 1729. I think this number is not interesting at all." A few seconds Ramanujan (which was extremely competent with numbers and calculations) replied: "You are not right Mr.Hardy. 1729 is very interesting. It is the smallest number that can be written as a sum of cubes in two different ways."

This was a nice way to close the interview. We didn't have much time left, so we said some relaxing things and then ended the interview conversation. All in all, it went well and my interviewer was a really nice person. Our discussion was interesting and I soon got the news that I was to pass to the next level. Having acquaintance with math and generally science history certainly helps!

Jump to the next Google interview.

20 comments:

Anonymous said...

in your second interview..your answer would be "World" not blank as you said..

ElectricTheater said...

I am not so sure. I remember compiling it and getting blank using MSFT compiler. I had to use char * and malloc to get it print "World"

jqb said...

I knew it had to do something with memory allocation

You are completely and utterly clueless.

I said that the output would be blank and I guess I was right

Uh, no. The correct answer is " World" (not blank and not "World"). Is it really that hard to count 5 characters?

I am not so sure. I remember compiling it and getting blank using MSFT compiler. I had to use char * and malloc to get it print "World"

That makes no sense at all.

ElectricTheater said...

@jqb

Jqb you have to study harder. And please stay cool.

A Guy on the Internet said...

$ cat >foo.c
main() {
char X[500] = "Hello_World";
printf("%s",X+5);
}

$ make foo
cc foo.c -o foo
foo.c: In function ‘main’:
foo.c:3: warning: incompatible implicit declaration of built-in function ‘printf’

$ ./foo
_World$

Shriram said...

Could you elaborate on the
creation of rand(25) from two rand5 calls?
are you trying to imply that
5*5 = 3*7 +4
where 25->multiple of 5 = Y
from randY

and 7 is the X from randX.

Why should I consider rand(25) only, and what's the basis for getting that thought?

Anonymous said...

Hi there all, here every person is sharing these knowledge, therefore it's nice to read this webpage, and I used to pay a quick visit this web site every day.
Here is my blog ; amber leaf

Anonymous said...

Hey very cool website!! Guy .. Excellent .. Superb .
. I'll bookmark your website and take the feeds additionally? I'm glad to seek out a lot of helpful information
here in the submit, we'd like work out extra techniques in this regard, thank you for sharing. . . . . .
Feel free to surf my site ; mac baren tobacco

Anonymous said...

Hi there! I know this is kinda off topic nevertheless I'd figured I'd ask.
Would you be interested in trading links or maybe
guest authoring a blog article or vice-versa?
My site discusses a lot of the same topics as yours and I believe
we could greatly benefit from each other. If you're interested feel free to shoot me an e-mail. I look forward to hearing from you! Excellent blog by the way!
Also visit my weblog ... amphora tobacco

Anonymous said...

I visited several blogs except the audio quality for audio songs existing at
this site is truly fabulous.
Also visit my web blog - golden virginia

Anonymous said...

Why people still use to read news papers when
in this technological world everything is available on web?
Feel free to surf my page - drum tobacco

Anonymous said...

Wonderful post! We are linking to this particularly great post on our website.
Keep up the great writing.
Here is my weblog ... old holborn blog

Anonymous said...

Wonderful post! We are linking to this particularly great post on our website.
Keep up the great writing.
My web page > old holborn blog

Anonymous said...

I'm now not positive where you're getting your info,
however great topic. I needs to spend a while learning
more or understanding more. Thank you for fantastic
information I used to be looking for this information for my
mission.
Also visit my blog ; borkum riff pipe tobacco

Anonymous said...

What's up, this weekend is nice in favor of me, because this occasion i am reading this wonderful educational paragraph here at my residence.
my web page: dave-wright.net

Anonymous said...

Hey just wanted to give you a quick heads up. The words in your article seem to be running off
the screen in Ie. I'm not sure if this is a formatting issue or something to do with internet browser compatibility but I figured I'd post to let you know.
The design and style look great though! Hope you get the issue fixed soon.
Thanks
Look into my web blog :: to get rid of acne

Anonymous said...

Pretty great post. I simply stumbled upon your weblog and wanted to say
that I've really loved browsing your blog posts. After all I will be subscribing on your rss feed and I am hoping you write once more soon!
Also visit my blog - homemade acne treatments

Anonymous said...


http://smarturl.co/njfhkyp To participate, please Comply aviator sunglasses maximum ease in this unisex retro aeronaut sunglasses alternative. airman sunglasses, you should pay attention to some points.

http://hkc.im/1Ww aviator sunglasses For Menaviator sunglasses feature that all the sunglasses that are sold in the Australian part mustiness Follow with these predefined standards. wayfarer sunglasses A occupation man, subsequently eroding a twin of flier Sunglasses, can as advantageously promise to observe the fastest in peril now and we should get hold of measures to protect those materials. Whenever summertime rolls approximately, it's that metre too pick out pliant aviator sunglasses.

Unknown said...

Would you not get done with the Java's checked exceptions. I would certaily answer that.

Anonymous said...

smokeless cigarettes, ecig forum, electronic cigarettes, electronic cigarettes reviews, electronic cigarettes, electronic cigarette