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.