Friday, August 15, 2008

Google Interview Questions

Found this on the net.

Since it's my last day at work, I thought it'd be fun for me to answer as many interview questions from Google as possible, in hopes that someone from Google might see this and whisk me away to the Googleplex.

1. How many golf balls can fit in a school bus?

By sheer guesstimation, a golf ball is a roughly spherical object an inch in diameter. A schoolbus will be assumed to be a 10 foot by 5 foot by 5 foot box (which I'm guesstimating as rough dimensions of a bus). Assuming I get perfect control over the way I stack spheres in a schoolbus, That would make (10 x 12) x (5 x 12) x (5 x 12) golfballs in the schoolbus. That makes 518400 golf balls.

Also, if I could do math, I would have been an accountant not a lawyer.

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?

I am about 66 inches tall. A nickel is about half an inch in diameter (which I assume what the question is asking, cos "height" could mean the thickness of the nickel). I weight about 160 pounds. I will weight 0.134 lbs or 2.1 ounces when I am shrunk down.

That's about the weight of 10 nickels, for perspective.

I would probably be able to generate enough force to really screw with the blades so that they won't even work, cos blender blades are actually pretty flimsy when force is applied perpedicular to the business end. Plus, most blenders have anti-locking mechanisms, so screwing with the blades will cause them to lock, which will in turn stop them from spinning.

3. How much should you charge to wash all the windows in Seattle?

It depends on how much it would cost me, how many other people can wash all the windows in Seattle, and how much the people in Seattle want their windows washed in aggregate. I can plug in some numbers but it will pretty much be making shit up.

4. How would you find out if a machine’s stack grows up or down in memory?

Say what?

5. Explain a database in three sentences to your eight-year-old nephew.

(a) Imagine every book you could ever want.

(b) Imagine all of these books stored in one place.

(c) Imagine a librarian to assist you to finding any book you want.

6. How many times a day does a clock’s hands overlap?

23 times, once an hour, except for midnight (or noon if you are callibrating from that point). Yes I know this is the wrong answer, but I'm being honest here.

7. You have to get from point A to point B. You don’t know if you can get there. What would you do?

I use Google maps, and follow the directions.

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?

I use my laundry as an indication of how used a set of shirts are. 4 washes a month means that shirt rises to the top of the pile, and get the most accessible area. Fewer washes go down the pile progressively. Shirts I never wash, I never wear, so that goes to the bottom of the pile, and into the least accessible area.

The unwashed shirts go to salvation army. The exception is winter clothing and suits. I will keep a set vacuum sealed and packed away for when I need 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?

One of two things can occur - no one talks, or everyone talks.

In a situation where no one talks, no one does anything. This is because the queen of the village's information does not add anything new to the table. Because every married couple has cheated on his wife, and every woman knows when a man other than her husband has cheated, each woman knows that 99 of the men in the village has cheated - which corroborates what the queen has said. Because each woman cannot PROVE that her husband has cheated, no one dies.

If any one woman asks any other woman the magic question "Did my husband cheat?" and gets an honest answer, then every man in the village dies. ONE woman executing her husband signals to the rest of the wives that she knows her husband had cheated. However, since every woman knows that every other husband had cheated except their own, the fact that one husband is executed MUST mean that every husband in the village has cheated. Once this is established, all husbands will be executed.

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?

Dammit. I know this is an "infinite series that tends towards 100%" question but I can't remember the math.

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

I can't even begin to figure out the math of this.

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

It's a quarter of one-twelfth of a full circle. That's 7.5 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?

Have 10 minute dude hold the torch and walk across while 5, 2, and 1 walk across in sequence. Here's the math.

5 and 10 minute dude start. 5 minute dude outpaces 10 minute dude, but 10 minute dude has torch pointing forward. Illuminated, 5 minute dude finishes and 10 minute dude is halfway across the bridge.

At this point, 10 minute dude must stop and point the torch backwards. 2 minute dude takes 1 minute to reach 10 minute dude's location and another minute to cross the bridge. In the time it takes for 2 minute dude to cross the bridge, 10 minute dude would have waited 1 minute, and progressed another one-tenths of the bridge. He's now at the 60% mark of the bridge.

Then comes 1 minute-dude. 10 minute dude must wait 60% of a minute, or 36 seconds, for 1 minute dude to reach his position before being able to continue forward. 1 minute dude finishes the remaining distance in 24 seconds but that is irrelevant because 10 minute dude still needs another 4 minutes to complete the journey.

The total time taken to cross the bridge is 10 minutes plus wait time which is 1 minute and 36 seconds, for a total of 11 minutes, 36 seconds, well before 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?

No, because statistically, you will need to find 2 birthday matches for every one non-birthday match there is in order to break even. Because the number of pairs for birthday matches is far less than the number of non-birthday matches, you will not find the critical mass you want no matter how many people there are in the room.

15. How many piano tuners are there in the entire world?

You know, I'd answer this question but McKinsey asks the same question. It's basically a bunch of numbers, assumptions and looking at the assumptions. I'll bite though.

There are 6 billion people in the world. 1.2 billion people live below the poverty line, and are too poor to buy pianos. 4.8 billion people remain. Since they are above the poverty line, it is fair to assume 5 people to a household (since large families tend to be associated with subsistence level living). 960 million families now.

Assuming a figure of 10% of these households have the inclination to own a piano. That's 96 million pianos worldwide. Assuming twice a year tuning, thats 192 million tunings a year. One piano takes a day to tune. Assuming 320 work days a year on average, it will take 600 thousand piano tuners worldwide to tune the pianos.

Assume also commercial piano ownage is negligible in light of this.

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?

Grab any 6 balls. Weigh 3 per plate. 2 results can happen.

(a) Both sides are equal. You then weigh the remaining 2 balls and find the heavier one.

(b) One side is heavier than the other. You grab two balls from the remaining pile and weigh them. If one is heavier, that's your ball. If they are both equal, the remaining ball is the heavier one.

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

Start with the end in mind.

In a situation where there are only 2 pirates left, the fourth can either give everything to the fifth pirate, or the fifth pirate will vote no and the fourth will die. Hence, the fourth pirate will either die or live, but get nothing. He will be playing to avoid that situation, so he -will- vote yes to one gold coin, which is superior to all other alternatives.

If the situation reaches the third pirate, how the fifth votes depends on whether it is possible for the fifth pirate to force the third pirate to be executed and lead matters to the aforementioned situation with the fourth pirate. However, since the third needs only 1 vote, and since the fourth will vote for 1 gold coin, the third will divide the gold coin as 99 to himself and 1 for the fourth, securing his vote and making the fifth's vote irrelevant.

Hence, by the time it reached the third pirate's distribution, the fifth will get nothing. Hence, from the first to the second pirate, the fifth will vote yes to one gold coin, since it is impossible for the fifth to get a single gold coin if the third wants to ensure he gets away with the lion's share of the wealth while securing a vote.

Hence, the first pirate can give a gold coin to the fourth and fifth pirates, and keep 98 for himself. The fourth will accept one gold coin because any distribution prior to his own distribution that gives him one gold coin will result in a gain for him. The fifth pirate will not get anything by the time the third pirate distributes because the fourth pirate's situation will compel him to accept the offer of one gold coin from the third. Because he gains nothing by the time the third pirate's distribution comes around, he will accept a gold coin from anyone before the third pirate's distribution and make a gain. Two votes pass the resolution.

It isn't necessary to discuss the second pirate's situation anymore, since the second pirate's situation is identical to the first, but with a smaller pool of candidates. The second still needs 2 votes to secure his distribution, and he can essentially use the same solution as the first pirate.

7 comments:

dagger said...

On q5, point (b), given google's move towards cloud computing and storage, saying a database is a collection of information concentrated in one location may not be the best answer. I would have also elaborated on the librarian's kick ass ability to find exactly what your nephew wants in milliseconds.

That or have a nephew with genius level IQ.

Joeli said...

Good luck with your new job! The only advice I can give is - according to some of your answers - don't give up your day job in favour of engineering or computer science. ;)

Anthony said...

Dagger,

Actually, I didn't think of distributed storage and computing. Ah well.

Joeli,

Yeah, I'm pretty bad at math, but pretty good at logic puzzles. The ones that give me the least problems are the logic puzzles, the most problems, the math and engineering.

Anonymous said...

Anthony,
Question 4 is about computer memory stacking models.
Some memory stacks work upwards and some memory stacks work downwards. The easiest answer I could think of was use a "Write" command (or its equivalent in whatever language you are using) and get it to WRITE OUT the items in the memory stack.
Jim Profit

(T) (H) (B) said...

Er.. It's ok.. I'll stay with my job cos I have no idea how to answer any of the questions!!!

Anthony said...

Jim,

Say what?

THB,

That's fine. I'm told (by two people no less) that I should stick with my day job anyways.

BunnyButt said...

About the piano question, you forgot music schools and schools. ;)

There are a total of 4 pianos in my school.

But I'm just nit-picking. Sorry.