Google interview questions - fun brain teasers! Saturday, September 8, 2007
1. How many golf balls can fit in a school bus?
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?
3. How much should you charge to wash all the windows in Seattle?
4. How would you find out if a machine’s stack grows up or down in memory?
5. Explain a database in three sentences to your eight-year-old nephew.
6. How many times a day does a clock’s hands overlap?
7. You have to get from point A to point B. You don’t know if you can get there. What would you do?
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?
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?
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?
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)?
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!)
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?
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?
15. How many piano tuners are there in the entire world?
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?
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.)
Hi All
Answer 17: This is a classical question. and surprisingly the hint given is correct!
The answer is Pirate 5 98, Pirate 2 1 and Pirate1 1 gold coin.
Reasonning:
Pirate 1 plan: pirate 5 dead, Pirate 4 dead, pirate 3 dead, pirate 2 dead, pirate 1 100 coin.
pirate 2 plan: pirate 5 dead, Pirate 4 dead, pirate 3 dead, pirate 2 0 , pirate 100 coin.
pirate 3 plan :pirate 5 dead, Pirate 4 dead, pirate 3 99 , pirate 2 1 coin, pirate 0 coin.
pirate 4: pirate 5 dead, Pirate 4 98 coin, pirate3 0 coin , pirate 2 1 coin, pirate 1 coin.
pirate 5: pirate 5 98 , Pirate 4 0 coin, pirate3 0 coin , pirate 2 1 coin, pirate 1 coin.
This will the plan of the fifith pirate.
You’re a pirate.
pirate 5’s plan ( top )
98 for himself(p5)
0 for p4
0 for p3
1 for p2
1 for p1
p1 & p2 have doubt that, they may not get anything if p4 or p3 puts the plan, hence they will be happy with even 1 coin.
I didn’t like the way the question is asked first of all. It does not contain all the necessary information. Also the solutions posted here are not correct. You can find the solution in this link: http://en.wikipedia.org/wiki/Pirate_game
This problem is a game theory question and I think is not very appropriate for an interview where people struggle to answer many different questions under pressure.
few more interviews by Google
Interview At Google
Google Top Interview Questions ( around 30 With Solutions)
Google Interview for Freshers
i cant find an answer to any of the brain teasers.
#1
About 500,000, assuming the bus is 50 balls high, 50 balls wide, and 200 balls long
#2
Use the measurement marks to climb out
Try to unscrew the glass
Risk riding out the air current
#3
Assuming 10,000 city blocks, 600 windows per block, five minutes per window, and a rate of $20 per hour, about $10 million
#4
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. (If they’re the same, you did something wrong!)
#5
A database is a way of organizing information. It’s like a genie who knows where every toy in your room is. Instead of hunting for certain toys yourself and searching the whole room, you can ask the genie to find all your toy soldiers, or only X-Men action figures, or only race cars — anything you want.
#6
The clock hands don’t overlap at 1:05, 2:10, 3:15 etc. Because, by the time the minutes hand reaches where the hours hand was, the hours hand has moved on, as it doesn’t remain fixed through the entire hour. the answer can be worked out in this way:
In every hour, as the hour hand moves across 5 minute spaces, the minute hand moves across 60. That means the minute hand gains 55 min sp. over hour hand in 60 min. Thus, between the nth and (n+1)st hr, to overlap the minute hand must gain the 5n min sp. that exists between them when the clock strikes n hrs. Apply unitary method and you get the time in which it does so i.e. 60n/11 min. So, the clock hands overlap at n hrs 60n/11 min. Obtain the values by putting m = 0 to 11, and you will find that from 00:00:00 to 23:59:59 (please note that 23:59:60 is equivalent to 24:00:00 or 00:00:00), the hands overlap 22 times.
#7
The two most common way to tackle problem like this is using Depth-First Search (DFS)and Breadth-First Search (BFS).
In the example above, You drive and drive around until you hope to find the destination. Reach a deadend? Turn around and come back where you came from. It might not be the shortest way, but if you tried every possible road, you’ll know that maybe you can’t get to China from New York (And that’s a DFS!).
Understanding these leads to you more exotic things like A* Search, and it’s a fundamental exploring algorithm. Too many things can be reduced into a graph, and knowing the best way to search a graph will come in handy. DFS is basically a stack-based implementation, while BFS is a queue-based implementation, and each with its strength and weaknesses.
#8
Hash it. Take every shirt, and put it in a different drawer depending on the color of the shirt. Whenever you want a shirt, all you have to do is simply open the drawer with the corresponding color. That’s hashing in a nutshell.
#9
Since each wife never knows her husband has cheated on her, there is no way of killing an husband because she can’t prove it.
#10
about 1:1
Half the couples have boys first, and stop. The rest have a girl. Of those, half have a boy second, and so on.
So suppose there are N couples. There will be N boys. There will be an “infinite” sum of girls equal to N/2 + N/4 + N/8 + … As any college math student knows, this sum adds up to N. Therefore, the proportion of boys to girls will be pretty close to 1:1, with perhaps a few more boys than girls because the sum isn’t actually infinite.
#11
Since you know the probability of seeing a car in 30 minutes is 0.95, then look at the probability of seeing a car in the first 10 minutes, or the second 10 minutes or the third ten minutes.
So then it is like a disjunctive probability: P( A or B or C ), i.e. P( 1st 10m or 2nd 10m or 3rd 10m ).
The formula for a disjunctive probability is
P(A or B or C) = P(A) + P(B) + P(C)
Since the default probability is constant, then, P(A) = P(B) = P(C) = x, so
3x=0.95
x = 0.95/3
#12
The hour hand moves at 30 degrees per hour, so the angle is 7.5 degrees.
#13
Let us organize our thought… let’s say that we have 4 persons, each identified with a letter: A, B, C, or D. Let’s say that A is the fastest, while D is the slowest. Each person’s speed is thus:
A - 1 bridge/min
B - 1/2 bridge/min
C - 1/5 bridge/min
D - 1/10 bridge/min
The flashlight only lasts 17 minutes. If they take turns, allow a buddy to cross the bridge and only then start crossing the bridge, then they will take 1+2+5+10 = 18 minutes, which is 1 minute past the flashlight’s battery lifetime.
MY SOLUTION: based on intuition, I would propose that the fastest person (A) should cross first, hold the flashlight and illuminate the bridge for the others. Then the slowest one (D) and the remaining fastest one (B) would start crossing, and once B gets to the other side, then C starts crossing. This way, we would take only 11 minutes to cross the bridge, and we would never have more than 2 persons simultaneously on the bridge. To make it more visualizable:
[0,1] minutes -> A is crossing the bridge
[1,3] minutes -> B and D are crossing
[3,8] minutes -> C and D are crossing
[8, 11] minutes -> D is alone crossing
#14
There are 10 people: p1 p2 p3 p4 p5 p6 p7 p8 f y
F=Friend
Y=You
Thus taking the bet puts you at a -1$ start assumeing that your friend doesn’t share your birthday. The chance of someone else having your birthday is 7.4% thus you would be at a huge disadvantige. You would end up in the hole roughly 19$, Because you have your own birthday.
#15
First think about how many pianos there are and how often they are used. Pianos are typically owned by middle to upper class households, and are also found schools, churches, hotels, etc.
The US population is approx 300 million. Assuming that each household has 3 people in it, that leaves 100 mil lion households. Of those, 50 million are in the middle to upper class and may have pianos. Of those 50 million households, you can think that no more than 10 percent have pianos. (That is probably high…it may be more like 2-3%). Anycase, that leaves us with approximately 5 million households with pianos.
Now you need to think about how many piano tuners it takes to maintain those pianos. I would say a typical piano tuner could tune approx 20 pianos a week (2 hours each), and given a full year, that is approximately 1000 pianos.
Now, how often do pianos need to be tuned? Once a year maybe? If that is the case, then there would be 1 piano tuner for every 1000 pianos. That mean approx 5000 piano tuners in the US.
Now think about the rest of the world, it’s population, and it’s wealth. I would guess that the US has 1/3 of the world’s pianos. Therefore, I would guess the total number of piano tuners in the world is approximately 15000.
#16
Put 4 balls on either of pan, you will get to know which pan is heavier. Now take the four balls from heavier pan and split them in group of two and place in each pan of balance to get the heavier group. And you can physically feel and can distinguish the heavier of the 2 balls.
#17
P5 98 (High Ranking)
P4 1 (So as not to complain)
P3 1 (So as not to complain)
P2 0
P1 0
P1 and 2 can complain all they want, but as long as P3 or 4 dosent complain the high ranking pirate get to stay alive.
13. Try the following:
1. The 1min and 2min cross and 1 min returns. Total time=3min
2. The 5min and 10min cross and the 2 min returns. Total Time=12min.
3. The 1min and 2min cross. Total time =2min.
Total time to cross is 17min.
13. All the answers posted here are wrong. This is the only sequence.
a: 1 min and 2 min cross and 1 min returns = 2 min (not 3)
b: 5 min and 10 min cross and 5 min returns = 10 min
c: 1 min and 5 min. cross = 5 min
total 17 min
I had to take a moment and thank you for the post you wrote. I have been trying to understand about interview questions for a while, there is so much information out there, but your post helped me understand the concept.
Thanks!
From eight balls take each half and place it in balance one which weighs more will have the heaviest ball among them
then split half among them again continue .again pick balls which weighs higher than the other. now remaining two balls
one with heavier weight can be found in same way.