Google Interviews Part V - Just Two More Questions

This is the last part of posts describing my own experience interviewing with Google. You may find the first interview here and then follow the traces until this last one.

Time had already passed (almost a month) after three successive interviews with Google and this last one was most probably the critical one. I did not prepare for this as much as the previous. The whole thing tires you up and at some point it seems better to relax and concentrate on the psychology rather than the technical stuff.

I was only asked two technical questions, and since my language of choice was Java the interviewer wanted to see some Java code for the answers. In summary, this interview was perfect. While in all previous interviews, mostly the first and the second, I had some important flaws in my performance, but this one was different. And all this because I was playing in my field.

Google at some point asks for a CV. However, the way I see it, Google and other major software companies search always for something unconventional in the candidate's application. You could say of course you know 5 or 10 programming languages, or that you can build an internet spider in 1 minute, however there might be some knowledge you have, that is somewhat rare and hence you should mention. In my case, this is Number Theory.

For me, number theory is a passion that has not passed over time. It was love in the first sight, when I became aware of it, maybe at the age of 15 or so, and from that time it was the field mathematics that I was really feeling comfortable with. Anyway, it is not hard to see why it has been named as the "Queen Of Mathematics". First, it is very easy to grasp the basics (primes, divisors etc) since they are inherently tractable by the human brain. After all, every human being starts my learning how to count, which is the first step of the true intelligence, aka understanding that 5 ice creams and 5 cars, share something in common: that they are 5. This helps solving silly cases like, if I ate 5 ice creams and then I ate 1 more, how many did I eat? There is no need to think of ice creams, nor the eating process. All you have to do is to construct the proper model for this situation: use natural numbers and solve 5+1.

Another great thing with number theory, is that your 'lab' can be a blank piece of paper. You can argue that 15 is divisible by 3, but all you need is a paper to perform the division. While a physicist might say that in light speeds some hypo-atomic elements, called mambojambions, are created, he still needs a gigantic, CERN-like laboratory to test his theories.

Anyway, I myself was raised in a Pythagorean culture(numbers are holy) and so I claimed in my CV to know some number theory stuff. Although I was a little worried if I would be able to defend such claims (after I would be talking to Google), it soon proved to be a wise decision. Both in phone and on site interviews with Google, there was no better time for me than doing number theory. And to much of my surprise, and despite that Google's name is inspired by a natural number (or a unit of measure if you wish), all the 'Googlers' that I spoke and met with, did lack elementary knowledge on the field. This time, (I assume) the interviewer had dug in my profile and wanted to see for himself. Every question and conversation was related to Number Theory.

So, the first question was about sets: "Create a function, called powerSet(), that will output the power set of the input set." The power set in Algebra theory is the set of all subsets of a set (no..bull-set!) If a set has N elements then the power set will have 2^N elements. So if a set is denoted by {a,b} with a,b as elements then the power set is { {},{a},{b},{a,b} }.
The {} is the empty set. Note that all elements of the power set are sets. Recursion can help for solving this problem. If for example the powerSet function can produce power sets for sets that have at most N elements how should we solve for the N+1 case?

If we denote sets with capital letters and the initial set as A, we can use the following algorithm
1. define B set initially empty
2. a = extract one element from A
3. add powerSet(A) to B
4. for every set in B, say X, add a, and then add it to B
5. return B

Making the proper checks, this yields a function that can produce the power set of a set. For the Java case you can use the java.util.Set interface to write the code. I was asked to write the Java code but not asked any further questions, like complexity, runtime and so on. So we moved to the next and final question.

This was: "Create a function, called findZeros(), that will compute the number of zeros in the decimal representation of n!". Now this is interesting and despite seemingly easy it has subtle points. For example, 5! = 1.2.3.4.5= 120 has one zero and 10! = 1.2.3.4.5.6.7.8.9.10 = 3628800 and has two zeros. Now the obvious answer is to produce this C-style pseudo code:

int findZeros(int n) {
z<-0;
N<- n!
while ( N%10==0) { z++; N/=10;} return z;
}

It seems right but has a terrible flaw: it fails at very 'small' values of n, in our 4-byte world, for n=15. Using some Java code like below, we can verify this case.

int n=1,i=2,m=1;
while(n>=m) {
m=n; n*=i;
System.out.println("Previous value "+m+" Current value "+n+" Counter "+i);
i++; }
System.out.println("OOPS! Overflow!");

So, if our code works only for 14 cases, it is pretty much useless. We should do better than that.
For number theory geeks, like myself, this means show time! The equation below is called the Legendre's formula
and basically computes the factorization of n!. The exponent in which prime p is 'participating' in the factorization is the sum in the figure. Now, we should use it for our case. 10 is the product 2x5. So, the exponents of 2 and 5 in the factorization of n! defines how many zeros we get. For example, 10! = 1.2.3.4.5.6.7.8.9.10 = (2^8).(3^3).(5^2).7 So 2 is found 8 times and 5 is found 2 times in the factorization, hence if we pair up the 2's and 5's we get two zeros. Now, there are obviously more 2's than 5's in the expansion so finally we have to answer at the question:
What is the exponent of 5 in the factorization of n!?
Based on the reasoning above this is equal to the number of zeros of n!.
Based on Legendre's formula we have to calculate:
[n/5]+[n/5^2]+[n/5^3]+... to infinite. This is done for example by the following Java code

calculateZeros(int n) {
int s=0,r,p=5;
while((r=(n/p)) !=0)
{s+=r;
p*=p;}
System.out.println(n+"! has "+s+" zero"+((s==1)?"":"s"));
}

For example, 25 = 1.2.3....23.24.25 = 15511210043330985984000000. Running the above code will produce the message 25! has 6 zeros. Instead of messing with a number with 26 digits (25!) you only have to deal with the number 25. Why?

In the sum S(n) = [n/5]+[n/5^2]+[n/5^3]... the first term, [n/5], computes how many numbers up to n are multiples of 5. For the 25 case there are 5 of them: 5,10,15,20,25. The second computes all multiples of 25, i.e. only one. The third and all others are zero. A number that in its factorization, the prime 5 is in the power of k, e.g. 10 = 2.5 and k=1 or 25 = 5^2 and k=2, participates in the first k terms of the sum by adding one to each term. Hence its overall contribution is k, hence the sum S(n) calculates the power of 5 in the factorization of n!, and therefore the number of zeros in the decimal representation, Q.E.D.

That was it! There is no other way to handle such big values and the solution can deal with really gigantic numbers without explicit calculation. The interviewer had elementary number theoretic knowledge but was able to follow the reasoning and we had a very nice conversation after that. He seemed to be fond of such mathematical tricks as the one we dealt with.

In summary, I think this was the interview question that booked me the plane ticket to fly to the Google site. I was very satisfied after we hang up and I was impatient for the outcome but deep inside I was sure it was an ideal interview session and that my chances were great. The next morning I received a phone call from Google inviting me for the on site interviews. Mission was accomplished.

This post ends a series of posts in which I wrote about my phone interviews with Google along with many interview questions. For the on site interviews I am bound to an NDA so maybe I will post them encrypted! That's all for now about Google interview questions. Until, I come back for the on site experience remember a small tribute to Number Theory: "Die ganzen Zahlen hat der liebe Gott gemacht, alles andere ist Menschenwerk" (Numbers were created by good Lord. Everything else is human's work-Leopold Kronecker)

Google Interviews Part IV

This is the 3rd interview I had with Google. You can find the previous and the questions asked here:
* First Google interview
* Second interview

Update: Fourth Google Interview

In the 3rd interview I talked with a woman software engineer from Mountain View. As usually it lasted for about 45 minutes but there was a surprise waiting at the last question..But let's take things from the beginning.

The first question was a hard test for my memory: "How do you test your code?" This is a fair one for software engineers. But not for my style. I personally like things that are quick and dirty. For larger projects I use some of my own class libraries that employ some kind of logging, measure method execution time and so on. But saying "Well, I use my own class libraries." I thought would not be a good answer. Nor a professional one.

So talking about Java, I made the mistake of mentioning the JUnit framework. I had used for some time (long ago) but the time had passed so I had forgotten even the basics. And of course the interviewer started the questions (How the JUnit handles exception and others) To tell you a secret I had already opened in my browser a JUnit site (some kind of tutorial I guess) but this didn't help at all. So, don't do it. It will only make things worse. Trying to think logically didn't help either. The interviewer kept pushing, until I 'broke' and admitted that I couldn't answer. That was it. We moved to the next question.

All next questions were really typical, the kind you find in tech interview sites:
* "What is a Unix kernel?"
* "What is the difference between interfaces and abstractt classes?"
* "What is the difference between threads and processes?"
* "What is inheritance, polymorphism and encapsulation?"
* "What is overriding and what is overloading?"

I think there is no need to elaborate further on that. You most probably have come across these concepts and have your own mind.

Which brings us to the last question. Actually it was a puzzle including programming with handicaps, i.e. with small processor, low memory etc. The puzzle was this:
"You have 1000 integers. All are less than 1000 and greater or equal to 1. Among them, 999 are distinct and there is one that is found twice. How can you find the duplicate?" To this I gave an answer I think is optimal. The idea is simple. If you denote the duplicate number by d and the sum of all the integers by S then the following equation holds:
S-d= 499500 since S-d is the sum 1+2+3...+999 which is equal to 499500 by applying the formula 1+2+3...+n = n*(n+1)/2
Now the good thing is that we can be able to find the duplicate even we have capacity for one integer, or when reading from a stream and so on. We can optimize even if we apply modulus to the first equation: d = (S-500) (mod 1000) Now if d is equal to a positive number mod1000 then this is the duplicate, otherwise the duplicate is the negative part plus 1000. For example is 1 was the duplicate, then d=1(mod 1000) and the duplicate had to be the 1. If the duplicate was 600, then d=-400(mod 1000) so the duplicate had to be -400+1000=600. This means we do not need to have storage for integer (int type) but only the byte type is enough.

While fairly easy to grasp the interviewer had difficulties in understanding how this would work, so she asked for an example when we have 10 integers. I replied this would transform the equation to d =S-45 but then the counter question was disappointing: "How did you compute 45?" It is quite obvious however that I had to compute 1+2...+9 which is equal to 45 when applying the formula that Gauss found when he was 8. But the interviewer started computed 'by hand' the sum, adding the numbers from 1 up to 9, which left me speechless for some seconds. I mentioned that there was a formula for that but she didn't listen, still being concentrating on her computations. I didn't bother elaborating on the modulus idea since obviously would not give me any more credit.

After that, the interview had finished. I didn't ask anything, saying something like 'I have many questions but I do not wish to spend any more of your time' and we ended the conversation. In overall the last incident was really awkward. To that time I believed that all Google engineers had a good mathematical background. The engineer that I spoke with, did lack elementary skills. So in my eyes, the myth had been destroyed and it is a good advice to anybody, not bother berating himself more than he should. If you already knew the formula for the sum of consecutive integers, you have a good reason to feel more confident.

Update: Go to the last Google phone interview

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.

Google Interviews Part II

The first Google interview is most likely the easiest one.
I have the feeling that they normally ask general questions, just to ensure that you have some knowledge of computers and you are not just the guy who believes he deserves a place in Google because he can make nice Powerpoint presentations. At least happened in my case.

A guy from Mountain View called me sharply at the time we had arranged. He called on my mobile. I had everything arranged: From the bluetooth hands-free to nice and clean desk in front of me. At first, he asked me some questions about my CV, my age and my education. He didn't seem so interested in that and my impression was that his questions were somewhat mechanical.

After a couple of minutes, he started asking technical questions. The first one was easy: If we would like to index the entire earth population, how long should the index size be? Although a piece of cake, I felt like I was asked to prove that P=NP. Soon, I panicked but I asked for some time to 'warm up'. The Google Engineer was kind enough to understand and gave me all the time I needed in order to finally realize that I was talking to Google and that I had to control myself.

After recovering and answering to this question, I was put in front of a puzzle involving buckets and I was asked to find an algorithm that would end up in a situation that one bucket would be empty, as soon as some conditions were met. Excuse me for this vague description but I am still not able to remember exactly what the problem was all about. Instead of trying to find some exact solution to a problem that I couldn't understand (perhaps I was very nervous or I didn't understand the language), I followed an old Harry Truman's quote: "If you cannot convince them, confuse them". This seemed to work extremely well. I soon said something about modelling the problem as a Diophantine equation, where the solutions in integers would mean filling if positive or emptying if negative. Of course I had no idea what I was talking about, but the Google Engineer fell into it. He was not familiar with the idea, we soon started talking until we had switched to a more theoretical conversation. This gave me time to think over the solution and present with a backtracking-type of algorithm. During all this, I was asked some algorithmic-theoretical questions, for example about hashing space and time complexity.

We spent a lot of time on this problem. The last one was around his own domain of expertise. It turned out that this guy was working on Google Book Search and asked what I would if I had to find duplicates in book catalogs with entries with different titles but with the same content.. I had no idea of the format, Google was using to index book entries, I asked some questions that clarified the problem to me and then I presented my solution. My idea was to use some basic format properties of book text, for example number of paragraphs, size of paragraphs and so on. This way a book named "Albert Camus-The Stranger" would match a book "Famous Authors-L'etranger" (the example might not be realistic but it gives the idea)

The 45 minute had finished and it was time to ask my own questions. I asked a couple of things (one being if book search is still beta to which the engineer falsely responded that it is not!)and some other lame how-wonderful-is-Google questions and we said goodbye.

The next day I was informed by my recruiter that I had done well we had to proceed to the next stage. Overall, the guy I talked was very kind and showed a lot of understanding when I was stuck in the first and simplest question. But now I had to prepare for the 2nd interview which my recruiter had informed me that would be much more technical...

Continue to the second interview

Google Interviews Part I- Questions and more

This is a summary of my own experience on interviewing in Google. The process went quite well and lasted for about 40 days. I had 4 phone interviews and then they flew me to the Google Site I had applied to. I had 5 on-site interviews, quite stressful and lengthy to finally reach the bitter end 3 days later, when I was informed that I had the potentials but not matched to the exact expectations of the position.

Either you are into computers, or you are having your own interviews with Google or other major software company or you are just curious, you might find this topic to be at least interesting. Later I will reveal many of the questions they asked me but for what follows I will give my own summary view of this process.

I am sure you have heard for 'weird puzzles' or 'crazy questions' during the interviews (for example how many golf balls fit into a school bus? or how many piano tuners are there in the world?). Well, all these are total nonsense. Google is all about algorithms (Well at least the searhing-Google). If you are planning of preparing for interviews some textbooks on the subject might be a good start. Another good advice would be to check out the data structures and algorithms library available in the programming language of your choice (for example Java Collections Framework or .NET Collections package)

But don't be scared. Googlers are not creatures with extra-terrestrial intelligence. You will talk to people that are great scientists but also to people that are not. You will talk to engineers that honor their title but also to others that are merely mediocre programmers. Google is now a big company and this is inevitable. You will understand what I mean if you keep on reading the next blog posts.

So, a few quick tips would be:
1. Have a strong understanding of algorithms
2. Have a mastery on programming and especially the libraries available (collections)
3. Be calm and inspire confidence
4. Goto 1

These 4 advices are fairly general. You can customize it further for the Google case. For example since Google is a search company you should consider fair questions regarding Regular Expressions.

In summary, it has been a really unique experience. Google is really a great company and probably the best place for software engineers (too bad I couldn't see it my self). During the on-site interviews I had the chance to launch at the in-Google restaurant, which was really amazing, providing dishes literally for any kind of diet. You will also talk to interesting people and if lucky you will meet some of them and talk about subjects you are keen on. It is a challenge worth taking and be prepared to deal with all possible outcomes.

In later blog posts I will give out the entire set of questions they asked me during the interviews. You can find the 1st Google Interview here.I have recorded more than 20 questions but unfortunately I am not free to disclose the questions I was asked on site (I am bound to an NDA-Non Disclosure Agreement) Till then, enjoy your holidays!