Wed 28 Feb 2007
The puzzle “You have two hard eggs. But the question is ‘how hard are they?’ You have a 100 story building and only the two eggs, how would you find out which is the highest floor of the building you can drop the eggs from, before they break? It could be the 1st floor but it could also be the 99th floor—you must try dropping the eggs from different floors and see what happens. Your goal is to find the answer with the least number of egg drops.”
50th floor, worst case: egg 1: floor 50, 100 (break), then Egg 2: 51-99 : 2 + 49
25th floor, worst case: egg 1: floor 25, 50, 75, 100 (break), then Egg 2: 76-99: 4 + 24
10th floor: Egg 1: floor 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 (break), Egg 2: floor 91, 92, 93, 94, 95, 96, 97, 98, 99: 10 + 9 drops
a function which models this is:
f(x) = 100/x + (x-1), where x is a positive integer less than or equal to 100
to find the local minima of function f(x), take the derivative of f(x) and set it equal to zero
f’(x) = -100/x^2 + 1 = 0
x = 10
So f(x) has a minimum at 10, which is the optimal solution
[...] the egg drop solution [...]
but the variable x is the size of the interval.
when you say 10 is optimal solution, you are wrong
because the number of trial that leads from dividing into size 10 interval is 19.
there is a better solution which is 14.
FYI, the “better solution” is this:
Egg 1: 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99
Let’s say the egg broke on 77… so egg 2 would be:
Egg 2: 70, 71, 72, 73, 74, 75, 76
That was 7 drops for egg 1 and 7 drops for egg 2, which equals 14 total. A higher floor for egg 1′s break means less trials for egg 2, since we are narrowing the gap for egg 2 the higher we go. This caps the worst case scenario at 14.
In practice, I have a suspicion that 10 is a better solution… I think with the 10 solution, we are less likely to hit the worst case scenario and more likely to find the right floor sooner… so even if with the 14 solution we can guarantee that worst case trials is 14, best case trials might be less frequent than in the 10 solution… can anyone verify this?
Well, I wrote a Perl script to check your (Genius) assertion for the resulting floor being each one from 1 to 100. And here are the results:
diviser avg worst
1 50.5 100
2 26.49 51
3 18.82 35
4 15.22 28
5 13.26 24
6 12.1 21
7 11.44 20
8 11.02 19
9 10.9 19
10 10.81 19
11 10.9 19
12 10.9 19
13 11.02 19
14 11.37 20
15 11.44 20
16 11.8 21
17 12.1 21
18 12.25 22
19 12.7 23
20 13.26 24
21 13.3 24
22 13.54 25
23 13.98 26
24 14.62 27
25 15.22 28
26 15.25 28
27 15.4 29
28 15.67 30
29 16.06 31
30 16.57 32
While for your solution the corresponding numbers are:
10.35 14
Which is not too different from 10.81 avg for diviser=10.
Picture is here:
http://bt.pa.msu.edu/~poklonskiy/figure.png
p.s. I was asked this question during the interview at Microsoft yesterday and was able to come up with diviser=5 which gives 24 in worst case and 13.26 on average. But I was refining and I am confident I would’ve found minimum at 10. I was thinking there might be some other mechanism to divide floors into sub-sequences which are not equal, but was not unable to figure out that this should be such that
n_trials_to_find_subsequence + n_trials_in_subsequence = CONST
for all frames.
How many trailing zeros are there in 100! (100 factorial)?
100! = 93 326 215 443 944 152 681 699 238 856 266 700 490 715 968 264 381 621 468 592 963 895 217 599 993 229 915 608 941 463 976 156 518 286 253 697 920 827 223 758 251 185 210 916 864 000 000 000 000 000 000 000 000
There are 20 multiples of 5 from 1 to 100, which when multiplied by any of the 50 even numbers between 1 and 100, will produce a 10. Plus one extra one for 100, which is 2x5x2x5.
Plus three more:
25 = 5 * 5
50 = 5 * 5 * 2
75 = 5 * 5 * 3
which makes 24
src: http://discuss.joelonsoftware.com/default.asp?interview.11.319968.3
problem: four people are on this side of the bridge. the bridge will be destroyed by a bomb in 17 minutes. everyone has to get across before that. problem is that it’s dark and so you can’t cross the bridge without a flashlight, and they only have one flashlight. plus the bridge is only big enough for two people to cross at once. the four people walk at different speeds: one fella is so fast it only takes him 1 minute to cross the bridge, another 2 minutes, a third 5 minutes, the last it takes 10 minutes to cross the bridge. when two people cross the bridge together (sharing the flashlight), they both walk at the slower person’s pace. can they all get across before the bridge blows up?
person A: 1 minute
person B: 2 minutes
person C: 5 minutes
person D:10 minutes
solution: of course its possible, otherwise it wouldn’t be a very interesting question. the only trick is in realizing that you want to get the two slowest people across together, because otherwise you are wasting too much time. but then once you get them across, how do you not make one of them walk back with the flashlight? well, you just have one of the fast people already there waiting to sprint the flashlight back across.
1. A & B cross. total time: 2 minutes.
2. B comes back. total time: 4 minutes.
3. C & D cross. total time: 14 minutes.
4. A comes back. total time: 15 minutes.
5. A & B cross. total time: 17 minutes.
another solution which is valid is to have A bring the flashlight back in step 2. it only changes the solution slightly. this is supposed to be a “classic” microsoft interview question but it seems absurdly easy to be a good interview question (especially coupled with the fact that everyone has probably heard it already).
src: http://www.techinterview.org/Solutions/fog0000000106.html
there is a better way!!!
- Drop the first egg at floors 14,27,39,50,60,69,77,84,90,95,99,100
- when the first egg breaks, drop second egg in the range of floors underneath the floor between the previously tested floor and the floor
at which the first egg breaks.
eg. if first egg breaks at 77 then test range of floors 70 to 76
When the second egg breaks, the floor beneath is the highest floor you can drop the eggs safely without the egg breaking.
The maximum number of drops is 14 with this method.
Why begin at 14? 14 is the last number in the arithmetic progression
1+2+3+4+5+6+7+8+9+10+11+12+13+14 which just exceeds 100.
The next floor is 14 + 13 = 27
The next floor is 27 + 12 = 39
The next floor is 39 + 11 = 50
,etc,etc,etc
src: http://www.sitepoint.com/blogs/2006/06/10/a-googlish-puzzle/#comment-32211