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 8, 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 8, 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 8, 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 8, 2004 The solution is not so trivial. http://www.techinterview.org/Solutions/fog0000000143.html JHY Wednesday, December 8, 2004 Damn...  I guess I'm not hiring material. zekaric Thursday, December 9, 2004 It's similar to a binary search. You can determine the floor in log2 (100) = 7. naveed Tuesday, December 21, 2004   Fog Creek Home