We are given two eggs, and access to a 100-story building. Both eggs are identical.
The aim is to find out the highest floor from which an egg will not break when dropped out of a window from that floor. If an egg is dropped and does not break, it is undamaged and can be dropped again. However, once an egg is broken, that’s it for that egg.
If an egg breaks when dropped from floor n, then it would also have broken from any floor above that. If an egg survives a fall, then it will survive any fall shorter than that.
The question is:
What strategy should you adopt to minimize the number egg drops it takes to find the solution?.
And what is the worst case for the number of drops it will take?
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
Answer:
14
x + (x-1) + (x-2) +...+ 1 = 100
Sigma(x) = 100
x*(x+1) / 2 = 100
x(x+1) = 200
x = 13.65
x = 14
Detailed answer:
http://datagenetics.com/blog/july22012/index.html
http://www.programmerinterview.com/index.php/puzzles/2-eggs-100-floors-puzzle/
The aim is to find out the highest floor from which an egg will not break when dropped out of a window from that floor. If an egg is dropped and does not break, it is undamaged and can be dropped again. However, once an egg is broken, that’s it for that egg.
If an egg breaks when dropped from floor n, then it would also have broken from any floor above that. If an egg survives a fall, then it will survive any fall shorter than that.
The question is:
What strategy should you adopt to minimize the number egg drops it takes to find the solution?.
And what is the worst case for the number of drops it will take?
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
Answer:
14
x + (x-1) + (x-2) +...+ 1 = 100
Sigma(x) = 100
x*(x+1) / 2 = 100
x(x+1) = 200
x = 13.65
x = 14
Detailed answer:
http://datagenetics.com/blog/july22012/index.html
http://www.programmerinterview.com/index.php/puzzles/2-eggs-100-floors-puzzle/
No comments:
Post a Comment