by **JC**, published: 2012-10-08 10:17 viewed: 6387 times

想了解更多的美国生活窍门？请订阅: **JC写的剑知北美生活快报。**

There is a 100-story building and you are given two eggs. The eggs (and the building) have an interesting property that if you throw the egg from a floor number less than X, it will not break. And it will always break if the floor number is equal or greater than X. Assuming that you can reuse the eggs which didn't break, you need to find X in a minimal number of throws. Give an algorithm to find X in minimal number of throws.

Here is the main point of this problem. If you broke one egg, you will need to do a linear search to find the floor. So you pretty much have to go from the lowest to the highest, and the worst is the total number of floors in the linear search with the second egg plus the drops you have done with the first egg.

So the whole question grinds up to how to make use of the first egg to reduce the linear testing using the second egg.

This problem can be solved by thinking backwards from the answer. So, here are the steps:

1. Take N for the answer

2. The best choice will be to start with floor N first.

- if the egg breaks, do a linear search starting from 1 to N-1, guaranteeing a solution in N attempts.

- else go to N + (N-1) floor.

3. Continuing in this way, with N attempts, we can cover sum(N + N-1 + N-2... 2 + 1) floors.

Thus we will need to cover 100 floors, so N *(N + 1) / 2 > 100

N = 14, so the answer is 14 maximum drops and we can find the floor.

The computer algorithm would be like this. Drop first egg from floors 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100... (i.e. move up 14 then 13, then 12 floors, etc) until it breaks (or doesn't at 100).

Lastly, to prepare for algorithm/data structure interviews, here are some books I would highly recommend, if you can read them all in detail, you are gold in getting any jobs at Google/Amazon/Microsoft/Facebook/Twitter, etc. or any software company:

My Recommendation On Algorithm Interview Books

Here is the main point of this problem. If you broke one egg, you will need to do a linear search to find the floor. So you pretty much have to go from the lowest to the highest, and the worst is the total number of floors in the linear search with the second egg plus the drops you have done with the first egg.

So the whole question grinds up to how to make use of the first egg to reduce the linear testing using the second egg.

This problem can be solved by thinking backwards from the answer. So, here are the steps:

1. Take N for the answer

2. The best choice will be to start with floor N first.

- if the egg breaks, do a linear search starting from 1 to N-1, guaranteeing a solution in N attempts.

- else go to N + (N-1) floor.

3. Continuing in this way, with N attempts, we can cover sum(N + N-1 + N-2... 2 + 1) floors.

Thus we will need to cover 100 floors, so N *(N + 1) / 2 > 100

N = 14, so the answer is 14 maximum drops and we can find the floor.

The computer algorithm would be like this. Drop first egg from floors 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100... (i.e. move up 14 then 13, then 12 floors, etc) until it breaks (or doesn't at 100).

Lastly, to prepare for algorithm/data structure interviews, here are some books I would highly recommend, if you can read them all in detail, you are gold in getting any jobs at Google/Amazon/Microsoft/Facebook/Twitter, etc. or any software company:

My Recommendation On Algorithm Interview Books

1. visitor 2011-03-26 04:59

The solution to this problem is sort of tricky. Well, for someone who see it for the first time. This is a classical problem. It used to be a Goldman Sachs interview question.
2. Morten Lærkedal 2011-10-29 12:59

And what if you have 3 eggs ?
3. JC 2011-10-30 22:57

In fact, I need to think twice again. If there are 3 eggs, then you probably would need less than 14 tries...
4. JC 2011-11-03 23:11

@Morten,With 3 eggs, you could use the extra egg for binary divide-and-conquer. Here is my thoughts:

1) Use the first egg to drop from floor 50. The worst case is it will be broken.

2) Now we try with the remaining 2 eggs, for floor 1 to 49, using the same algorithm above.

N *(N + 1) / 2 > 49, so N = 11. Since we already used one egg in 1), so, the maximum drops would be 12.

So, with 3 eggs, it is slightly better than 2 eggs. It seems there is a diminishing return on using more eggs.

Overall, in terms of solving a computer science problem, certain optimization is better, but too much would be overkill.

5. Martin Matuska 2012-10-08 06:38

Using your floors 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100 gives a maximum of 14 drops and a average of 9.47 drops. The probabilities of hitting specific drop numbers are:

1: 1%

2: 2%

3: 3%

4: 4%

5: 5%

6: 6%

7: 7%

8: 8%

9: 9%

10: 10%

11: 11%

12: 12%

13: 11%

14: 11%

But that gives a aggregated rounding error if you just round 13.67746 to 14 and then apply this rounding error to all next drops.

Lets see what better approximates give:

13.650971698085 ~ 14

26.30194339617 ~ 26

37.952915094255 ~ 38

48.60388679234 ~ 49

58.254858490425 ~ 58

66.905830188509 ~ 67

74.556801886594 ~ 75

81.207773584679 ~ 81

86.858745282764 ~ 87

91.509716980849 ~ 92

95.160688678934 ~ 95

97.811660377019 ~ 98

99.462632075104 ~ 99

100.11360377319 ~ 100

Now lets try to make a better distribution from these numbers:

14,26,38,49,58,67,75,81,87,92,95,98,99,100

Now we have still a maximum of 14 drops but our average has improved to 9.45 (about 0.3%). This is definitely closer to the "ideal" solution (which is impossible).

The probabilities of hitting specific drop numbers are:

1: 1%

2: 2%

3: 3%

4: 4%

5: 5%

6: 6%

7: 7%

8: 8%

9: 9%

10: 10%

11: 11%

12: 12%

13: 13%

14: 9%

A ideal solution with perfect distribution is possible only if number of floors is expressed as n*(n+1)/2 - e.g. for 14 drops it would be 105 floors.

6. JC 2012-10-08 10:17

@Martin,Wow, I am impressed with your detailed analysis. Let me read it first and understand a bit more. Thanks,

本文版权属于美国剑知信息网。如需转载，请先同我们联系。