Home »» Placement Papers »» All Papers »» Google »» Placement Paper

### Google Interview Questions Part - 1

Google Interview   Questions Part - 1

This is a list of interview puzzles used at     Google.

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?svery hard to find a     shirt. So what can you do to organize your shirts for easy retrieval?What method would you use to look up a word in a dictionary?
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 herhusband     has cheated, but does not know when her own husband has. The village has a     law that does not allow foradultery.Anywife who can prove thather     husband is unfaithful must kill him that very day. The women of the village     would neverdisobeythislaw.One day, the queen of the village visits and     announce that at least one husband has been unfaithful. What happens?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?How do youcutarectangular cake into two equal pieces when someone has     already taken a rectangular piece from it? The removed piece an be any size     or at any place in the cake. You are only allowed one straight cut.

How many piano tuners are there in the entire world?

What gives you joy?

Mike has $20 more than Todd. How much does each have given that combined they have$21 between them. You can?t use fractions in the answer. Hint:     This is a trick question, pay close attention to the condition)

How many times a day a clock?s hands overlap?

Two MIT math graduates bump into each other. They hadn?t seen each     other in over 20 years.

The first grad says to the second: ?how have you been??

Second: ?Great! I got married and I have three daughters now?

First:  ?Really? how old are they??

Second:  ?Well, the product of their ages is 72, and the sum of their ages     is the same as the number on that building over there..?

First: ?Right, ok.. oh wait.. I still don?t know?

second: ?Oh sorry, the oldest one just started to play the piano?

First: ?Wonderful! my oldest is the same age!?

Problem: How old are the     daughters?

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?

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)?

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?

You have an empty room, and a group of people waiting outside the room.     At each step, you may either get one person into the room, or get one out.     Can you make subsequent steps, so that every possible combination of people     is achieved exactly once?

The rectangle puzzle has a special case which does allow for an answer.     If the rectangular removed piece is smaller than the cake, then the solution     is to make a cut which joins the centre of the cake with the centre of the     removed piece (if these centres are the same point, then any cut through     this one point). However, if the removed piece is the whole cake, then there     is no possible cut, since there is no cake. I wonder how many people figured     this out (and I include the people who made up the question).

The last question about putting people in a room is the only one related     to anything at Google. The solution is simply the Gray code, which is     actually something of mild interest in Computer Science, and whose knowledge     might actually be useful to future work at a computer company. The other     questions are either silly, trivial if you know some math, or just wrong.

the 8 balls question answer is
1)take any 7balls from 8 and keep remaning aside
2)take any 6balls from that 7 keep remaing aside
NOW
CASE:1)
weigh:1)3 and 3 of that 6 if equal then
weigh:2)that 1 and 1 from remaing finish.

CASE:2)
weigh:1)same 3 and 3 of that 6 if not equal
weigh:2) 1 and 1 of that odd 3 finish

The ball question is silly because the algorithm works for up to 9 balls.     In general, you can find the heavier ball in N weighings if there are at     most 3^N balls, so using a non power of 3 misses the point. The general     algorithm for 3^N balls is:
Take 2 groups of 3^(N-1) balls. If they weigh the same, then the ball is     in the 3rd group, and you can find the ball in a further N-1 steps by     recursion. Otherwise, the ball is in the heavier group, and you can again     find it in N-1 further steps by recursion.
The adjustment for non powers of 3 is clear.
This is probably the easiest coin problem. The harder ones don?t tell     you if the coin is heavier or lighter.

You can also outwit the examiner in the clock quesiton. Normally the     answer would be 22, but that is assuming that there are only hour and minute     hands. However, you can outwit the examiner by making the formally correct     statement ?most clocks have a second hand? and just wait there until he     figures it out. Since this would obviously guarantee you wouldn?t get the     job, I?m wondering if the real point of these questions is to make sure     that you aren?t smarter than the people who made them up.

Anyone felt dumber reading Ilan?s responses?
On the rectangular cake, don?t cut it from up to down. Cut across at     mid-height.
The point of asking ?8″ balls is to lead people to think to weigh     4 with 4, 2 with 2, 1 with 1, etc. Weighing ?9″ balls actually make     the question easier.
On the married couples question, use induction and start with the village     having only 1 couple, then 2, and so on. Think in terms if you were the     wife, and you cheated with someone?s husband, how would you deduce if your     husband cheated and whether or not the other wife can deduce.

If you look at a clock and the time is 3:15, what is the angle between     the hour and the minute hands?
- Degrees per clock cycle or a circle: 360
- Degrees per clock cycle Ticks: 360 / 60 (total minute ticks in a clock) =     6 degrees
- Ticks between two hour digits: 5
- Minute Hand Ticks per Hour Hand Movement: 60/5 = 12
Using above data we can calculate the exact clock hands position &     angle for 3:15 Time i.e.
- Minute Hand position will be: 3
- Change in Hour Hand position will be: (5/12) * 15 = 1.25 (exact ticks out     of 5 hour ticks between two hour digits & this is also an exact ticks     difference from minute hand)
- So, ar there is (360/60) 6 degrees difference between two clock ticks     hence thers is 1.25 * 6 = 7.50 exact degrees difference between minute &     hour hands in 3:15 clock time :)

The answer to the bridge crossing questions:
I will use following terms.
camper1 - camper who can cross the bridge in 1 minute
camper2 - camper who can cross the bridge in 2 minute
camper5 - camper who can cross the bridge in 5 minute
camper10 - camper who can cross the bridge in 10 minute
1. camper1 and camper2 crosses (2 min)
2. camper1 gets back (1 min)
3. camper5 and camper10 crosses (10 min)
4. camper2 gets back (2 min)
5. camper1 and camper2 crosses (2 min)
Total 17 min.

To     CSharp?s question:
?If you look at a clock and the time is 3:15, what is the angle between     the hour and the minute hands??
The way I thought it was (ends in same result as urs):
The answer is that the hour hand moves 360 degrees in 12 hour. That is 30     degrees each hour - 7.5 degrees each quarter.
Therefore the difference     between the hands at 3 and warter is 7.5 degrees !

MIT Math Graduates Problem:-We know that 72?s factor are 2*2*2*3*3.Now     we need to calculate all possible combinations of ages from those     factors.The Combinations will be:-(2,4,9) and (2,6,6) and (2,3,12) and     (3,3,8) and (3,6,4).For every combination the sum of ages will be (15) and     (14) and (17) and (14) and (13) respectively.14 is the only digit which     comes twice so that is the digit which is written on building that?s why     first graduate couldn?t find out their correct ages.So possibly the ages     should be (2,6,6) or (3,3,8).Now second graduate says that his oldest     daughter just learned piano so this statement indicate that his oldest     daughter is not twin so surely there ages will be 3 and 3 and 8.

The Restangular Cake solution:
Whatever be the shape and size of the cut piece.
Just cut the cake horizontally from mid of the height.
thats all!

To explain the cake solution:
1) cutting a whole cake in half, in one strait cut, requires going from     one side, through the center of the cake, to the other side (we can chose     any angle we like).
2) cutting the empty part in half , using one strait cut, requires going     from one side of the empty part, through the center of the empty part, to     the other side of the empty part.
- The solution requires both cutting the whole cake in half, and cutting     the empty section in half, so we combine (1) and (2) to one striat cut     through both centers.
As explained by Ilan.

How many times a day a clock?s hands overlap?
Only 11 times. Overlap exists on or after every hour except after     11′o clock.
Srikanth Bethi

How many times a day a clock?s hands overlap?
Above answer is incomplete?.in a it completes 2 rounds?in the round     it gets 11 times and in the second round it gets only 10 times?
so the total is 21 times in a day

What gives you joy?
Word ?YOU? is having letters ?Y? & ?O? and it requires     letter ?J? to make ?JOY?. So the answer is ?J?.

Another way of looking at the 3:15 clock problem:
Normally hour hand moves 1/12 of clock each hour.
For 15 mins, it?s 1/4 of that then, or 1/48.
Then 360 degrees / 48 = 7.5 degrees.

For the $20 trick question, i think i just figured it out. M = 20 + T M + T = 21 Substitute M: 20 + 2T = 21 T = 0.5 So, Todd has$0.50 and Mike has \$20.50.
Oh, and i didn?t use fractions in my answer.
I used decimals.

probability of watching a car is .95 in 30 min
it means probability of watching a car is 95% in 30 min
probability of watching a car per minute is 95/30=1.9%
probability of watching a car in 10 minute is 1.9* 10=19%

To Vimal     Garg,
Your answer to the three girls? age is right, but you can?t just     verifying 72?s factor which is 2*2*2*3*3, because it is possible that the     youngest daughter?s age is 1, for example: 1, 6, 12.
The point to the question is that, there must be several combinations result     in the same summary. Like 2+6+6 = 3+3+8 = 14. And there could be only one     who has the oldest age, that is 8

To gaurav     khatwani,
your math is wrong in more than one spot.
You can?t merely say probability of seeing a car in one minute is x and     therefore in 10 minutes its 10*x. Probabilities don?t add up like that.
Think of tossing a quarter. The probability of seeing a heads in 2 flips     is 3/4 not 1/2 + 1/2.
Solution (I think) is the probability of not seeing a car in 30 minutes     is 05%.
If the probability of not seeing a car in 10 minutes is x. then for each     additional 10 minutes we multiply by x. so x^3 = .05
So the probability of seeing a car in 10 minutes is thus 1 - cuberoot(.05)

 Comment Tweet