4 ms·

I was asked this question in a google interview earlier this year. Neither I nor the interviewer got past the "every 10 floors" approach (though I did make it t

I was asked this question in a google interview earlier this year. Neither I nor the interviewer got past the "every 10 floors" approach (though I did make it through that round of interviews!). Interesting to see there was more meat on that bone.

tomp 14y ago
I think that "every 10 floors" approach is optimal for average case. Basically, E(number of drops) = E(number of drops for 1st egg) + E(number of drops for 2nd egg). We know that E(number of drops for 2nd egg) = 1/2 the difference between two drops of the 1st egg, and E(number of drops of 1st egg) = 1/2 the number of intervals, and 100 = the number of intervals × the difference. So, we're minimizing x + y, knowing that x × y = 100. Since the problem is symmetric, x and y must be equal, namely 10, so "every 10 floors" is the correct answer.
- numlocked 14y ago
  Actually there's a slight optimization available. Why ten floors? Because basically what we are doing is establishing a most significant digit - the tens place, then the ones place. This works because 100 is a square number (10*10). But what if there were 64 floors? Then, to do the same thing (but in base 8), we'd drop every 8 floors. We can account for this as we drop by treating all floors above as a fresh tower and rounding to the nearest square number: Drop on floor 10 (90 floors remain - 81 is closest square, so now only go up 9 floors), drop on 19 (81 floors remain, go up 9 again), drop on 28 (72 floors remain, 64 is closest square, go up 8), etc, etc.
- philh 14y ago
  This seems to be false: eggs :: [Int] -> Int -> Int eggs drops floor = if floor >= last drops then (length drops) - 1 else let numless = length $ filter (<= floor) drops below = last $ filter (<= floor) drops above = head $ filter (> floor) drops in numless + (floor - below) + (if floor + 1 == above then 0 else 1) sum $ map (eggs [0,10 .. 100]) [0..100] -- returns 1100 sum $ map (eggs [0,14,27,39,50,60,69,77,84,90,95,99,100]) [0..100] -- returns 1047 (Not 100% confident that I haven't made a mistake. You pass "eggs" a list of floors to drop the first egg on, and the lowest floor that the egg will survive being dropped from. It returns the number of drops it takes to discover that value. The list needs to start with 0 because that requirement simplifies the function slightly. But if I haven't made a mistake, "10, 20, 30..." takes an average of 10.9 drops and "14, 27, 39..." takes an average of 10.4. That's assuming the floor is uniformly distributed between 0 and 100 inclusive.)
- thaumasiotes 14y ago
  > E(# of drops) = E(# of drops for 1st) + E(# of drops for 2nd) In the general case, I don't think this is true. I think you're relying on the idea that all intervals are equally large. But I'm not definite here. > E(# of drops for 2nd) = 1/2 the difference between two drops of the 1st egg Sure, but this depends in a nasty way on your schedule for dropping the first egg. > E(# of drops of 1st) = 1/2 the number of intervals This is definitely wrong. Say my schedule for dropping the first egg is [1, 2, 3, 100]. On your analysis, the expected number of drops the first egg will take to break is 1.5. If we assume that the egg's breaking threshold is uniformly distributed over floors 1-100, the actual expectation for drops-to-break-the-egg is 3.94. > 100 = the number of intervals × the difference True for the average difference, but this is pretty explicit about assuming that the size of an interval is constant.
  - lotharbot 14y ago
    >> "E(# of drops) = E(# of drops for 1st) + E(# of drops for 2nd)" > "In the general case, I don't think this is true. I think you're relying on the idea that all intervals are equally large." Pretty much. More explicitly, the grandparent is relying on the assumption that E(egg2) is independent of what happens to egg1, which is only true if the interval sizes are the same. In the article's solution, E(egg2) is dependent upon which interval egg2 is dropped in -- if egg1 breaks on the first drop, E(egg2)=7 (the center of the 1-13 interval) but if egg1 breaks on floor 100, E(egg2)=0 since we already know floor 99 is safe. To calculate E(egg1 + egg2) we need to compute something resembling a weighted average. A quick-and-dirty excel chart gives me an expectation of 9.97, whereas intervals of size 10 give an expectation of 10.5 (first egg gets 1-10 drops for an expectation of 5.5; second gets 1-9 drops for an expectation of 5.0 as the tenth drop would be a repeat.)
mhartl 14y ago
I predict that the overwhelming majority of people who correctly solve this problem under interview conditions have seen it before.

tomp 14y ago

I think that "every 10 floors" approach is optimal for average case. Basically, E(number of drops) = E(number of drops for 1st egg) + E(number of drops for 2nd egg). We know that E(number of drops for 2nd egg) = 1/2 the difference between two drops of the 1st egg, and E(number of drops of 1st egg) = 1/2 the number of intervals, and 100 = the number of intervals × the difference. So, we're minimizing x + y, knowing that x × y = 100. Since the problem is symmetric, x and y must be equal, namely 10, so "every 10 floors" is the correct answer.

numlocked 14y ago
Actually there's a slight optimization available. Why ten floors? Because basically what we are doing is establishing a most significant digit - the tens place, then the ones place. This works because 100 is a square number (10*10). But what if there were 64 floors? Then, to do the same thing (but in base 8), we'd drop every 8 floors. We can account for this as we drop by treating all floors above as a fresh tower and rounding to the nearest square number: Drop on floor 10 (90 floors remain - 81 is closest square, so now only go up 9 floors), drop on 19 (81 floors remain, go up 9 again), drop on 28 (72 floors remain, 64 is closest square, go up 8), etc, etc.
philh 14y ago
This seems to be false: eggs :: [Int] -> Int -> Int eggs drops floor = if floor >= last drops then (length drops) - 1 else let numless = length $ filter (<= floor) drops below = last $ filter (<= floor) drops above = head $ filter (> floor) drops in numless + (floor - below) + (if floor + 1 == above then 0 else 1) sum $ map (eggs [0,10 .. 100]) [0..100] -- returns 1100 sum $ map (eggs [0,14,27,39,50,60,69,77,84,90,95,99,100]) [0..100] -- returns 1047 (Not 100% confident that I haven't made a mistake. You pass "eggs" a list of floors to drop the first egg on, and the lowest floor that the egg will survive being dropped from. It returns the number of drops it takes to discover that value. The list needs to start with 0 because that requirement simplifies the function slightly. But if I haven't made a mistake, "10, 20, 30..." takes an average of 10.9 drops and "14, 27, 39..." takes an average of 10.4. That's assuming the floor is uniformly distributed between 0 and 100 inclusive.)
thaumasiotes 14y ago
> E(# of drops) = E(# of drops for 1st) + E(# of drops for 2nd) In the general case, I don't think this is true. I think you're relying on the idea that all intervals are equally large. But I'm not definite here. > E(# of drops for 2nd) = 1/2 the difference between two drops of the 1st egg Sure, but this depends in a nasty way on your schedule for dropping the first egg. > E(# of drops of 1st) = 1/2 the number of intervals This is definitely wrong. Say my schedule for dropping the first egg is [1, 2, 3, 100]. On your analysis, the expected number of drops the first egg will take to break is 1.5. If we assume that the egg's breaking threshold is uniformly distributed over floors 1-100, the actual expectation for drops-to-break-the-egg is 3.94. > 100 = the number of intervals × the difference True for the average difference, but this is pretty explicit about assuming that the size of an interval is constant.
- lotharbot 14y ago
  >> "E(# of drops) = E(# of drops for 1st) + E(# of drops for 2nd)" > "In the general case, I don't think this is true. I think you're relying on the idea that all intervals are equally large." Pretty much. More explicitly, the grandparent is relying on the assumption that E(egg2) is independent of what happens to egg1, which is only true if the interval sizes are the same. In the article's solution, E(egg2) is dependent upon which interval egg2 is dropped in -- if egg1 breaks on the first drop, E(egg2)=7 (the center of the 1-13 interval) but if egg1 breaks on floor 100, E(egg2)=0 since we already know floor 99 is safe. To calculate E(egg1 + egg2) we need to compute something resembling a weighted average. A quick-and-dirty excel chart gives me an expectation of 9.97, whereas intervals of size 10 give an expectation of 10.5 (first egg gets 1-10 drops for an expectation of 5.5; second gets 1-9 drops for an expectation of 5.0 as the tenth drop would be a repeat.)

mhartl 14y ago

I predict that the overwhelming majority of people who correctly solve this problem under interview conditions have seen it before.