15 google interview questions

[tkil]

Ran across this link earlier: 15 Google Interview Questions That Will Make You Feel Stupid

First, my answers:

1. How many golf balls can fit in a school bus?
   Figure golf balls are about 1.5" diameter, so 6 per foot, 36 per square foot, 216 per cubic foot (oops, that's 8 per linear foot, 64 per square foot, and 512 per cubic foot). Figure the school bus is 8' wide, 6' tall, and 25' long. That gives 1200 cubic feet, or about 260,000 550,000 golf balls.
2. How much should you charge to wash all the windows in Seattle?
   No real idea on this one. Only approach I came up with was to take population of Seattle (presumably metro area), allocate each person a certain number of house windows, and a number of office windows (possibly of skyscrapers, hence more expensive) and go from there. Smart-ass replies include "as much as they'll pay".
3. 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?
   A quick table shows 1/2 have 1 boy; 1/4 have 1 girl, then 1 boy; 1/8 have 2 girls then 1 boy, etc. So the sum for boys is easy: across 100 couples, we have 100 boys. The girls are a bit harder: 25 + 12.5*2 + 6.25*3 + 3.125*4 + ... + n*2^-(n-1) = 25 + 25 + 18.75 + 12.375 = 81.125. Not having the energy to find the closed-form solution to that sum, we can guess from the values we have already that it's likely to just end up being 50/50. A quick check on a spreadsheet bears out that suspicion.
4. How many piano tuners are there in the entire world?
   No idea. Maybe start from one person in 50 owning a piano, two tunings a year, tuning takes two hours, tuner works 50 weeks/year (which is 2000, or 1000 tunings, or 500 pianos), so we need one tuner per 25k people. Underestimate total world population to be 5G, and we have 200k piano tuners.
5. Why are manhole covers round?
   Traditional answer is: so they can't fall into the hole. Secondary bonus is that they're symmetrical, so you don't have to worry about lining them up to close them, either.
6. Design an evacuation plan for San Francisco
   First cut: make all highways and bridges contraflow, so they're pure outbound. (Might need one inbound for emergency access, but that might also be a better use of ferries.) Then assign outbound routes via zip codes; they're fairly geographic, everyone knows theirs, and they're difficult to fake.
7. How many times a day does a clock’s hands overlap?
   23 (including both midnights). If the hour hand didn't move, both midnights would have the minute hand crossing 12 o'clock 25 times; but the hour hand does move, and it catches up twice, so 23 crossings. Another way of looking at it is that crossings occur 1:05:05.mumble apart; 22 intervals then adds up to 24 hours, and you need one more crossing to correct the fencepost error at the end.
8. Explain the significance of "dead beef"
   a. it's real words spelled out of valid hex characters (hence you can do "0xdeadbeef");
   b. it's hard to cook a moving cow.
9. A man pushed his car to a hotel and lost his fortune. What happened?
   A meteorite struck the earth and everyone died. (Guess who hates under-specified "lateral thinking" problems?)
10. You need to check that your friend, Bob, has your correct phone number, but you cannot ask him directly. You must write 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?
    If you know Bob's phone number, and Eve doesn't, then you can ask Bob to write down the product of his phone number and yours. If you only want to check that Bob has the correct phone number, any checksum will do (some being more powerful than others).
11. You're the captain of a pirate ship and your crew gets to vote on how the gold is divided up. If fewer than half of the pirates agree with you, you die. How do you recommend apportioning the gold in such a way that you get a good share of the booty, but still survive?
    Offer each crew member two shares of booty for one share for the captain. Each crew member then feels that they're getting a good deal, while the captain will still get 1/3 the total booty.
12. 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 3 against 3; if they're even, weigh the last two. If the first weighing is uneven, take the heavy side and pick two balls to weigh; if even, the last ball left is the heavy one; if uneven, the heavier ball on the scale is the heaviest.
13. You are given 2 eggs. You have access to a 100-story 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 100th floor. Both eggs are identical. You need to figure out the highest floor of a 100-story building an egg can be dropped without breaking. The question is how many drops you need to make. You are allowed to break 2 eggs in the process.
    Assuming that eggs do not fatigue with dropping, then the most drops needed would be 50. Algorithm: take egg 1, drop from floor 50; if it does not break, drop from 75, then 87, then 92 (doing binary search to the top.) As soon as the egg breaks, switch back to the last level that didn't break the egg, then do linear search upwards from there. Worst case would be "survives fall of 49 stories"; the first egg would break on first drop, then second egg would need to linear search (1st, 2nd, 3rd...). If we knew more about the distribution of egg strengths, the upper bound of 50 could probably be reduced (at least in average case).
14. Explain a database in three sentences to your eight-year-old nephew.
    It's like Pokemon cards: each card talks about the creature on the card, and then there are rules that describe how the different cards work with each other.
15. 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?
    If I still had the same leg strength (and the lid is off!), jump out. Otherwise, crawl onto hub of blades and hold on tightly. (Alternately, see if I'm small enough to lie under the blades, but I worry about air currents in that case.)

Now to see how I did...

1. Golf balls: they came up with 500k, but that's pure volume (doesn't take packing into account -- cubic is probably not best for spheres, but hey..., same order of magnitude.
2. Seattle windows: Looks like "smart ass" was closer than most; they suggest a per-window fee (although I don't know how fair that is, given that skyscraper windows presumably cost much more to clean than ground-level ones do...)
3. Boys vs Girls: 50/50 is the right answer, although they approach it a bit differently than I did.
4. Piano Tuners: They do recommend Fermi estimation, and most of their numbers were very close to mine. They came up with 125 for Chicago (population 5M), so saying 200k piano tuners for a world population of 6G is not bad. (I intentionally lowballed the world population in my estimate, to reflect for high-population but low-per-capita-wealth nations such as India and China.)
5. Manhole Covers: "Doesn't fall through". Boooorrrrring.
6. Evacuate San Fran: They claim it's more of a "how to ask for more information about the problem" problem, but other than possibly saying that some routes are unavailable, I'm not sure how ambiguous "evacuate" is.
7. Overlapping Clock Hands: They say 22 times, but they don't count 24:00.
8. Dead Beef: Ha, I missed the answer they called "obvious but wrong": beef isn't beef until the cow is dead. (Well, maybe I struck a glancing blow with my smart-ass answer.) They elaborate on the hex answer, pointing out that it was specifically used for debugging on certain architectures.
9. Cars, Hotels, Fortunes: It's a Monopoly reference. Riiiight. I like the meteorite story better.
10. Bob's your [Stalker] Uncle: They suggest a whole protocol ("have bob call you"), which is very close to violating the exact terms of the question asked (which seems to imply that Eve must return the message). They do also mention checksumming (although without discussing ordering -- which I didn't mention specifically either, although I hinted at it with the "stronger than others" checksums).
11. Pirate Captain: They say: "You divide the booty evenly between the top 51% of the crew." I'm not sure I buy that, but ... it's odd. (I figured there was some sort of voting paradox thing going on there.)
12. 8 Balls: Exact same answer as mine.
13. Breaking Eggs: They definitely have a nicer lower bound than mine (14 vs 50). The trick is to keep track of the remaining precision that you still need to achieve with the second egg; they suggest dropping at 14, then 27, then 39, then 50, etc; whenever the first one breaks, you always have 13-n drops left, for a worst case of 14. So I totally botched that one.
14. 8-yo Database Admin: Boo, hiss, boring answer.
15. Nickle-Sized: They say it's pure creativity, and suggest breaking the motor. Hello? From inside the blender? With what tools, what leverage? That might be creative, but doesn't seem like it'd work all that well...

Overall, I give myself about 11/15 (with most of those being "0.5 for near miss").

Edit 2009-12-06 02:29Z: 12"/1.5" is 8, not 6...