Cracking The Coding Interview/Q 6.5

From Software Engineers Wiki
Jump to: navigation, search

There is a building of 100 floors. If an egg drops from the Nth floor or above, it will break. If it's dropped from any floor below, it will not break. You're given two eggs. Find N, while minimizing the number of drops for the worst case.

Answer

If there were infinite number of eggs, we may try binary search. But we have only two eggs. Once the first egg is broken, we can only do linear search with the second egg.

If the first egg is dropped from floor F1 and gets broken, we can do a linear search with the next egg for F1-1 floors. We want to minimize number of drops in the worst case. For each drop, we go up by Fn floor.

  • egg1 gets broken on first drop: 1 + (F1 - 1) drops
  • egg1 gets broken on second drop: 2 + (F2 - 1) drops
  • egg1 gets broken on third drop: 3 + (F3 - 1) drops

If we make F2 = F1 - 1 and F3 = F2 - 1, then we get the same number of worst case drops regardless when the egg gets broken. So this becomes

1 + (F1 - 1) + (F1 - 2) + (F1 - 3) + ... >= 100

For 100 floor building, F1 is 14, with worst case drop of 14 times.

Reference

Personal tools
Namespaces

Variants
Actions
Navigation
Toolbox