The Googleinterview process is Infamous for it’s mind boggling and creative methods to test new candidates. Here are two I’ve selected for you to first try to solve yourself, then see Google’s perfect answer.
Q. How many golf balls will fit in a Mini?
A.
We will use a new mini opposed to a classic mini shape.
It is shorter than a person, so maybe its 4.5 feet high, but with the clearance off the floor, lets say roughly 4 foot. There’s space for two people to sit side by side, with roughly 2.5 feet per person. So that’s 5 feet wide. It’s probably two people long, which is approximately ten feet. However the bonnet takes up half the length, so the usable length is 5 feet. The interior volume, then, is about 4 X 5 X 5, which is 100 cubic feet.
A golf ball is somewhat bigger than an inch in diameter. Let’s say that 10 golf balls line up to make a foot. A cubic lattice of 10 X 10 X 10 golf balls, an even thousand, would just about occupy a cubic foot. That gives a quick answer of about 100 X 1,000 = 100,000
Or ….. take into consideration that each ball could be packed more densely given the shape of each. Effectively resting in an imaginary Lucite cude whose edges equal the ball’s diameter. You stack those Lucite cubes like building blocks. This would mean that the balls occupy about 52 per cent of the space. Break out of the imaginary Lucite boxes, and you can pack far more balls in a volume. This is an empirical fact. Physicists have done experiments by pouring steel balls into big flasks and calculating the density. The resulting random packing occupies anywhere from 55 to 64 per cent of the space. That’s denser than a cubic lattice. It’s also a fairly large range. How you fill the container matters. When the spheres are added gradually and gently, like sand pouring through an hourglass, the density is at the lowend of the range. When the container is shaken vigorously, the spheres settle into a denser packing of up to 64 per cent.
Where does this leave us? Someone willing to painstakingly stack golf balls in the cannonball pattern can pack about 42 per cent more gold balls in the mini than you’d estimate from a cubic lattice (or as above). That seems an absurd amount of labor, even for an absurd question. The reported density of stirred random packing is a more realistic goal. You might achieve that by pouring golf balls into the mini and stirring with a stick to settle them. That would give a density of about 20 per cent more than that of a cubic lattice. You might therefore increase your final estimate by 20 per cent, from 100,000 to 120,000.
For the record, the Mini website states a Mini Cooper Hardtop is 145.6 inches long, 75.3 inches wide (including mirror) and 55.4 inches high. The regulation diameter of a golf ball is 1.690 inches, give or take 0.005 inches.
Q. It’s raining and you have to get to your car at the far end of the car park. Are you better off running or not, if the goal is to minimize how wet you get?
What if you have an umbrella?
A.
To answer this question, you must reconcile two conflicting trains of thought. The case for running is this; the longer you are in the rain, the more drops fall on your head, and the wetter you get. Running shortens your exposure to the elements and thereby keep you drier.
There’s also a case for not running; In moving horizontally, you slam into raindrops that wouldn’t have touched you had you been standing still. A person who runs in the rain for a minute gets wetter than a person who just stands in the rain for a minute.
That valid point is mostly besides the point. You have to get to your car and there’s nothing to be done about that. Imagine yourself zipping across the car park at infinite speed. Your senses are infinitely accelerated, too, so you don’t slam into cars. From your point of view, external time has stopped. It’s like the bullet time effect in a movie. All the raindrops hand motionless in the air. Not one drop will fail on your head or back or sides during the trip. The front of your clothing will sop up every single raindrop hanging in the path from shelter to car.
When you travel at normal speed, you’re fated to run into those raindrops or, rather their successors. At normal speed, you also have drops falling on your head. The number of raindrops you encounter will depend on the length of your horizontal path and also on the time it takes to travel that path. The length of the path is a given. The only thing you can control is the time it takes. To stay as dry as possible, you should run as fast as possible. Running makes you less wet –provided you don’t have an umbrella.
Had you an umbrella as wide as a city block, and where you able to hold it, it wouldn’t matter whether you sauntered or sprinted. You’d be dry as toast.
Most umbrellas are barely big enough to keep the user dry when he or she is standing in general, vertical rain. In practice, you expect to get a little wet.
Umbrellas work by creating a rain shadow, a zone where there are no raindrops. In a vertical downpour, and with a circular umbrella, the rain shadow is a cylinder. When the rain is coming at an angle, the rain shadow becomes a skewed cylinder. However, as every seasoned umbrella user knows, its best to point the umbrella in the direction of the driving rain. This makes the rain shadow a proper cylinder again. Now pointed at an angle to the vertical,
The standing human body doesn’t fit so well into a slanted cylinder. Were a hurricane driving the rain at you horizontally, you would have to hold the umbrella horizontally, and a tree foot diameter would protect only about half your body. The rest would get soaked.
Wind is bad, and so is motion. The skilled umbrella wielder knows to tilt the umbrella forward, in the direction of the motion, to get the maximum coverage. In fact, wind and motion are indistinguishable as far as optimal umbrella pointing goes. Running at ten miles an hour in windless, vertical rain demands the same tilt as standing still in tenmile an hour wind. Either way, the raindrops are coming at you ten miles an hour, horizontally, in addition to their downward velocity.
In vertical rain, you’re best off walking slowly. The umbrella will not have to be tilted much, and your body should fit within the rain shadow. Ideally, you should walk no faster than the speed where the rain shadow just covers your feet. Then you’d stay dry.
Reality is messier than that, there are always going to be gusts of wind, spatter from pavement, and runoff from the umbrella itself. The rain hitting the top of the umbrella does not disappear: it slides off the umbrella and falls in a cylindrical sheet encircling the rain shadow. There is more rain in that run off zone than anywhere else. That means that any part of your body that intersects the runoff zone gets wetter faster than it would have you not used an umbrella at all.
The advantage of slowness diminishes in high headwinds.
The umbrella has to be pitched at such angle that your lower body is out of the rain showdown. You’ll get half soaked no matter what you do.
All that reasoning boils down to the advice you may have heard from mum: walk if you’ve got an umbrella: run if you don’t.
You have 1 to N1 array and 1 to N numbers, and one number is missing, you need to find the missing the number. Now you have 1 to N2 numbers, and two numbers missing. Find them.
Solution:The question can be elucidated as follows.Given an array of size N1 containing numbers less than N and with out any duplicates!! We knew that there is a number missing from the array say K .Let S be the sum of the elements of the array.
Sum of first N natural numbers=N*(N+1)/2
and S=N*(N+1)/2 – K.Now putting this other way around we get K=N*(N+1)/2 S !!
Now the second part of the question says that there are 2 of the first N numbers missing.Let they be X and Y.
We solve this problem by solving 2 essential equations.
They are X+Y=N*(N+1)/2 S (1)
X*Y=N!/P (2) where S and P are the cumulative sum and product of the array entries.
You have cycle in linked list. Find it. Prove that time complexity is linear. Also find the node at which looping takes place.
Solution:The problem of checking whether there is a cycle or not can be solved using 2 pointers one moving in increments of 1 and the other in increments of 2.If there is a cycle then these 2 pointers meet at some node say N1 inside the cycle otherwise the fast pointer reaches the end of the list.This is a O(N) solution.
Now coming to the identification of the node at which looping took place.After our identification of cycle ,both the pointers P1 and P2 are at node N1.Now iterate the slow pointer to count the no of nodes in the cycle.(After traversing the whole cycle P1 and P2 shall again be at the same node).Let this size be K.Now take one of the pointers to the head node and count the no of nodes till N1.Let this number be X.Now use one of these pointers to reverse the cycle starting from N1.Only the cycle gets reversed.Now again traverse from head node to N1.Let the number of nodes this time be Y.Let the no of nodes from head to the start node of the cycle be Z
Now X+Y=2*Z+K .Hence solve for K and then having figured out the start node N2 of the cycle.Now as the cycle is reversed having figured out this start node its next node is the looping nodes so set the looping nodes next pointer to NULL and reverse the list further till you reach N2.Questions on my project please be prepare well about your projectHow do you search for a word in a large database.How do you build address bar in say gmail. i.e. if you press ‘r’ then you get all email starting from ‘r’, and if you press ‘ra’ then you will get emails starting from ‘ra’.
Question: How to find the Least Common Ancestor for 2 nodes of a binary tree?
This sounds like "On finding lowest common ancestors: simplification and parallelization", by Baruch Schieber and Uzi Vishkin, SIAM J. Comput. Vol 17, No 6, December 1988. A google search leads me tohttp://ia700208.us.archive.org/12/items/onfindinglowe00schi/onfindinglowe00schi.pdf.
I actually wrote an implementation of this for fun  it is in a zip file miscellaneous forfun Java code that you can find off a link from http://www.mcdowella.demon.co.uk/programs.html.
(The algorithm needs linear space and time for preprocessing, then runs at O(1) per query).
All the below questions are to be done in O(n) time complexity.
1>Given an array of size n1 whose entries are integers in the range [1, n], find an integer that is missing. Use only O(1) space and treat the input as readonly.
2>Given an array of size n2 whose entries are integers in the range [1, n], find two integer that are missing.
3>There is an array A[N] of N integers. You have to compose an array B[N] such that Output[i] will be equal to the product of all the elements of A[] except A[i].
or
Example:
INPUT:[4, 3, 2, 1, 2]
OUTPUT:[12, 16, 24, 48, 24]
Solve it without division operator and in O(n).
Solution :
1>Let the missing number be M. We know that the sum of first
N natural numbers is N*(N+1)/2. Traverse through the array once and
calculate the sum. This is the sum of first N natural numbers – M or
S=N*(N+1)/2 – M. Therefore M = N*(N+1)/2 – S.
2>Similar approach to the first one. Traverse the array once and
calculate its sum and multiplication. Let the sum be S and
multiplication be M. Let the missing numbers be P and Q. From above we
know that P+Q = N*(N+1)/2 – S. Also P*Q = N!/M. So we can get P and Q
from these two equations.
3> Lets first see the C++ solution.
void solution(vector<int> A)
{
int N=A.size(),i,j;
vector<int> L(N,0);
vector<int> R(N,0);
vector<int> B(N,0);
for (i=0,j=N1; i=0 ;i++, j–)
{
L[i] = i==0? 1 : A[i1] * L[i1];
R[j] = j==N1? 1 : R[j+1] * A[j+1];
}
for (i=0; i
{
B[i] = L[i] * R[i];
printf(“%d “,B[i]);
}
}
Most is clear from the program. Anyways, through the L and R we calculate the multiplication of terms to the left and right of ith term. then finally we multiply it to get the result.
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
hypoatomic elements, called mambojambions, are created, he still needs
a gigantic, CERNlike 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..bullset!) 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 Cstyle 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 4byte 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 workLeopold Kronecker)
This is the 3rd interview I had with Google. You can find the previous and the questions asked here:
* First Google interview
* Second 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:
Sd= 499500 since Sd 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 = (S500) (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 =S45 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.
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 Cguru 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/(1b).
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!
Q:
What should I expect from a phone interview with Google?
I have a phone interview which I never done this kind of interview by
phone. What should I expect? Learn? Prepare?
Any tip may help.
A: First of all, congratulations on having the opportunity to work at a top company...
You must have very attractive credentials on paper.
I believe you live in Austria. I think Google is headquartered in Mountain View, CA with offices all over the world.
There are a couple reasons well run corporations conduct telephone interviews.
It provides them with a costeffective way to screen you,
without having to pay to fly you to Milan, Zürich, or the US for an in
person interview.
It offers the HR function the
opportunity to gather basic information about you and do a high level
corporate fit test. Be sure you are fluent in your strengths and
"weaknesses". Make yourself focused about where you want to be in 5
years...whether you are or not. Think of the 23 top things that you
bring to the table. Be sure they come out in the Q&A somehow.
And, prepare 35 good questions you want answered by them. You may
only get time to ask one. Make it a good one.
If you pass this first screen, you will be interviewed by someone in
the area/function in which you would be working. These interviews can
sometimes also be done by telephone, especially if the candidate who
looks attractive on paper lives far away.
Eventually, you will be brought in for face to face meetings, possibly supplemented by videoconference interviews.
I don’t know the type of job you are interviewing forbusiness?
engineering? staff? etc.? But, Google has a reputation for hiring the
best and the brightest.
On the phone, they have the ability to evaluate how well you
communicate and how you think. Depending upon how important the latter
is, they have the ability to give you "brainteasers" or cases to
solve. Typically, solving the problem is secondary to seeing how you
structure your solutions and go about problem solving.
Don’t be nervous. It will help you to prepare for the interview.
Show that you have done your research into the company and in
particular into the division in which you are hoping to work. Do what
you can to find out specifics about Google’s recruiting process from
other Google candidates who have gone through it successfully. Perhaps
there are alumni from your university employed there. Speak to them.
Hals und Beinbruch! (not literally, of course...) Viel Glück!
Sources: decades of interviewing experience on both sides of the desk
Q:
What is the protocol after a phone interview? Do I write a thank you note/email?
I know that after a regular job interview, one should write a thank you note. Should a thank you note be written after a phone interview? Also, is it acceptable to send an email thank you note if you do not have the person's work......
A: Definately
Speaking
from Human Resources experience, something as small as a thank you will
make a huge impression. It's not much effort on your part, and it will
help solidify a phone conversation in the minds of the interviewers and
company.
I myself would never do a formal letter after a phone interview or phone screen, but email is perfect.
Also, keep it short and sweet. Thank them for the opportunity,
not the interview (this keeps it positive). If by some chance you can
put a quick sentance in that personalizes the thank you, do it . If you
spoke with the interviewer about something noninterview related,
making a light, one sentance comment about it is fine. Something you
would say to your grandmother or pastor/priest/reverend will be the
test on appropriateness.
EXAMPLE:
Mr. Smith 
Thank you for the phone conversation and the opportunity, and
looking forward to the next step of the process. Hope that your Cubs
make it past this weekend!
Regards,
Employee X
One last thing: Stay away from animated emails, backgrounds, and
use a general font (Arial, Times New Roman, Helvetica, etc.)
Q:
Do you care about A ‘Dream’ Come True?: US Approves The First Google Phone!
A ‘Dream’ Come True: US Approves The First Google Phone New York Times, United States  Aug 18, 2008 The new phone is an important step in Google’s plans to expand the company’s presence beyond the personal computer and into the mobile......
A: Google seems to be a company
that is determined in dominating the technology market.
I don't care about their phone, but I can imagine it giving a run for its money to Blackberry and iPhone.
Free cafeteria food, annual ski trips to the Sierras and free
laundry are just some of the fringe benefits of working at Google.
Getting hired is the trick.
Every month, aspiring workers deluge the popular Mountain View,
Calif., search engine with up to 150,000 resumes  equivalent to a
stack of paper at least 50 feet high. And the company claims to read
each and every one.
As one of Silicon Valley's hottest companies, Google has become a
beacon for job seekers. In just a few short years, the interest has
helped the company amass an arsenal of what is arguably among the
world's top technology minds.
"I would argue that definitely they have the best talent," said Joe
Kraus, a cofounder of the Web portal Excite Inc. who currently leads a
startup, JotSpot, in Palo Alto, Calif. "They invest so much because
the more great talent you have, the easier it is to attract even more
great talent."
Google hires nine new workers a day. In less than two years, the number of employees has more than tripled to 4,989.
The growth spurt is being fueled by a gangbusterslike online
advertising market and Google's boundless ambition, including new
initiatives in everything from wireless Internet access to video
downloads. The goal is to keep the production line of new products
humming so that users spend more time on the Web site.
Getting rich is what drives some of the applicants. Many Google
workers became instant millionaires at the time of the company's
initial stock offering in 2004. To this day, prospective employees are
drawn by the promise of wealth, although their chances of striking gold
are a lot lower now that the firm's shares are soaring above $400,
making stock options less likely to appreciate by large amounts.
Competition for the best and brightest is fierce. Rivals Microsoft
Corp. and Yahoo! Inc., plus startups, are trying to reel in many of
the same job applicants, igniting occasional bidding wars.
Hiring is a major challenge
Yahoo!, in particular, has recently landed some workers who
interviewed at Google, such as Andrei Broder, a former research
executive at AltaVista and IBM. He says being at Yahoo!'s research lab
is an opportunity to have more impact because it's younger and smaller
than those of its competition.
Sergey Brin, Google's cofounder, has called hiring one of his
firm's biggest challenges. If it's unable to find enough topnotch
workers, he says the company's rapid growth could be hamstrung.
Google's also hiring superstars. This year, they include Vint Cerf,
one of the Internet's founding fathers, as chief Internet evangelist.
KaiFu Lee, a former Microsoft executive and expert in technology that
turns speech into text, now heads operations in China. And Louis
Monier, founder of the early search engine AltaVista, has an
undisclosed technical role.
To lure workers, Google offers perks, including free cafeteria
meals, free use of laundry machines, a childcare center, a free annual
onenight ski trip (resort destinations vary depending on office
location), dogfriendly offices and an onsite doctor. Engineers can
devote 20 percent of their time to projects of their choice. What's not
mentioned is that much of the largesse is designed to keep workers at
their desks longer.
In addition to posting job openings in newspapers and online, Google
recruits at universities, offers computer science students free pizza,
hosts a software programming competition and invites technology clubs
to hold their meetings at its headquarters.
Last year, the company won attention for publishing a booklet of 21
problems called the Google Labs Aptitude Test. Readers of several
technology magazines were asked to mail in their answers and promised
that Google would get in touch with them if they scored well.
One question asked: "In your opinion, what is the most beautiful
math equation ever derived?" The Gaussian integral, a complex
mathematical equation used in studying the kinetic molecular theory of
gases, among other things, has been suggested as a smart answer by some
on the Internet. Another question involved filling a blank rectangle
"with something that improves upon emptiness," leaving applicants
scratching for a subjective winner.
Judy Gilbert, Google's staffing programs director, says the
questions weren't really used for hiring. In any case, smart alecks
soon posted the answers online so they could be easily found by
cheaters.
Hundreds of recruiters keep the resumes pouring into Google. Many
are contractors, making them easier to dismiss if the company scales
back its hiring needs.
Jobs available as of last week include someone to negotiate video
licensing deals with Hollywood studios, someone to lead user studies
for guiding product design and an attorney to manage the firm's real
estate. More posts are likely to open in announcements this week, as
the company is creating 600 new jobs in Ireland and up to 100 in
Pittsburgh.
To land allstars, Google's recruiting machine goes into overdrive.
Secrecy is sometimes critical. If tipped off, companies from which
Google is trying to poach could start a bidding war or retaliate
against a potential defector.
The risk can be worth it for a top executive of Lee's caliber. He
ultimately accepted a compensation package of more than $10 million,
igniting the legal battle between Google and Microsoft.
To fill positions lower on the pecking order, Google has created an
extensive collegehiring program, among other efforts. Recruiters
visited 60 schools this year to show off the firm's technology, hand
out Tshirts and interview prospective job candidates.
Interviews at Google usually begin on the telephone. If successful,
applicants are invited for facetoface meetings with up to 10 people,
a process described as excruciating by people who have gone through
them because of the length of time it takes and the mental gymnastics
necessary.
Recent job candidates described questions as being on topic, whether
about software code or business. In many cases, they were asked to
brainstorm and roleplay to show how they think. For instance, how
would they market a product? Those who conduct the interviews
frequently challenge applicants. Questions about algorithms, Java
software and computer networking are common for applicants seeking
technical positions.
Google has created its own software system for tracking job
candidates that allows employees to share comments on each applicant.
Because so many people must sign off on new hires  Larry Page, one of
the firm's famed cofounders, approves each one  the process can be
lengthy, even excessively so, several applicants said.
Some were shocked to learn the importance Google gives to college
gradepoint averages in deciding whom to hire. The emphasis draws
complaints from some older candidates, who believe the measure is
irrelevant for them because they have been out of school for so long.
In general, Gilbert says Google seeks applicants who show they are
willing to take risks, are highly motivated by a range of topics and
want to be part of something bigger than themselves. The profile is in
line with the firm's carefully crafted iconoclastic image.
Historically, Google has paid workers less than the industry standard and showered them with stock options.
That paid off for approximately 1,000 Google employees in 2004, when
the company's highprofile initial stock offering made them instant
millionaires. Although the firm's current pay structure is a closely
guarded secret, one can assume hundreds, if not thousands, more have
become worth seven figures, at least on paper, considering that
Google's stock is now hovering above the $400 mark, a nearly fivefold
increase from its premiere.
After its initial public offering last year, the company has had to
offer more money upfront because options aren't as valuable,
compensation experts say.
Many competing firms claim Google has driven up salaries for software programmers by nearly 50 percent in recent years.
According to one source who wanted to remain anonymous, the
beginning salary for programmers is now about $45,000. How accurate
this is cannot be known, but at least it's a clue.
BENEFITS GOOGLE TEST QUESTIONS
A test published by Google last year in several magazines was used as a recruiting tool. Questions included:
1) Solve
this cryptic equation, realizing of course that value for M and E could
be interchanged. No leading zeros are allowed: WWWDOT  GOOGLE
DOTCOM
Answers: 777589  188106
589483 or 777589  188103
589486
2) How many different ways can you color an icosahedron with one of three colors on each face?
Answer: 58,130,055
3) Which of the following expresses Google's overarching philosophy?
a) I'm feeling lucky
b) Don't be evil
c) Oh, I already fixed that
d) You should never be more than 50 feet from food
e) All of the above
Answer: b
 San Francisco Chronicle
BENEFITS
Workers at Google get a range of benefits that surpass those at many other companies. Here's a sample:
Free cafeteria meals
Onsite dry cleaning
Coinfree laundry room
Free annual ski trip
Dogfriendly offices
Onsite doctor and dentist
Free commuter shuttle service to several Bay Area locations
Source: Google Inc.
Given a number, describe an algorithm to find the next number which is prime.
There are 8 stones which are similar except one which is heavier
than the others. To find it, you are given a pan balance. What is the
minimal number of weighing needed to find out the heaviest stone ?
Answer:
Divide the stones into sets like (3,3,2). Use pan to weigh (3,3).
If
the pan is remains balanced, the heavier is in the remaining (2). use
pan again to find which is heavy from (2). (Total pan use 2)
If the pan does not remain balanced when weighing (3,3), pick the
set of stones that outweigh other. Divide it into (1,1,1). use pan to
weigh first two. It it remains balanced, the remaining stone is the
heavier, otherwise the one outweighing other is heavier(total pan use
2)
[These questions from 'Taher']
Order the functions in order of their asymptotic performance
* 2^n
* n^Googol ( 10^100)
* n!
* n^n
Answer: n^(whatever constant), 2^n, n! (==> n^n / e^n ), n^n
what is the best and worst performance time for a hash tree and binary search tree?
Answer:
Best is O(c), worst is O(log n)
Questions regarding a string Class
* What do you need when you instantiate a string ( i said a byte array and possibly the length) ?
* What is the best and worst time for the operation 'equals'
* How do you spedup the 'equals' operation (i said used hash MD5 for example)
This still has some problem ( a hash can be the same for unequal strings)
> Use Boyer–Moore string search algorithm => O(n)
Trade offs between a multi threaded and single threaded implementation ?
N threads .. n resources .. what protocol do you use to ensure no deadlocks occur?
There are a set of 'n' integers. Describe an algorithm to find for each of all its subsets of n1 integers the product of its integers.
For example, let consider (6, 3, 1, 2). We need to find these products :
6 * 3 * 1 = 18
6 * 3 * 2 = 36
3 * 1 * 2 = 6
6 * 1 * 2 = 12
last one is simple
int mul = 1;
for i = 1 to N
mul *=a[i];
for i= 1 to N
a[i] = mul/a[i];
(I got this question, your answer is not correct)
First of all if a[i]=0 you get an exception, the guy wanted me to use dynamic programming to solve this.
Here's the dynamic programming solution:
You want to build a table where x[i,j] holds the product of (ni .. nj). If you had such a table, you could just output
for (int i = 1; i <= n; i++)
{
if (i == 1)
print x[2,n];
else if (i == n)
print x[1,n1];
else
print x[1,i1] * x[i+1,n];
}
To build the table, start along the diagonal (x[i,i] = ni). Then do
successive diagonals from previous ones (x[j,k] = x[j1,k] * x[j,k+1]).
1. Describe Sorting algorithms and their complexity  Quick sort, Insertion Sort, Merge Sort
2. If you had a million integers how would you sort them and how much memeory would that consume?
Binary tree  requires 1,000,000 integers x 4 bytes = 4 MB + left pointer and right pointer = 12 MB
Insertion sort  can be done in under 4 MB
3.Describe an alogrithm to find out if an integer is a square? e.g. 16 is, 15 isn't
a) simple answer  start at 2 and divide the integer by each
successive value. If it divides evenly before you reach half way then
it is.
b) complex answer after much leading  Do the bitwise AND of n and
(n1). If it is zero then it is a square (I think this is wrong. This
actually tests whether n is a power of 2).
No, it almost tests whether n is power of 2. It falsely proclaims 0 to be a power of 2. More info: http://graphics.stanford.edu/~seander/bithacks.html#DetermineIfPowerOf2
C)
i=2;
while(!NO)
{
if((i*i)==Number)
{
NO;
return True;}
if((i*i)>Number)
{
NO;
return false;}
i++;
}
4. How would you determine if adwords was up and running and serving contextual content ?
5428907816463810488188
Here are some questions I got on my first interview with Google (slightly altered for NDA reasons).
1 Suppose you have an NxN matrix of positive and negative integers.
Write some code that finds the submatrix with the maximum sum of its
elements.
2 Write some code to reverse a string.
3 Implement division (without using the divide operator, obviously).
4 Write some code to find all permutations of the letters in a particular string.
5 You have to get from point A to point B. You don’t know if you can get there. What would you do?
6 What method would you use to look up a word in a dictionary?
7 Imagine you have a closet full of shirts. It’s very hard to find a shirt. So what can you
do to organize your shirts for easy retrieval?
8 You have eight balls all of the same size. 7 of them weigh the
same, and one of them weighs slightly more. How can you fine the ball
that is heavier by using a balance and only two weighings?
Phone interview
1. Describe the data structure that is used to manage memory. (stack)
2. whats the difference between local and global variables?
3. If you have 1 million integers, how would you sort them efficiently? (modify a specific sorting algorithm to solve this)
4. In Java, what is the difference between static, final, and const.
(if you dont know java they will ask something similar for C or C++).
5. Talk about your class projects or work projects (pick something
easy)… then describe how you could make them more efficient (in terms
of algorithms).
In person interview
1. In Java, what is the difference between final, finally, and finalize?
2. What is multithreaded programming? What is a deadlock?
3. Write a function (with helper functions if needed) called toExcel
that takes an excel column value (A,B,C,D…AA,AB,AC,… AAA..) and returns
a corresponding integer value (A=1,B=2,… AA=26..).
4. You have a stream of infinite queries (ie: real time Google
search queries that people are entering). Describe how you would go
about finding a good estimate of 1000 samples from this never ending
set of data and then write code for it.
5. Tree search algorithms. Write BFS and DFS code, explain run time
and space requirements. Modify the code to handle trees with weighted
edges and loops with BFS and DFS, make the code print out path to goal
state.
6. You are given a list of numbers. When you reach the end of the
list you will come back to the beginning of the list (a circular list).
Write the most efficient algorithm to find the minimum # in this list.
Find any given # in the list. The numbers in the list are always
increasing but you don’t know where the circular list begins, ie: 38,
40, 55, 89, 6, 13, 20, 23, 36.
Retrieved from "http://alien.dowling.edu/~rohit/wiki/index.php/Google_Interview_Questions"
Here is a bunch more:
How many golf balls can fit in a school bus? This is a Fermi question.
You are shrunk to the height of a nickel and your mass is
proportionally reduced so as to maintain your original density. You are
then thrown into an empty glass blender. The blades will start moving
in 60 seconds. What do you do?
How much should you charge to wash all the windows in Seattle?
How would you find out if a machine’s stack grows up or down in memory?
Explain a database in three sentences to your eightyearold nephew.
How many times a day does a clock’s hands overlap?
You have to get from point A to point B. You don’t know if you can get there. What would you do?
Imagine you have a closet full of shirts. It’s very hard to
find a shirt. So what can you do to organize your shirts for easy
retrieval?
Every man in a village of 100 married couples has cheated on
his wife. Every wife in the village instantly knows when a man other
than her husband has cheated, but does not know when her own husband
has. The village has a law that does not allow for adultery. Any wife
who can prove that her husband is unfaithful must kill him that very
day. The women of the village would never disobey this law. One day,
the queen of the village visits and announces that at least one husband
has been unfaithful. What happens?
In a country in which people only want boys, every family
continues to have children until they have a boy. if they have a girl,
they have another child. if they have a boy, they stop. what is the
proportion of boys to girls in the country?
If the probability of observing a car in 30 minutes on a
highway is 0.95, what is the probability of observing a car in 10
minutes (assuming constant default probability)?
If you look at a clock and the time is 3:15, what is the
angle between the hour and the minute hands? (The answer to this is not
zero!)
Four people need to cross a rickety rope bridge to get back
to their camp at night. Unfortunately, they only have one flashlight
and it only has enough light left for seventeen minutes. The bridge is
too dangerous to cross without a flashlight, and it’s only strong
enough to support two people at any given time. Each of the campers
walks at a different speed. One can cross the bridge in 1 minute,
another in 2 minutes, the third in 5 minutes, and the slow poke takes
10 minutes to cross. How do the campers make it across in 17 minutes?
You are at a party with a friend and 10 people are present
including you and the friend. your friend makes you a wager that for
every person you find that has the same birthday as you, you get $1;
for every person he finds that does not have the same birthday as you,
he gets $2. would you accept the wager?
How many piano tuners are there in the entire world?
You have eight balls all of the same size. 7 of them weigh
the same, and one of them weighs slightly more. How can you find the
ball that is heavier by using a balance and only two weighings?
You have five pirates, ranked from 5 to 1 in descending
order. The top pirate has the right to propose how 100 gold coins
should be divided among them. But the others get to vote on his plan,
and if fewer than half agree with him, he gets killed. How should he
allocate the gold in order to maximize his share but live to enjoy it?
(Hint: One pirate ends up with 98 percent of the gold.)
Tags: answers 
Posted by
Admin on
8/31/2008 1:18 PM 
Comments (0)
We are providing solutions to the Crazy Questions at Google Job Interview post By Thiomir
How many golf balls can fit in a school bus?
Solution:
The point of the question isn't to see how golf balls you think are in
the bus, but to see what your deduction skills are like. Do you just
make a random guess or try to cop out by saying a lot, or do you
actually try to come up with a legitimate answer by going through a
logical series of steps.
You are shrunk to the
height of a nickel and your mass is proportionally reduced so as to
maintain your original density. You are then thrown into an empty glass
blender. The blades will start moving in 60 seconds. What do you do?
Solution:You
simply jump out. As you are scaled down, the ratio of muscle mass to
total mass remains the same. Potential energy is given by E = mgh. So,
if E/m is unchanged (where E is the energy expended in expanding your
leg muscles, and m is your mass), then h is unchanged. Minime jumps as
high as me. This is the reason why grasshoppers can jump about as high
as people.
How much should you charge to wash all the windows in Seattle?
Solution:As
crazy as it might sound, questions like these demonstrate your ability
to think through a complex problem with little or no information. They
expect you to take an educated guess. Most of the time you can ask them
questions like  how many buildings are there in Seattle.
How would you find out if a machine’s stack grows up or down in memory?
Solution:Instantiate
a local variable. Call another function with a local. Look at the
address of that function and then compare. If the function's local is
higher, the stack grows away from address location 0; if the function's
local is lower, the stack grows towards address location 0.
Explain a database in three sentences to your eightyearold nephew.
Solution:A
database is like a file cabinet. The files, or data, is stored in it
and can be arranged in categories. But unlike an actual file cabinet,
you can do a lot more cool stuff with a database like being able to
make it accessible through the internet.
How many times a day does a clock’s hands overlap?
Solution:The
Hour hand and Minute hand would be meeting exactly 11 times in 12 hours
(Hour hand would have taken 1 clockwise round and Minute hand would
have taken 12 clockwise rounds, so 12  1 = 11 rounds).
result:
First time hour and minute hands overlap will be 12 Hours / 11 =
01:05:27.27. So at this time only hour and minute hands would be
overlapping and second hand will not be any near to them. Similarly for
2nd, 3rd, 4th, 5th, 6th, 7th, 8th, 9th and 10th overlap of hour and
minute hand the Second hand wont be any nearby. So all 3 hands (hour,
minute and Second) overlap only 2 times i.e. (0:0:0 and 12:0:0).
Also we all know when we get our watches repaired, normally the repairman overlaps all the three hands to 12.
If we are considering that the second hand is not present, then the rest two overlaps 22 times in 24 hours.
There again is a catch, if we check the angles by which the hour hand and minute hand moves.
The
second hand moves 6 degree in a second. In that time the minute hand
will move 6/60 degrees. and the hour hand will move 6/(60*12) degrees.
now taking these things in the considerations. if we check the
positions of the hour and minute hand in terms of angle from the marker
12, for our first rendezvous time, i.e. 01:05:27.27 sec.
first thing
that comes to my mind is that, there is fraction in the seconds. So
that time can’t be measured. there will be no exact overlap. now lets
calculate the angles:
1 hour 5 mins and 27 seconds = 3600 + 5*60 + 27 = 3927 seconds.
angle of hour hand = 3927 * 6/(60*12) = 32.725 degree.
angle of minute hand = 3927 * 6/60 = 392.7 degree
subtracting 360 degree from it we get  32.7 degree.
So at 01:05:27 both hands don’t overlap. Now for 01:05:28 :
Angles : hour hand  32.73333
minute hand  32.8
so obviously they dont meet at 01:05:28 either.
So they overlap at 12:00 and 24:00 only. So the answer is 2 only.
You have to get from point A to point B. You don’t know if you can get there. What would you do?
Solution:Utilizing
a “learn as you go” approach and applying collected knowledge and data
along the way is the best way to proceed. Let’s break this down farther.
Determine
the amount of time you have to go from point A to point B. Spend the
initial 20% of that time making a 360° search with the largest
circumference possible with the in the time you have allowed.
During
that time, ask people, look for maps, clues, collect data, and
knowledge. At the end of the initial 360° search take an objective look
at all the information you have obtained and you calculate the risk of
failure you are willing to live with. Create a plan and a strategy
based on your assessment of where you believe point B to be. Then you
proceed on implementing your plan with predetermined intervals of
reassessment and strategy improvements.
This is the best chance you have reaching point B if you don’t know if you can get there.
Imagine
you have a closet full of shirts. It’s very hard to find a shirt. So
what can you do to organize your shirts for easy retrieval?
Solution:Let’s suppose there are
a
set of attributes of each shirt you are interested in: e.g. sleeve
length, color, buttons (no buttons, fully button, partially buttoned
from collar to chest level).
Let’s say the closet is a simple wall
closet with a single closet rod running the entire length of closet. On
the left you put all the short sleeve shirts, and on the right the long
sleeve shorts. You separate then long and short sleeve sides with a
specially marked coat hanger. Then you separate each group into no
buttonoed, partially buttoned, and fully button, using more specially
marked hangers. Then each sub group is separated into colored and
monochrome subsubgroups (specially marked hangers aren’t needed for
separators unless you are color blind) Then each colored group is
sorted left to right according to the color spectrum: ROYGBIV: red,
orange, yellow, green, blue, indigo, violet. Each monochrome ggroup is
sorted left to right: white on the left, black on the right, and shades
of grey in the middle, the darker greys on the right, the lighter on
the left.
Every man in a village of 100 married
couples has cheated on his wife. Every wife in the village instantly
knows when a man other than her husband has cheated, but does not know
when her own husband has. The village has a law that does not allow for
adultery. Any wife who can prove that her husband is unfaithful must
kill him that very day. The women of the village would never disobey
this law. One day, the queen of the village visits and announces that
at least one husband has been unfaithful. What happens?
Solution:1. There is only one cheat husband

If it is so then 99 wives knew it before. So the cheated wife got the
idea from queen that her husband is cheating. So she will kill him.
Next morning every wife will know there is no cheat husbands anymore.
2. There are more than one cheat husbands

In this case, all of the wives already had the idea prior to queen's
information. Its just that the cheated wives knew the count which is
one less than what the noncheated wives' knew  thats all. i.e. if
there were 2 cheat husbands then their wives knew the count is 1 and
others knew its 2. So the queen just repeated the info saying "at least
1". Same goes to 2,3,4...100 cheat husbands. So in this case no wife
kills her husband.
In a country in which people
only want boys, every family continues to have children until they have
a boy. if they have a girl, they have another child. if they have a
boy, they stop. what is the proportion of boys to girls in the country?
Solution:From pure probability,we get the expected number of girls born to be 1/2 with that of boys being 1.So the ratio is 2:1
If
the probability of observing a car in 30 minutes on a highway is 0.95,
what is the probability of observing a car in 10 minutes (assuming
constant default probability)?
Solution:If the
chance to see the car is 10 percent per minute, the first minute you
have 10% chance, the second minute you have 10% of 90% = 9% (so total
19%), the third minute 10% of 81% (= 8,1%, total 27,1 %) ......
As the chance for 30 minutes is 95 percent, the chance for 1 minute is 9.5% and for 10 minute 63.1 %.
If
you look at a clock and the time is 3:15, what is the angle between the
hour and the minute hands? (The answer to this is not zero!)
Solution:7.5
degrees (the hour hand is 1/4th of the way between 3 and 4, the angle
measure of that is 360/12 = 30 degrees between hours / 4 = 7.5 degrees).
Four
people need to cross a rickety rope bridge to get back to their camp at
night. Unfortunately, they only have one flashlight and it only has
enough light left for seventeen minutes. The bridge is too dangerous to
cross without a flashlight, and it�s only strong enough to support two
people at any given time. Each of the campers walks at a different
speed. One can cross the bridge in 1 minute, another in 2 minutes, the
third in 5 minutes, and the slow poke takes 10 minutes to cross. How do
the campers make it across in 17 minutes?
Solution:1
and 2 cross, taking 2 minutes, 1 goes back carrying the flashlight
total=3 minutes. 5 and 10 cross, taking 10 minutes totaltime now= 13
minutes, 2 goes back,total time now = 15 minutes. 1 and 2 cross again,
taking 2 minutes making it 17 minutes.
You are at a
party with a friend and 10 people are present including you and the
friend. your friend makes you a wager that for every person you find
that has the same birthday as you, you get $1; for every person he
finds that does not have the same birthday as you, he gets $2. would
you accept the wager?
Solution:No.
How many piano tuners are there in the entire world?
Solution:1) At first list out all the piano manufacturing companies in the world.
2) Then look into their purchase records and find out the piano purchasers information.
3)
i) If the purchase is made by an individual or a house hold then the
piano is played at best case by all the people of the house.
ii) Else if the piano is purchased for school then list out the students that opted the piano course in their music curriculum.
iii) If the piano is purchased by a Church then count the no of major or minor events of the church and count the piano users.
sum up all the numbers to get more or less accurate piano users count.
You
have eight balls all of the same size. 7 of them weigh the same, and
one of them weighs slightly more. How can you find the ball that is
heavier by using a balance and only two weighings?
Solution:choose 6 balls and weigh 3 against 3
 if they weigh the same, you have another weighing for the remaining 2 balls and you can find the heavier one
 if they don’t weigh the same, from the group of 3 which was heavier, choose any 2 balls and weigh them:

if they weigh the same, the remaining ball is the heavier one;
otherwise you just found the heavier one by weighing the 2 chosen balls.
You
have five pirates, ranked from 5 to 1 in descending order. The top
pirate has the right to propose how 100 gold coins should be divided
among them. But the others get to vote on his plan, and if fewer than
half agree with him, he gets killed. How should he allocate the gold in
order to maximize his share but live to enjoy it? (Hint: One pirate
ends up with 98 percent of the gold.)
Solution:The highest ranked pirate gets 98 gold coins
Two pirates get 1 gold coin each
The other 2 pirates get nothing.
Total there are five Technical Interviews followed by Management round.
So here are the questions.
Google Interview Round 1:
What is the Space complexity of quick sort algorithm? how do find it?
Solution: Quicksort has a space complexity of O(logn), even in the worst case, when it is carefully implemented such that
* inplace partitioning is used. This requires O(1).
* After partitioning, the partition with the fewest elements is
(recursively) sorted first, requiring at most O(logn) space. Then the
other partition is sorted using tailrecursion or iteration.
The
version of quicksort with inplace partitioning uses only constant
additional space before making any recursive call. However, if it has
made O(logn) nested recursive calls, it needs to store a constant
amount of information from each of them. Since the best case makes at
most O(logn) nested recursive calls, it uses O(logn) space. The worst
case makes O(n) nested recursive calls, and so needs O(n) space.
However,
if we consider sorting arbitrarily large lists, we have to keep in mind
that our variables like left and right can no longer be considered to
occupy constant space; it takes O(logn) bits to index into a list of n
items. Because we have variables like this in every stack frame, in
reality quicksort requires O(log2n) bits of space in the best and
average case and O(nlogn) space in the worst case. This isn't too
terrible, though, since if the list contains mostly distinct elements,
the list itself will also occupy O(nlogn) bits of space.
What are dangling pointers?
Solution:
A dangling pointer is a pointer to storage that is no longer allocated.
Dangling pointers are nasty bugs because they seldom crash the program
until long after they have been created, which makes them hard to find.
Programs that create dangling pointers often appear to work on small
inputs, but are likely to fail on large or complex inputs.
Given that you can take one step or two steps forward from a given step. So find the total number of ways of reaching Nth step.
Solution:The simple recurrence relation governing this problem is f(N)=f(N1) +f(N2)(why?),which is a fibonacci sequence.
Nth
state can be arrived directly by taking 2 step movement from N2 or 1
step from N1.Remember N2 > N1 > N is not a direct path from
N2th state to Nth state.Hence the no of solutions is no of ways to
reach N2th step and then directly taking a 2 jump step to N + no of
ways to reach N1th step and then taking 1 step advance.
You are given biased coin. Find unbiased decision out of it?
Solution:Throw
the biased coin twice.Classify it as true for HT and false for TH.Both
of these occur with probability=p*(1p),hence unbiased. Ignore the
other 2 events namely HH and TT.
On a empty
chessboard, a horse starts from a point( say location x,y) and it
starts moving randomly, but once it moves out of board, it cant come
inside. So what is the total probability that it stays within the board
after N steps
Google Interview Round 2:
You
have 1 to N1 array and 1 to N numbers, and one number is missing, you
need to find the missing the number. Now you have 1 to N2 numbers, and
two numbers missing. Find them.
Solution:
The
question can be elucidated as follows.Given an array of size N1
containing numbers less than N and with out any duplicates!! We knew
that there is a number missing from the array say K .Let S be the sum
of the elements of the array.
Sum of first N natural numbers=N*(N+1)/2 and S=N*(N+1)/2  K.Now putting this other way around we get K=N*(N+1)/2 S !! Now the second part of the question says that there are 2 of the first N numbers missing.Let they be X and Y.
We solve this problem by solving 2 essential equations.
They are X+Y=N*(N+1)/2 S>(1)
X*Y=N!/P(2) where S and P are the cumulative sum and product of the array entries.
You have cycle in linked list. Find it. Prove that time complexity is linear. Also find the node at which looping takes place.
Solution:
The
problem of checking whether there is a cycle or not can be solved using
2 pointers one moving in increments of 1 and the other in increments of
2.If there is a cycle then these 2 pointers meet at some node say N1
inside the cycle otherwise the fast pointer reaches the end of the
list.This is a O(N) solution.
Now coming to the identification
of the node at which looping took place.After our identification of
cycle ,both the pointers P1 and P2 are at node N1.Now iterate the slow
pointer to count the no of nodes in the cycle.(After traversing the
whole cycle P1 and P2 shall again be at the same node).Let this size be
K.Now take one of the pointers to the head node and count the no of
nodes till N1.Let this number be X.Now use one of these pointers to
reverse the cycle starting from N1.Only the cycle gets reversed.Now
again traverse from head node to N1.Let the number of nodes this time
be Y.Let the no of nodes from head to the start node of the cycle be Z
Now
X+Y=2*Z+K .Hence solve for K and then having figured out the start node
N2 of the cycle.Now as the cycle is reversed having figured out this
start node its next node is the looping nodes so set the looping nodes
next pointer to NULL and reverse the list further till you reach N2.
Questions on my project please be prepare well about your project
How do you search for a word in a large database.
How
do you build address bar in say gmail. i.e. if you press 'r' then you
get all email starting from 'r', and if you press 'ra' then you will
get emails starting from 'ra'.
Google Interview Round 3:
You have given an array. Find the maximum and minimum numbers in less number of comparisons.
Solution:
only
3n/2 comparisons are necessary to find both the minimum and the
maximum. To do this, we maintain the minimum and maximum elements seen
thus far. Rather than processing each element of the input by comparing
it against the current minimum and maximum, however, at a cost of two
comparisons per element, we process elements in pairs. We compare pairs
of elements from the input first with each other, and then compare the
smaller to the current minimum and the larger to the current maximum,
at a cost of three comparisons for every two elements.
You
have given an array from 1 to N and numbers also from 1 to N. But more
than one number is missing and some numbers have repeated more than
once. Find the algo with running time O(n).
Solution:All
the numbers are positive to start with.Now, For each A[i], Check the
sign of A[A[i]]. Make A[A[i]] negative if it's positive. Report a
repetition if it's negative.Finally all those entries i,for which A[i]
is negative are present and those i for which A[i] is positive are
absent.
Google Interview Round 4 :
Three strings say A,B,C are given to you. Check weather 3rd string is interleaved from string A and B.
Ex: A="abcd" B="xyz" C="axybczd". answer is yes.
Solution:
bool test(A,B,C)
{
i=j=k=0;
while(k < C.size())
{
if(i < A.size() && C[k]==A[i])
{i++,k++;
}
else if(j < B.size() && C[k]==B[j])
{
j++,k++;
}
else
return false
}
return (i == A.size() && j == B.size());
}
The
above algorithm doesn't work when C[k]=A[i]=B[j], essentially throwing
one in to a dilemma whether to accept the character from A or B.
Given two sorted arrays A and B.
Find the intersection of these arrays A and B.
Solution:The intersection can be found by using a variation of merge routine of the merge sort.
If array A is small and array B is too large. how will you proceed for getting intersection of those two arrays?
Solution:In this case for each entry of smaller array,we can run a binary search routine on the larger one to know its presence.
Google Interview Round 5:
If you get into Google, which products are you going to work on?
What is TCP, UDP. what is reliability, unreliability, give examples of these?
Solution:
Click Here To Read About TCP
Click Here To Read About UDP
Click Here To Read About Reliability
What is http protocol?
Solution:
Click Here To Read About HTTP
How does Google search engine works?
What is indexing, what is the input and output to it. how Google does that?
This was the interview i got from one of my friends.
Tags: answers 
Posted by
Admin on
8/31/2008 9:01 AM 
Comments (2)
The Google Interview has some strange questions on it. Here are my answers:
1. How many golf balls can fit in a school bus?
1 trillion
(then I draw a Dr. Evil Picture)
2. You are shrunk to the height of a nickel and your mass is
proportionally reduced so as to maintain your original density. You are
then thrown into an empty glass blender. The blades will start moving
in 60 seconds. What do you do?
Plead to be taken back out.
3. How much should you charge to wash all the windows in Seattle?
As much as possible.
4. How would you find out if a machine’s stack grows up or down in memory?
Ask someone.
5. Explain a database in three sentences to your eightyearold nephew.
Hey. Kid. Google it.
6. How many times a day does a clock’s hands overlap?
24
7. You have to get from point A to point B. You don’t know if you can get there. What would you do?
Try.
8. Imagine you have a closet full of shirts. It’s very hard to
find a shirt. So what can you do to organize your shirts for easy
retrieval?
Tell my wife or a maid to do it.
9. Every man in a village of 100 married couples has cheated on
his wife. Every wife in the village instantly knows when a man other
than her husband has cheated, but does not know when her own husband
has. The village has a law that does not allow for adultery. Any wife
who can prove that her husband is unfaithful must kill him that very
day. The women of the village would never disobey this law. One day,
the queen of the village visits and announces that at least one husband
has been unfaithful. What happens?
They kill the queen  she’s the messenger (they always kill the messenger).
10. In a country in which people only want boys, every family
continues to have children until they have a boy. if they have a girl,
they have another child. if they have a boy, they stop. what is the
proportion of boys to girls in the country?
~1:1
11. If the probability of observing a car in 30 minutes on a
highway is 0.95, what is the probability of observing a car in 10
minutes (assuming constant default probability)?
About 63% via .95 =(n+n*(1n))+n(1(n+n*(1n)))
(actually, I think it has to do with logs and that’s slightly off).
12. If you look at a clock and the time is 3:15, what is the
angle between the hour and the minute hands? (The answer to this is not
zero!)
360/12/4 degrees.
13. Four people need to cross a rickety rope bridge to get back
to their camp at night. Unfortunately, they only have one flashlight
and it only has enough light left for seventeen minutes. The bridge is
too dangerous to cross without a flashlight, and it’s only strong
enough to support two people at any given time. Each of the campers
walks at a different speed. One can cross the bridge in 1 minute,
another in 2 minutes, the third in 5 minutes, and the slow poke takes
10 minutes to cross. How do the campers make it across in 17 minutes?
1 goes with 2 = 2 mins
1 returns with the flashlight = 1 min
5 goes with 10 = 10 mins
2 returns = 2 mins
1 + 2 go = 2 mins
but really, how the fuck would they know the flashlight has 17 minutes left on it?
14. You are at a party with a friend and 10 people are present
including you and the friend. your friend makes you a wager that for
every person you find that has the same birthday as you, you get $1;
for every person he finds that does not have the same birthday as you,
he gets $2. would you accept the wager?
Maybe . . . but only if i was really shitfaced.
15. How many piano tuners are there in the entire world?
What do you mean, an African or European Swallow?
16. You have eight balls all of the same size. 7 of them weigh
the same, and one of them weighs slightly more. How can you find the
ball that is heavier by using a balance and only two weighings?
weigh balls 1, 2, 3 (set 1) against 4 against 4 and 5 and 6 (set 2)
 if not equal, take the heavier set and weigh 1 v 2 (or 4 v 5 if set 2 was heavier)
 if not equal the heavier ball is the it
 if equal it is the odd ball is heaviest.
 if set 1 and 2 are equal weight 7 v 8 and the heavier is the heaviest.
17. You have five pirates, ranked from 5 to 1 in descending
order. The top pirate has the right to propose how 100 gold coins
should be divided among them. But the others get to vote on his plan,
and if fewer than half agree with him, he gets killed. How should he
allocate the gold in order to maximize his share but live to enjoy it?
(Hint: One pirate ends up with 98 percent of the gold.)
Wrong shitbag. You tell a pirate he’s gonna get 1 gold piece out of
100 and he’s gonna vote to kill you. You can reason with him all you
want, but he’s gonna vote to fucking kill you. It’s not game theory,
it’s human emotions and common sense.
20/20/20/20/20 or something close to it.
Hint: They’re fucking Pirates, not Game theory doctorates. If anyone get’s fucked they’re gonna vote to kill the others.
I’d vote to kill you if you if you gave me only 1 piece.
ARRRRRRGGGGG!
Tags: answers 
Posted by
Admin on
8/31/2008 8:58 AM 
Comments (0)
Some time back I
interviewed with Google, and a number of other well known software
development companies. I've written up a number of questions very
similar to the ones I was asked, changing them enough so that I'm not
breaking my NDA.
Q: Why are manhole covers round?
Q: A man pushed his car to a hotel and lost his fortune. What happened?
Q: Explain the significance of "dead beef".
Q: Write a C program which measures the the speed of a context switch on a UNIX/Linux system.
Q:
Given a function which produces a random integer in the range 1 to 5,
write a function which produces a random integer in the range 1 to 7.
Q: Describe the algorithm for a depthfirst graph traversal.
Q: Design a class library for writing card games.
Q:
You need to check that your friend, Bob, has your correct phone number,
but you cannot ask him directly. You must write a the question on a
card which and give it to Eve who will take the card to Bob and return
the answer to you. What must you write on the card, besides the
question, to ensure Bob can encode the message so that Eve cannot read
your phone number?
Q: How are cookies passed in the HTTP protocol?
Q: What is the size of the C structure below on a 32bit system? On a 64bit?
struct foo {
char a;
char* b;
};
Q: Design the SQL database tables for a car rental database.
Q: Write a regular expression which matches a email address.
Q:
Write a function f(a, b) which takes two character string arguments and
returns a string containing only the characters found in both strings
in the order of a. Write a version which is order Nsquared and one
which is order N.
Q: You are given a the source to
a application which is crashing when run. After running it 10 times in
a debugger, you find it never crashes in the same place. The
application is single threaded, and uses only the C standard library.
What programming errors could be causing this crash? How would you test
each one?
Q: Explain how congestion control works in the TCP protocol.
Here's one that someone sent me in email. I've outlined a possible solution, but I haven't
thought through the problem very well. Here's the question:
Design and describe a system/application that will most efficiently produce a report of the top 1
million Google search requests. You are given:
You are given 12 servers to work with. They are all
dualprocessor machines with 4Gb of RAM, 4x400GB hard drives and
networked together.(Basically, nothing more than highend PC's)
The
log data has already been cleaned for you. It consists of 100 Billion
log lines, broken down into 12 320 GB files of 40byte search terms per
line.
You can use only custom written applications or available free opensource software.
There are approx. 8 billion search terms per log file (320 GIG / 40
Bytes). Each computer can return it's top 1 million search terms to a
central server at a cost of 48MB each because 40 Bytes * 1 million =
40MB, plus a 8 byte unsigned integer occurrence count for each search
term.
The combined top 1 million results from each log take only 520 MB, so
there is plenty of space on any single computer to merge the 12
million entries together and come up with top 1 million.
So, the only missing part at this point is how to efficiently count
the search term occurrences on each computer, and return the top 1
million (this same algorithm can be used for merging the 12 top 1
million, too). A hash table may be a bad idea.
With this many search terms and
only 4GIG of memory, hashing the search terms would cause a lot of collisions.
You want
to use a tree, not a hash. Order ln(n) should work well for the search
term lookups (if it's good enough for the STL maps, it's good enough for me, right??!!).
Now, we know that we need to produce the top 1 million results,
but there are potentially 8 Billion unique search terms per log, and a
minimum of 1 unique search term per log (what are the chances you get 8
billion searches for 'porn' or 'sex' on a single log? Not much, but
it is a formal possibility. At the very least, such a case would make
a great unit test for your program), either way, you could blow a 32
bit unsigned int trying to count them... So, we do have to use
unsigned longs. That increases the size of the search term count to a
longint, 8 bytes instead of 4. With 4 gigs of memory, how many log
entries can be counted at a time? 1 unique term will take 40 bytes, +
8 bytes for the count, two pointers for the left/right nodes of the
binary tree (+ 8 bytes or + 16 bytes on a 64 bit system). Let's only
assume you can use 3.5GIG of the 4GIG of memory, so that's 3.5/64 =
0.0546 GIG, or about 54 million. So, here's the stratagy:
1) go through the log, and count the occurances of search terms found
using a binary tree for search term lookups, and a longint for the
counter. Do this unil you have 54 million unique terms in your tree.
Write a marker into the log file for each search term used so that
further passes know it has been counted.
2) transmit the tree over the network to the next computer and count
only the search term occurances which are already in the tree, marking
any counted in the logs as such; then transmit the tree to the next
and repeat this process until the tree has passed through each
computer and ends up at the computer WHERE THE FIRST UNQIUE SEARCH
TERM WAS ADDED TO THE TREE(more on this in the next step). Heapsort
the tree by search term occurance number (why not, it's already in a
binary tree  that's great for heapsort!). Truncate the tree to 1
million search terms, and write it to disk.
3) Every time a tree of unique search terms has "filled up", that is,
the tree contains 54 million unique search terms, a new uniquesearch
term tree must be built and sent to each computer so that the terms
can be counted. A tree might begin near the end of a log on one
computer, and be sent to the next computer with less than the 54
million unique search terms. When this is the case, the tree will
continue to collect unique search terms from the log on the next
computer.
There are two processess occuring in this algorithm which travel in
rings around the computer network until they reach the computer at
which they began. The first process travels from computer to computer
generating these unqiue search term trees (call this process #1).
Once a tree fills up with unique terms, it breaks off from this
process and is sent around the ring to count the search term
occurances for terms which it already contains (call these processes
Tn, there can be many). Once process #1 reaches the computer where it
started, it quits. Once all the Tn processes have traveled the ring,
they quit also after writing their top 1 million search results to
disk in sorted order. The search terms in these files are all unique
and accurately counted. Just start popping search terms off the top
of these logs by the highest occurance count until you have 1 million
search terms. That should be it.
1. Reverse a singly linked list
//
// iterative version
//
Node* ReverseList( Node ** List )
{
Node *temp1 = *List;
Node * temp2 = NULL;
Node * temp3 = NULL;
while ( temp1 )
{
*List = temp1; //set the head to last node
temp2= temp1>pNext; // save the next ptr in temp2
temp1>pNext = temp3; // change next to privous
temp3 = temp1;
temp1 = temp2;
}
return *List;
}
2. Delete a node in double linked list
void deleteNode(node *n)
{
node *np = n>prev;
node *nn = n>next;
np>next = n>next;
nn>prev = n>prev;
delete n;
}
3. Sort a linked list
//sorting in descending order
struct node
{
int value;
node* NEXT;
}
//Assume HEAD pointer denotes the first element in the //linked list
// only change the values…don’t have to change the //pointers
Sort( Node *Head)
{
node* first,second,temp;
first= Head;
while(first!=null)
{
second=first>NEXT;
while(second!=null)
{
if(first>value < second>value)
{
temp = new node();
temp>value=first>value;
first>value=second>value;
second>value=temp>value;
delete temp;
}
second=second>NEXT;
}
first=first>NEXT;
}
}
4. Reverse a string
void ReverseString (char *String)
{
char *Begin = String;
char *End = String + strlen(String)  1;
char TempChar = '\0';
while (Begin < End)
{
TempChar = *Begin;
*Begin = *End;
*End = TempChar;
Begin++;
End;
}
}
5. Insert a node a sorted linked list
void sortedInsert(Node * head, Node* newNode)
{
Node *current = head;
// traverse the list until you find item bigger the // new node value
//
while (current!= NULL && current>data < newNode>data)
{
current = current>next);
}
//
// insert the new node before the big item
//
newNode>next = current>next;
current = newNode;
}
6. Covert a string to upper case
void ToUpper(char * S)
{
while (*S!=0)
{
*S=(*S >= 'a' && *S <= 'z')?(*S'a'+'A'):*S;
S++;
}
}
7. Multiple a number by 7 without using * and + operator.
NewNum = Num << 3; // mulitplied by 2 ^ 3 = 8
NewNum = NewNum  Num; // 8 – 1 = 7
8.
Write a function that takes in a string parameter and checks to see
whether or not it is an integer, and if it is then return the integer
value.
#include
int strtoint(char *s)
{
int index = 0, flag = 0;
while( *(s+index) != '\0')
{
if( (*(s + index) >= '0') &&
*(s + index) <= '9')
{
flag = 1;
index++;
}
else
{
flag = 0;
break;
}
}
if( flag == 1 )
return atoi(s);
else
return 0;
}
main()
{
printf("%d",strtoint("0123"));
printf("\n%d",strtoint("0123ii"));
}
9. Print a data from a binary tree – Inorder(ascending)
//
// recursive version
//
Void PrintTree ( struct * node node )
{
if ( node == NULL )
return;
PrintTree(node>left );
Printf(“%d”, node>data);
PrintTree(node>right );
}
10. print integer using only putchar
//
// recursive version
//
void PrintNum ( int Num )
{
if ( Num == 0 )
return;
PrintNum ( Num / 10 );
Puthcar ( ‘0’+ Num % 10 );
}
11. Find the factorial of number
//
// recursive version
//
int Factorial( int Num )
{
If ( num > 0 )
return Num * Factorial ( Num –1 );
else
return 1;
}
//
// iterative version
//
int Factorial( int Num )
{
int I
int result = 1;
for ( I= Num; I > 0; I )
{
result = result * I;
}
return result;
}
12. Generate Fib numbers:
int fib( n ) // recursive version
{
if ( n < 2 )
return 1;
else
return fib ( n –1 ) + fib ( n –2 );
}
int fib( n ) //iterative version
{
int f1 =1, f2 = 1;
if ( n < 2 )
return 1;
for ( i = 1; i < N; i++)
{
f = f1 + f2;
f1= f2;
f = f1;
}
return f;
}
13. Write a function that finds the last instance of a character in a string
char *lastchar(char *String, char ch)
{
char *pStr = NULL;
// traverse the entire string
while( * String ++ != NULL )
{
if( *String == ch )
pStr = String;
}
return pStr;
}
14. Return Nth the node from the end of the linked list in one pass.
Node * GetNthNode ( Node* Head , int NthNode )
{
Node * pNthNode = NULL;
Node * pTempNode = NULL;
int nCurrentElement = 0;
for ( pTempNode = Head; pTempNode != NULL; pTempNode = pTempNode>pNext )
{
nCurrentElement++;
if ( nCurrentElement  NthNode == 0 )
{
pNthNode = Head;
}
else
if ( nCurrentElement  NthNode > 0)
{
pNthNode = pNthNode >pNext;
}
}
if (pNthNode )
{
return pNthNode;
}
else
return NULL;
}
15. Counting set bits in a number.
First version:
int CoutSetBits(int Num)
{
for(int count=0; Num; Num >>= 1)
{
if (Num & 1)
count++;
}
return count;
}
Optimized version:
int CoutSetBits(int Num)
{
for(int count =0; Num; count++)
{
Num &= Num 1;
}
}
Last time I was interviewed for a software development engineer position, the recruiter asked me some of the classical Microsoft interview questions, such as “How Would You Move Mount Fuji?” or “How many gas station are there in your country?“.
It was the first time for me to be asked such questions but having obtained the job I think my answers were good enough.
After that day, I looked for other wellknown interview questions
and I discovered that Google has a totally different approach, focusing
on algorithms, data structures and complexity.
For instance, one of Google interview questions says:
There is an array A[N] of N integers. You have to
compose an array Output[N+1] such that Output[i] will be equal to the
product of all the elements of A[] except A[i].
Example:
INPUT:[4, 3, 2, 1, 2]
OUTPUT:[12, 16, 24, 48, 24]
Solve it without division operator and in O(n).
Without the two constraints at the end of the puzzle it would have been straightforward, but now we have to be smart.
Actually, the product of all elements of A[] except A[i] is equal to the product of all elements before A[i] and those after A[i].
We can traverse A[] twice, once from left to right and once in the opposite way and multiply all the elements we find before A[i].
We’ll pretend to have a new array called Output[] to store the output of the first pass, assigning Output[i] the product of all elements preceding A[i]:
let rec firstpass product input =
match input with
 [] > []
 x::xs > product :: firstpass (product * x) xs
let rec firstpass product input =
match input with
 [] > []
 x::xs > product :: firstpass (product * x) xs
For the second pass we need to move from right to left, but this can be done by reversing the input arrays and moving as usual:
let secondpass product input arr =
let rev_input = List.rev input
let rev_arr = List.rev arr
let rec rev_secondpass product (input:list<int>) arr =
match arr with
 [] > []
 x::xs > rev_secondpass (product * input.Head) input.Tail xs @ [(x * product)]
rev_secondpass product rev_input rev_arr
let secondpass product input arr =
let rev_input = List.rev input
let rev_arr = List.rev arr
let rec rev_secondpass product (input:list<int>) arr =
match arr with
 [] > []
 x::xs > rev_secondpass (product * input.Head) input.Tail xs @ [(x * product)]
rev_secondpass product rev_input rev_arr
Both firstpass and secondpass expect an integer argument called product, which will be always be 1 at the beginning and will be used to store the intermediate products during the recursive calls.
With these functions we can just define an input array and apply them to get the result.
The following is the complete F# code:
let input = [ 4; 3; 2; 1; 2 ]
let answer values =
let rec firstpass product input =
match input with
 [] > []
 x::xs > product :: firstpass (product * x) xs
let secondpass product input arr =
let rev_input = List.rev input
let rev_arr = List.rev arr
let rec rev_secondpass product (input:list<int>) arr =
match arr with
 [] > []
 x::xs > rev_secondpass (product * input.Head) input.Tail xs @ [(x * product)]
rev_secondpass product rev_input rev_arr
values > firstpass 1 > secondpass 1 values
Original story
I've been meaning to write up some tips on interviewing at Google for a
good long time now. I keep putting it off, though, because it's going
to make you mad. Probably. For some statistical definition of "you",
it's very likely to upset you.
Why? Because... well, here, I wrote a little ditty about it:
Hey man, I don't know that stuff
Stevey's talking aboooooout
If my boss thinks it's important
I'm gonna get fiiiiiiiiiired
Oooh yeah baaaby baaaaybeeeeee....
I
didn't realize this was such a typical reaction back when I first
started writing about interviewing, way back at other companies.
Boyohowdy did I find out in a hurry.
See, it goes like this:
Me: blah blah blah, I like asking question X in interviews, blah blah blah...
You: Question X? Oh man, I haven't heard about X since college! I've never needed it for my job! He asks that in interviews?
But that means someone out there thinks it's important to know, and,
and... I don't know it! If they detect my ignorance, not only will I be
summarily fired for incompetence without so much as a thankyou, I will
also be unemployable by people who ask question X! If people listen to
Stevey, that will be everyone! I will become homeless and destitute!
For not knowing something I've never needed before! This is horrible! I
would attack X itself, except that I do not want to pick up a book and
figure enough out about it to discredit it. Clearly I must yell a lot
about how stupid Stevey is so that nobody will listen to him!
Me: So in conclusion, blah blah... huh? Did you say "fired"? "Destitute?" What are you talking about?
You: Aaaaaaauuuggh!!! *stab* *stab* *stab*
Me: That's it. I'm never talking about interviewing again.
It doesn't matter what X is, either. It's arbitrary. I could say: "I really enjoy asking the candidate (their name)
in interviews", and people would still freak out, on account of
insecurity about either interviewing in general or their knowledge of
their own name, hopefully the former.
But THEN, time passes, and
interview candidates come and go, and we always wind up saying: "Gosh,
we sure wish that obviously smart person had prepared a little better
for his or her interviews. Is there any way we can help future
candidates out with some tips?"
And then nobody actually does anything, because we're all afraid of getting stabbed violently by People Who Don't Know X.
I
considered giving out a set of tips in which I actually use variable
names like X, rather than real subjects, but decided that in the
resultant vacuum, everyone would get upset. Otherwise that approach seemed pretty good, as long as I published under a pseudonym.
In
the end, people really need the tips, regardless of how many feelings
get hurt along the way. So rather than skirt around the issues, I'm
going to give you a few mandatory substitutions for X along with a fair
amount of general interviewprep information.
Caveats and Disclaimers
This
blog is not endorsed by Google. Google doesn't know I'm publishing
these tips. It's just between you and me, OK? Don't tell them I prepped
you. Just go kick ass on your interviews and we'll be square.
I'm only talking about general software engineering positions, and interviews for those positions.
These
tips are actually generic; there's nothing specific to Google vs. any
other software company. I could have been writing these tips about my
first software job 20 years ago. That implies that these tips are also
timeless, at least for the span of our careers.
These tips
obviously won't get you a job on their own. My hope is that by
following them you will perform your very best during the interviews.
Oh, and um, why Google?
Oho! Why Google, you ask? Well let's just have that dialog right up front, shall we?
You: Should I work at Google? Is it all they say it is, and more? Will I be serenely happy there? Should I apply immediately?
Me: Yes.
You: To which ques... wait, what do you mean by "Yes?" I didn't even say who I am!
Me: Dude, the answer is Yes. (You may be a woman, but I'm still calling you Dude.)
You:
But... but... I am paralyzed by inertia! And I feel a certain comfort
level at my current company, or at least I have become relatively
inured to the discomfort. I know people here and nobody at Google! I
would have to learn Google's build system and technology and stuff! I
have no credibility, no reputation there – I would have to start over
virtually from scratch! I waited too long, there's no upside! I'm
afraaaaaaid!
Me: DUDE. The answer is Yes already, OK? It's an invariant. Everyone else who came to Google was in the exact same position
as you are, modulo a handful of famous people with beards that put
Gandalf's to shame, but they're a very tiny minority. Everyone who
applied had the same reasons for not applying as you do. And everyone here says: "GOSH, I SURE AM HAPPY I CAME HERE!" So just apply already. But prep first.
You:
But what if I get a mistrial? I might be smart and qualified, but for
some random reason I may do poorly in the interviews and not get an
offer! That would be a huge blow to my ego! I would rather pass up the
opportunity altogether than have a chance of failure!
Me:
Yeah, that's at least partly true. Heck, I kinda didn't make it in on
my first attempt, but I begged like a street dog until they gave me a
second round of interviews. I caught them in a weak moment. And the
second time around, I prepared, and did much better.
The thing
is, Google has a wellknown false negative rate, which means we
sometimes turn away qualified people, because that's considered better
than sometimes hiring unqualified people. This is actually an
industrywide thing, but the dial gets turned differently at different
companies. At Google the falsenegative rate is pretty high. I don't
know what it is, but I do know a lot of smart, qualified people who've
not made it through our interviews. It's a bummer.
But the really important takeaway is this: if you don't get an offer, you may still be qualified to work here. So it needn't be a blow to your ego at all!
As
far as anyone I know can tell, false negatives are completely random,
and are unrelated to your skills or qualifications. They can happen
from a variety of factors, including but not limited to:
you're having an off day
one or more of your interviewers is having an off day
there were communication issues invisible to you and/or one or more of the interviewers
you got unlucky and got an Interview AntiLoop
Oh no, not the Interview AntiLoop!
Yes, I'm afraid you have to worry about this.
What
is it, you ask? Well, back when I was at Amazon, we did (and they
undoubtedly still do) a LOT of soulsearching about this exact problem.
We eventually concluded that every single employee E at Amazon has at
least one "Interview AntiLoop": a set of other employees S who would
not hire E. The root cause is important for you to understand when
you're going into interviews, so I'll tell you a little about what I've
found over the years.
First, you can't tell interviewers what's
important. Not at any company. Not unless they're specifically asking
you for advice. You have a very narrow window of perhaps one year after
an engineer graduates from college to inculcate them in the art of
interviewing, after which the window closes and they believe they are a
"good interviewer" and they don't need to change their questions, their
question styles, their interviewing style, or their feedback style, ever again.
It's a problem. But I've had my hand bitten enough times that I just don't try anymore.
Second
problem: every "experienced" interviewer has a set of pet subjects and
possibly specific questions that he or she feels is an accurate gauge
of a candidate's abilities. The question sets for any two interviewers
can be widely different and even entirely nonoverlapping.
A
classic example found everywhere is: Interviewer A always asks about
C++ trivia, filesystems, network protocols and discrete math.
Interviewer B always asks about Java trivia, design patterns, unit
testing, web frameworks, and software project management. For any given
candidate with both A and B on the interview loop, A and B are likely
to give very different votes. A and B would probably not even hire each
other, given a chance, but they both happened to go through interviewer
C, who asked them both about data structures, unix utilities, and
processes versus threads, and A and B both happened to squeak by.
That's
almost always what happens when you get an offer from a tech company.
You just happened to squeak by. Because of the inherently flawed nature
of the interviewing process, it's highly likely that someone
on the loop will be unimpressed with you, even if you are Alan Turing.
Especially if you're Alan Turing, in fact, since it means you obviously
don't know C++.
The bottom line is, if you go to an interview at any
software company, you should plan for the contingency that you might
get genuinely unlucky, and wind up with one or more people from your
Interview AntiLoop on your interview loop. If this happens, you will
struggle, then be told that you were not a fit at this time, and then
you will feel bad. Just as long as you don't feel metabad, everything
is OK. You should feel good that you feel bad after this happens, because hey, it means you're human.
And
then you should wait 612 months and reapply. That's pretty much the
best solution we (or anyone else I know of) could come up with for the
falsenegative problem. We wipe the slate clean and start over again.
There are lots of people here who got in on their second or third
attempt, and they're kicking butt.
You can too.
OK, I feel better about potentially not getting hired
Good! So let's get on to those tips, then.
If you've been following along very
closely, you'll have realized that I'm interviewer D. Meaning that my
personal set of pet questions and topics is just my own, and it's no
better or worse than anyone else's. So I can't tell you what it is, no
matter how much I'd like to, because I'll offend interviewers A through
X who have slightly different working sets.
Instead, I want to
prep you for some general topics that I believe are shared by the
majority of tech interviewers at Googlelike companies. Roughly
speaking, this means the company builds a lot of their own software and
does a lot of distributed computing. There are other techcompany
footprints, the opposite end of the spectrum being companies that
outsource everything to consultants and try to use as much thirdparty
software as possible. My tips will be useful only to the extent that
the company resembles Google.
So you might as well make it Google, eh?
First, let's talk about nontechnical prep.
The WarmUp
Nobody
goes into a boxing match cold. Lesson: you should bring your boxing
gloves to the interview. No, wait, sorry, I mean: warm up beforehand!
How do you warm up? Basically there is shortterm and longterm warming up, and you should do both.
Longterm
warming up means: study and practice for a week or two before the
interview. You want your mind to be in the general "mode" of problem
solving on whiteboards. If you can do it on a whiteboard, every other
medium (laptop, shared network document, whatever) is a cakewalk. So
plan for the whiteboard.
Shortterm warming up means: get lots
of rest the night before, and then do intense, fastpaced warmups the
morning of the interview.
The two best longterm warmups I know of are:
1) Study a datastructures and algorithms book.
Why? Because it is the most likely to help you beef up on problem
identification. Many interviewers are happy when you understand the
broad class of question they're asking without explanation. For
instance, if they ask you about coloring U.S. states in different
colors, you get major bonus points if you recognize it as a
graphcoloring problem, even if you don't actually remember exactly how
graphcoloring works.
And if you do remember how it works, then
you can probably whip through the answer pretty quickly. So your best
bet, interviewprep wise, is to practice the art of recognizing that
certain problem classes are best solved with certain algorithms and
data structures.
My absolute favorite for this kind of interview preparation is Steven Skiena's The Algorithm Design Manual.
More than any other book it helped me understand just how astonishingly
commonplace (and important) graph problems are – they should be part of
every working programmer's toolkit. The book also covers basic data
structures and sorting algorithms, which is a nice bonus. But the gold
mine is the second half of the book, which is a sort of encyclopedia of
1pagers on zillions of useful problems and various ways to solve them,
without too much detail. Almost every 1pager has a simple picture,
making it easy to remember. This is a great way to learn how to
identify hundreds of problem types.
Other interviewers I know recommend Introduction to Algorithms.
It's a true classic and an invaluable resource, but it will probably
take you more than 2 weeks to get through it. But if you want to come
into your interviews prepped, then consider deferring your application until you've made your way through that book.
2) Have a friend interview you.
The friend should ask you a random interview question, and you should
go write it on the board. You should keep going until it is complete,
no matter how tired or lazy you feel. Do this as much as you can
possibly tolerate.
I didn't do these two types of preparation
before my first Google interview, and I was absolutely shocked at how
bad at whiteboard coding I had become since I had last interviewed
seven years prior. It's hard! And I also had forgotten a bunch of
algorithms and data structures that I used to know, or at least had
heard of.
Going through these exercises for a week prepped me
mightily for my second round of Google interviews, and I did way, way
better. It made all the difference.
As for shortterm
preparation, all you can really do is make sure you are as alert and
warmed up as possible. Don't go in cold. Solve a few problems and read
through your study books. Drink some coffee: it actually helps you
think faster, believe it or not. Make sure you spend at least
an hour practicing immediately before you walk into the interview.
Treat it like a sports game or a music recital, or heck, an exam: if
you go in warmed up you'll give your best performance.
Mental Prep
So!
You're a hotshot programmer with a long list of accomplishments. Time
to forget about all that and focus on interview survival.
You should go in humble, openminded, and focused.
If
you come across as arrogant, then people will question whether they
want to work with you. The best way to appear arrogant is to question
the validity of the interviewer's question – it really ticks them off,
as I pointed out earlier on. Remember how I said you can't tell an
interviewer how to interview? Well, that's especially true if you're a candidate.
So
don't ask: "gosh, are algorithms really all that important? do you ever
need to do that kind of thing in real life? I've never had to do that
kind of stuff." You'll just get rejected, so don't say that kind of
thing. Treat every question as legitimate, even if you are frustrated
that you don't know the answer.
Feel free to ask for help or
hints if you're stuck. Some interviewers take points off for that, but
occasionally it will get you past some hurdle and give you a good
performance on what would have otherwise been a horrible stony
halfhour silence.
Don't say "choo choo choo" when you're "thinking".
Don't
try to change the subject and answer a different question. Don't try to
divert the interviewer from asking you a question by telling war
stories. Don't try to bluff your interviewer. You should focus on each problem they're giving you and make your best effort to answer it fully.
Some interviewers will not ask you to write code, but they will expect
you to start writing code on the whiteboard at some point during your
answer. They will give you hints but won't necessarily come right out
and say: "I want you to write some code on the board now." If in doubt,
you should ask them if they would like to see code.
Interviewers
have vastly different expectations about code. I personally don't care
about syntax (unless you write something that could obviously never
work in any programming language, at which point I will dive in and
verify that you are not, in fact, a circus clown and that it was an
honest mistake). But some interviewers are really picky about syntax,
and some will even silently mark you down for missing a semicolon or a
curly brace, without telling you. I think of these
interviewers as – well, it's a technical term that rhymes with "bass
soles", but they think of themselves as brilliant technical evaluators,
and there's no way to tell them otherwise.
So ask. Ask if they
care about syntax, and if they do, try to get it right. Look over your
code carefully from different angles and distances. Pretend it's
someone else's code and you're tasked with finding bugs in it. You'd be
amazed at what you can miss when you're standing 2 feet from a
whiteboard with an interviewer staring at your shoulder blades.
It's
OK (and highly encouraged) to ask a few clarifying questions, and
occasionally verify with the interviewer that you're on the track they
want you to be on. Some interviewers will mark you down if you just
jump up and start coding, even if you get the code right.
They'll say you didn't think carefully first, and you're one of those
"let's not do any design" type cowboys. So even if you think you know
the answer to the problem, ask some questions and talk about the
approach you'll take a little before diving in.
On the flip
side, don't take too long before actually solving the problem, or some
interviewers will give you a delayofgame penalty. Try to move (and
write) quickly, since often interviewers want to get through more than
one question during the interview, and if you solve the first one too
slowly then they'll be out of time. They'll mark you down because they
couldn't get a full picture of your skills. The benefit of the doubt is
rarely given in interviewing.
One last nontechnical tip: bring
your own whiteboard dryerase markers. They sell pencilthin ones at
office supply stores, whereas most companies (including Google) tend to
stock the fat kind. The thin ones turn your whiteboard from a 480i
standarddefinition tube into a 58inch 1080p HD plasma screen. You
need all the help you can get, and free whiteboard space is a real
blessing.
You should also practice whiteboard spacemanagement
skills, such as not starting on the right and coding down into the
lowerright corner in Teeny Unreadable Font. Your interviewer will not
be impressed. Amusingly, although it always irks me when people do
this, I did it during my interviews, too. Just be aware of it!
Oh,
and don't let the marker dry out while you're standing there waving it.
I'm tellin' ya: you want minimal distractions during the interview, and
that one is surprisingly common.
OK, that should be good for nontech tips. On to X, for some value of X! Don't stab me!
Tech Prep Tips
The
best tip is: go get a computer science degree. The more computer
science you have, the better. You don't have to have a CS degree, but
it helps. It doesn't have to be an advanced degree, but that helps too.
However,
you're probably thinking of applying to Google a little sooner than 2
to 8 years from now, so here are some shorterterm tips for you.
Algorithm Complexity:
you need to know BigO. It's a must. If you struggle with basic bigO
complexity analysis, then you are almost guaranteed not to get hired.
It's, like, one chapter in the beginning of one theory of computation
book, so just go read it. You can do it.
Sorting: know
how to sort. Don't do bubblesort. You should know the details of at
least one n*log(n) sorting algorithm, preferably two (say, quicksort
and merge sort). Merge sort can be highly useful in situations where
quicksort is impractical, so take a look at it.
For God's sake, don't try sorting a linked list during the interview.
Hashtables: hashtables are arguably the single most important data structure known to mankind. You absolutely have to know how they work.
Again, it's like one chapter in one data structures book, so just go
read about them. You should be able to implement one using only arrays
in your favorite language, in about the space of one interview.
Trees:
you should know about trees. I'm tellin' ya: this is basic stuff, and
it's embarrassing to bring it up, but some of you out there don't know
basic tree construction, traversal and manipulation algorithms. You
should be familiar with binary trees, nary trees, and trietrees at
the very very least. Trees are probably the best source of practice problems for your longterm warmup exercises.
You
should be familiar with at least one flavor of balanced binary tree,
whether it's a red/black tree, a splay tree or an AVL tree. You should
actually know how it's implemented.
You should know about tree traversal algorithms: BFS and DFS, and know the difference between inorder, postorder and preorder.
You
might not use trees much daytoday, but if so, it's because you're
avoiding tree problems. You won't need to do that anymore once you know
how they work. Study up!
Graphs
Graphs are, like, really really important. More than you think. Even if you already think they're important, it's probably more than you think.
There
are three basic ways to represent a graph in memory (objects and
pointers, matrix, and adjacency list), and you should familiarize
yourself with each representation and its pros and cons.
You
should know the basic graph traversal algorithms: breadthfirst search
and depthfirst search. You should know their computational complexity,
their tradeoffs, and how to implement them in real code.
You
should try to study up on fancier algorithms, such as Dijkstra and A*,
if you get a chance. They're really great for just about anything, from
game programming to distributed computing to you name it. You should
know them.
Whenever someone gives you a problem, think graphs.
They are the most fundamental and flexible way of representing any kind
of a relationship, so it's about a 5050 shot that any interesting
design problem has a graph involved in it. Make absolutely sure you
can't think of a way to solve it using graphs before moving on to other
solution types. This tip is important!
Other data structures
You
should study up on as many other data structures and algorithms as you
can fit in that big noggin of yours. You should especially know about
the most famous classes of NPcomplete problems, such as traveling
salesman and the knapsack problem, and be able to recognize them when
an interviewer asks you them in disguise.
You should find out what NPcomplete means.
Basically, hit that data structures book hard, and try to retain as much of it as you can, and you can't go wrong.
Math
Some
interviewers ask basic discrete math questions. This is more prevalent
at Google than at other places I've been, and I consider it a Good
Thing, even though I'm not particularly good at discrete math. We're
surrounded by counting problems, probability problems, and other
Discrete Math 101 situations, and those innumerate among us blithely
hack around them without knowing what we're doing.
Don't get mad
if the interviewer asks math questions. Do your best. Your best will be
a heck of a lot better if you spend some time before the interview
refreshing your memory on (or teaching yourself) the essentials of
combinatorics and probability. You should be familiar with nchoosek
problems and their ilk – the more the better.
I know, I know,
you're short on time. But this tip can really help make the difference
between a "we're not sure" and a "let's hire her". And it's actually
not all that bad – discrete math doesn't use much of the highschool
math you studied and forgot. It starts back with elementaryschool math
and builds up from there, so you can probably pick up what you need for
interviews in a couple of days of intense study.
Sadly, I don't have a good recommendation for a Discrete Math book, so if you do, please mention it in the comments. Thanks.
Operating Systems
This
is just a plug, from me, for you to know about processes, threads and
concurrency issues. A lot of interviewers ask about that stuff, and
it's pretty fundamental, so you should know it. Know about locks and
mutexes and semaphores and monitors and how they work. Know about
deadlock and livelock and how to avoid them. Know what resources a
processes needs, and a thread needs, and how context switching works,
and how it's initiated by the operating system and underlying hardware.
Know a little about scheduling. The world is rapidly moving towards
multicore, and you'll be a dinosaur in a real hurry if you don't
understand the fundamentals of "modern" (which is to say, "kinda
broken") concurrency constructs.
The best, most practical book I've ever personally read on the subject is Doug Lea's Concurrent Programming in Java.
It got me the most bang per page. There are obviously lots of other
books on concurrency. I'd avoid the academic ones and focus on the
practical stuff, since it's most likely to get asked in interviews.
Coding
You should know at least one programming language really well, and it should preferably
be C++ or Java. C# is OK too, since it's pretty similar to Java. You
will be expected to write some code in at least some of your
interviews. You will be expected to know a fair amount of detail about
your favorite programming language.
Other Stuff
Because
of the rules I outlined above, it's still possible that you'll get
Interviewer A, and none of the stuff you've studied from these tips
will be directly useful (except being warmed up.) If so, just do your
best. Worst case, you can always come back in 612 months, right? Might
seem like a long time, but I assure you it will go by in a flash.
The
stuff I've covered is actually mostly redflags: stuff that really
worries people if you don't know it. The discrete math is potentially
optional, but somewhat risky if you don't know the first thing about
it. Everything else I've mentioned you should know cold, and then
you'll at least be prepped for the baseline interview level. It could
be a lot harder than that, depending on the interviewer, or it could be
easy.
It just depends on how lucky you are. Are you feeling lucky? Then give it a try!
Send me your resume
I'll
probably batch up any resume submissions people send me and submit them
weekly. In the meantime, study up! You have a lot of warming up to do.
Realworld work makes you rusty.
I hope this was helpful. Let the flames begin, etc. Yawn.
Original story
Google telephonic Interview
Asked
about my project. Prepare well to answer any type of questions that may
arise in your project.They will just ask to explain about any one of
the projects listed in your resume.
In a plane, n points
are given i.e. the input is (x1,y1), (x2,y2)... (xn,yn). Now given
these n points.Find the maximum number of collinear points.
Solution:
The
duality algorithm would work. Find the point of intersection with
maximum no of lines incident on it in the dual plane. It works in
O(n^2).
Write the code for finding the min of n number.
I gave:
for(i=0;i<n;i++)
{
if( a[i]<min )
{
min = a[i]  eq(i)
}
}
Given that n numbers are from random sampling how many times (probability) does the line (i) be executed
Solution:
min=a[0];
for(i=1;i<n;i++)
{
if( a[i]<min )
{
min = a[i]; eq(i)
}
}
Once
the variable min is initialized,the probability of a[i] < min is
1/2. So the expected number of occurances of equation i is (n1)/2 .
Google Interview Round 2:
What is Bottom up parsing and what is top down parsing?
Solution:
Bottomup
parsing is a strategy for analyzing unknown data relationships that
attempts to identify the most fundamental units first, and then to
infer higherorder structures from them. It attempts to build trees
upward toward the start symbol. It occurs in the analysis of both
natural languages and computer languages.
Topdown
parsing is a strategy of analyzing unknown data relationships by
hypothesizing general parse tree structures and then considering
whether the known fundamental structures are compatible with the
hypothesis. It occurs in the analysis of both natural languages and
computer languages. Please refer to these links for much better
information.
http://en.wikipedia.org/wiki/Bottomup_parsing
http://en.wikipedia.org/wiki/Topdown_parsing
What is a symbol table?
Solution:
In
computer science, a symbol table is a data structure used by a language
translator such as a compiler or interpreter, where each identifier in
a program's source code is associated with information relating to its
declaration or appearance in the source, such as its type, scope level
and sometimes its location.
Check out
http://en.wikipedia.org/wiki/Symbol_table
There
is a portal with two billion users registered. If you store all the 2
billion users in a conventional databases it will take more time to
retrieve the data about a particular user when that user tries to
login. How do you handle this situation to make sure that the user gets
the response quickly.
Solution:
Every row has a primary key. Suppose the primary key for this
particular database is the name of the user then we can sort the names based
on alphabets and do secondary indexing based on the starting alphabet . If
the data is uniformly distributed we can go for multilevel indexing or
hashing.Similarly if we have a registration number as the primary key then
we can sort the table based on registration number and then do indexing
either secondary level or multilevel or apply hashing techniques based on
the distribution of data. Many efficient algorithms are available for
indexing and hashing.
There
are 8 identical balls. One of them is defective. It could be either
heavier of lighter. Given a common balance how do you find the
defective ball in least number of weighings.
Solution:
Weigh 3 balls against 3 others.
Case A:
If, on the first weighing, the balls balance, then the defective is
among the 2 remaining balls and can be determined using 2 weighings
making it a total of 3.
Case B:
Step1: If, on the first weighing, the balls don't balance.
If the balls do not balance on the first weighing, we know that the odd
ball is one of the 6 balls that was weighed. We also know that the
group of 2 unweighed balls are normal, and that one of the sides, let's
say Side A, is heavier than the other (although we don't know whether
the odd ball is heavy or light).
Step 2 :
Take 2 balls from the unweighed group and use them to replace 2 balls
on Side A (the heavy side). Take the 2 balls from Side A and use them
to replace 2 balls on Side B (which are removed from the scale).
I. If the scale balances, we know that one of the 2 balls removed from
the scale was the odd one. In this case, we know that the ball is also
light. We can proceed with the third weighing amd determine the lighter
of the 2 balls ,hance the defective.
II. If the scale tilts to
the other side, so that Side B is now the heavy side, we know that one
of the three balls moved from Side A to Side B is the odd ball, and
that it is heavy. We proceed with the third weighing and determine the
heavier one ,the defective.
III. If the scale remains the
same, we know that one of the two balls on the scale that was not
shifted in our second weighing is the odd ball. We also know that the
unmoved ball from Side A is heavier than the unmoved ball on Side B
(though we don't know whether the odd ball is heavy or light).
Step 3 (for Case B):
Weigh the ball from Side A against a normal ball. If the scale
balances, the ball from Side B is the odd one, and is light. If the
scale does not balance, the ball from Side A is the odd one, and is
heavy.
You have all the English words with
you. you would like to manage a dictionary so that you can look up when
ever you have doubt. Which data structure would you like to use and why?
Solution:
Dozens
of different data structures have been proposed for implementing
dictionaries including hash tables, skip lists, and balanced/unbalanced
binary search trees  so choosing the right one can be tricky.
Depending on the application, it is also a decision that can
significantly impact performance. In practice, it is more important to
avoid using a bad data structure than to identify the single best
option available.As the frequency of look ups for a word is also
important,weighted binary search tree with weights in proportion to the
frequency of lookups and determining the depth, can be effective.
Asked me about all the details of hash table and heaps.
Write code for finding number of zeros in n!
Solution:
A
zero in n! typically occurs when a multiple of 5 gets multiplied to an
even number.We use this simple yet effective information to solve this
problem.In the first n natural numbers,those divisible by 5 are always
less than the no of even numbers.So it all boils down to the power of 5
in the prime factorization of n! .
This simple formula works for finding it floor(n/5)+floor(n/25)+floor(n/125)+......
function zeros(int n)
{
int count=0,k=5;
while(n>=k)
{
count+=n/k;
k*=5;
}
return count;
}
this count is the number of o's in n!.
Google Interview Round 3 :
Write
C++ class for the game Connect Four. [Connect Four (also known as Plot
Four, Four In A Row, and Four In A Line) is a twoplayer board game in
which the players take turns in dropping discs into a seven column grid
with the objective of getting four of one's own discs in a line.]
Given a stack and an input string of 1234.At any point you can do anyone of the follow
i. take the next input symbol and Enque.
ii. you can pop as many as you can. When ever you
pop an element it will be printed
(you cannot pop from an empty stack)
How many such permutations are possible on an input of size N?
Solution:
It is Nth catalan number.For a detailed solution look at question5 of Stacks and Queues
Give an example of one permutation that this data structure cannot generate.
For Example:
1234 is input.
First push all 1,2,3,4 on to stack and pop all.
output will be 4321.
It means that this data structure can generate 4321.
Solution:
3124
for a detailed solution please look at question7 of the post
Stacks and Queues
Question 2 was pretty easy right? Now do again the same question but the data structure this time around is a Deque.
Input: 12345
Data Structure: Deque ( Doubly Que )
Note: Deque is a data structure into which you can do enque
and deque from both sides.Some thing like this
__________________________________
enque > <enque dequeue < >dequeue
__________________________________
Solution:
It
is N!. Guess why?(no constraints).Convince yourself by proving that
every permutation can be generated by a set of valid operations.This
prove can be using the principle of strong mathematical induction.So
for this specific input the answer is 120.
Classic
Egg Puzzle Problem You are given 2 eggs.You have access to a 100store
building. Eggs can be very hard or very fragile means it may break if
dropped from the first floor or may not even break if dropped from 100
th floor.Both eggs are identical.You need to figure out the highest
floor of a 100store building an egg can be dropped without breaking.
Now the question is how many drops you need to make. You are allowed to
break 2 eggs in the process.
Solution:
Let "d" be the number of drops required to find out the max floor.we need to get the value of d.
let's
say if we drop from height d then if it breaks then we have d1 floors
to check for the second egg . so max of "d" drops, so first we will
drop it from height "d" if it doesn't break at a height "d" then we are
left with "d1" drops,so lets drop it from d + 'd2' + 1 height suppose
if it break there then you are left with 'd2' drops.
and so on until that sum is less than 100, it's like a linear search,
in equations,
(1+(d1))+ (1+(d2)) + .... >= 100
here we need to find out d
from the above equation
d(d + 1)/2 >= 100
from above d is 14
Google Interview Round 4 :
Given n non overlapping intervals and an element. Find the interval into which this element falls.
Solution:
we can extend binary search to intervals.(Assuming the intervals are sorted)
consider interval [a,b].
if (ax)(bx) <=0
then x belongs to [a,b].
else
if x>a
element can be present only in the intervals to its right.
so select the middle interval among them to it's right
and repeat the procedure.
else
element can be present only in the intervals to its left.
so select the middle interval among them to it's left
and repeat the procedure.
The complexity of this problem is log(N) where N is the number of sorted nonoverlapping intervals.
Worst
case is take all intervals one at a time and see whether the element
lies in the interval or not.It will take O(n). So please give a
solution that will do better than O(n).
Now given
that the n intervals are overlapping then how do you solve? The
interviewer was concentrating more on the complexities (running, memory
..)
Solution:
If the above intervals
are overlapping ,then they can be merged in O(N) and then the exact
intervals can be resolved later.Otherwise ,we can identify one correct
interval and then linear search on its left and right neighbourhood to
find the other solutions.
Write code for Random Sort?
Algorithm is explained:
Given an input array of size n. Random sort is sampling
a new array from the given array and check whether the
sampled array is sorted or not. If sorted return else
sample again. The stress was on the
code.
Google Interview Round 5: This is Manager Round
Tell me an achievement that you have done in your non academics
Tell me about one of your project
Take a feature of C++ and tell me how you have implemented it in one of your project
By
taking one of your project as example tell me how you have taken care
of software engineering where you would have handled more data
There
is a routine already written to find the subtraction of two sets ( set
A  set B) . Write test cases for testing it.Tell me how do you test
the test cases you have written?
There is a printed
book. The page numbers are not printed. Now the printing of page
numbers is being done separately. If the total number of digits printed
is 1095 then how many pages does the book have?
Solution: Well people,this is too simple a question ..so do give it a try..(no malice,too simple).Any queries then do shoot a comment.
I thought it might be useful to collect some
of the questions I or my friends have been asked over the years. I've
had a number of jobs in the computer industry with the side effect that
I've been to a lot of interviews. Obviously these are all centered
around Linux System Administration since that's my profession.
So to dive right in, here are some questions I remember:
Name the three packets exchanged in the
setup of a TCP connection. Followup: name the three packets exchanged
when a client closes a TCP connection.
Answer: SYN, SYN/ACK, SYN
Followup: FIN, ACK, FIN, ACK
Three times are kept for every unix file. What are they?
Answer: atime, ctime, and mtime. The atime is
the access time, i.e. the last time the file was read. ctime seems like
it should be the creation time, but it isn't. In fact, there is no way
to determine when a file was created in Unix. ctime stands for change time,
and it is a record of the last time the file's inode was changed. This
happens for example when the permissions or ownership on the file are
modified.
Finally, the mtime is the time the file was modified, i.e. when the actual file was written to.
How many computers can you put on a /17 network?
Interviewers love these sorts of questions. I
personally hate them, but maybe that's just me. The answer to this
particular question is 32766. The quick formula is (2^(3217))2, i.e.
subtract the cidr # from 32, raise 2 to that power, and subtract 2. Why
subtract 2? Because all 0s and all 1s are not valid system addresses.
All 1s is the broadcast address. All 0s is technically a valid address,
but for historical reasons you can't use it. Thus for any address range
you always have to subtract 2 entries to get the number of usable
addresses.
A followup question is what is the netmask?
Answer: 255.255.128.0. To calculate, observe that in binary a /17 cidr
can be written as:
11111111 11111111 10000000 00000000
the first two octets are 255 (all ones). The
last is 0 (all zeros). Thus the only one you need to convert to decimal
is 10000000. To do this, dust off your binary knowledge:
10000000 = (0x2^0) + (0x2^1) + (0x2^2) + (0X2^3) + (0x2^4) + (0x2^5) + (0x2^6) + (1x2^7)
2^7 is 128, so it's 0+0+0+0+0+0+0+128 = 128. The netmask is therefore 255.255.128.0.
I suspect there's an easier way to do that.
What's an inode? Followup: what key piece of information about a file is not stored in the inode?
An inode is the ondisk data structure that
describes a file and contains key information such as owner and
permission. The answer to the followup is the filename  that is stored
in the directory. Followup to followup: this also explains the
difference between ctime and mtime.
What's the first startup script executed on a Fedora system?
Answer: /etc/rc.d/rc.sysinit
Put the following operations in order from
slowest to fastest: read cpu register, disk seek, read from main
memory, write to pci bus.
Answer: disk seek, write to pci bus, read from main memory, read cpu register
Compare the output of two processes using diff. Don't use temporary files.
Answer: use NamedPipesInBash, i.e.:
# diff <(process one) <(process two)
(this one is kind of extra credit)
What does the sticky bit do when applied to a file? A directory?
Describe RAID levels 0,1,5, and 0+1. What's the difference between 0+1 and 1+0?
What's the difference between my and local in perl? Give examples of usage of both.
Write a script that takes an input word and a corpus of text, and finds all anagrams of the input word in the text.
A pretty good way to do this in perl is to read
the input line by line. Then break each line into words by word
boundary (\b). Alphabetize the letters of the imput word and each word
in the line. If they are a match, you've found an anagram.
What are the three fundamental data types in Perl?
array, hash, scalar
Define a zombie process. Followup: when and why does init become the parent of a process?
A process becomes a zombie when it's parent
exits without calling wait().
If parent dies before child, init (PID 1) becomes parent of such child.
This is necessary to reclaim process state after child exits.
In bash, what variable contains the exit status of the last executed process?
$?
My intention here is not to trouble Google interviewers. I was just
collecting some classic puzzles and found this one and a small Google
search showed me that this is a Google interview puzzle to my pleasant
surprise. But many of the answers I found were either wrong or totally
twisted. I am making no surety of the answer I give and I am open to
your remarks or suggestion or corrections.
The Standard Problem in simple writing goes like this:
* You are given 2 eggs.
* You have access to a 100storey building.
* Eggs can be very hard or very fragile means it may break if dropped
from the first floor or may not even break if dropped from 100 th
floor.Both eggs are identical.
* You need to figure out the highest floor of a 100storey building an egg can be dropped without breaking.
* Now the question is how many drops you need to make. You are allowed to break 2 eggs in the process
If
you are one of the people who likes to solve a puzzle before seeing the
answer you must quit the blog now and come back later for checking the
answer.
Now that this is a Google interview question I am
taking the normal "InterviewStyle" of solving a problem. Simply saying
thinking aloud through the solution from worst to the best correcting
the flows optimizing the solution or taking the 5minute hard thinking
acting pause to a problem, which you know already and just want to make
your interviewer think that you are a challenge lover.
Solution
Drop
the first egg from 50.If it breaks you can try the same approach for a
50storey building (1 to 49) and try it from 25th floor. If it did not
break try at 75th floor. And use linear search with the remaining
portion of storey we need to test. For example if the first egg breaks
at 50 we need to try all possibilities from 1 to 49.
Now this
looks a feasible solution. In computer student's jargon do a binary
search with first egg and linear search with the second one. Best case
is log (100) and worst is 50.
Now the optimal solution for
the problem is that you figure out that you will eventually end up with
a linear search because you have no way of deciding the highest floor
with only one egg (If you broke one egg and you have to find the answer
among 10 all you can do is start from the lowest to the highest and the
worst is the total number of floors). So the whole question grinds up
to how to make use of the first egg to reduce the linear testing of the
egg.
(For strict computer science students, well this
problem can be solved using binary search on the number of drops needed
to find the highest floor.)
Now let x be the answer we want, the number of drops required.
So
if the first egg breaks maximum we can have x1 drops and so we must
always put the first egg from height x. So we have determined that for
a given x we must drop the first ball from x height. And now if the
first drop of the first egg doesn’t breaks we can have x2 drops for
the second egg if the first egg breaks in the second drop.
Taking
an example, lets say 16 is my answer. That I need 16 drops to find out
the answer. Lets see whether we can find out the height in 16 drops.
First we drop from height 16,and if it breaks we try all floors from 1
to 15.If the egg don’t break then we have left 15 drops, so we will
drop it from 16+15+1 =32nd floor. The reason being if it breaks at 32nd
floor we can try all the floors from 17 to 31 in 14 drops (total of 16
drops). Now if it did not break then we have left 13 drops. and we can
figure out whether we can find out whether we can figure out the floor
in 16 drops.
Lets take the case with 16 as the answer
1 + 15 16 if breaks at 16 checks from 1 to 15 in 15 drops
1 + 14 31 if breaks at 31 checks from 17 to 30 in 14 drops
1 + 13 45 .....
1 + 12 58
1 + 11 70
1 + 10 81
1 + 9 91
1 + 8 100 We can easily do in the end as we have enough drops to accomplish the task
Now
finding out the optimal one we can see that we could have done it in
either 15 or 14 drops only but how can we find the optimal one. From
the above table we can see that the optimal one will be needing 0
linear trials in the last step.
So we could write it as
(1+p) + (1+(p1))+ (1+(p2)) + .........+ (1+0) >= 100.
Let 1+p=q which is the answer we are looking for
q (q+1)/2 >=100
Solving for 100 you get q=14.
So the answer is: 14
Drop
first orb from floors 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99,
100... (i.e. move up 14 then 13, then 12 floors, etc) until it breaks
(or doesn't at 100).
Please feel free to correct or post any comment on the solution or the answer.
Links I found useful
How to get hired at Google
Preparing For a Software Engineering Interview
Google's recruitment procedure