Eggs problem

There's a building with 100 levels and you have two eggs. You can drop an egg from any level of the building to check whether it breaks or not. After it broke it is useless.

It is known that below a certain level eggs do not break and from that level up they always break.

The question is that which level it is? Tell me the minimum number of drops that will ALWAYS identify that level!

Generalization: N levels and k eggs...

levy

Levente Mészáros
Wednesday, December 08, 2004

int FindSafeLevel(void) {

  int a,
        level;

  for (level = 10; level <=100; level = level + 10) {

      if (EggDrop(level) == EGG_BREAK) {

        for (a = level - 9; a < level; a++) {

            if (EggDrop(a) == EGG_BREAK) {
              return a - 1;
            }
        }
        return level - 1;
      }
  }

  return 100;
}

So, at most 19 tests.  Minimum 10 tests.

Am I close?

zekaric
Wednesday, December 08, 2004

Generalization would be...

Square root the total levels and that will be your starting level.  Min will be the square root of the levels +/- 1 for integer rounding to a Max of  2 * Min - 1 give or take a level.

zekaric
Wednesday, December 08, 2004

I should clarify the minimum tests.  The minimum test for the local worst cases of the (multiples of 10) - 1.

Actually starting at level 9 and even 8 with a jump of 9 and 8 will yeild the same maximum tests as 10 but have a slightly larger average test count.

zekaric
Wednesday, December 08, 2004

The solution is not so trivial.

http://www.techinterview.org/Solutions/fog0000000143.html

JHY
Wednesday, December 08, 2004

Damn...  I guess I'm not hiring material.

zekaric
Thursday, December 09, 2004

It's similar to a binary search. You can determine the floor in log2 (100) = 7.

naveed
Tuesday, December 21, 2004

  Recent Topics

  Fog Creek Home