wilmott.com

You have two glass balls and a 100-story building. You would like to determine the lowest floor from which a glass ball will break when dropped. What is the strategy that will minimize the worst case scenario for number of drops? What is your strategy if you have 100 glass balls?

Nice question. I think the magical number here is 14.

Ok, now u want to minimize in expectation.

Man, I was asked this question on Tuesday evening!!!Sevvost, I think the number is 15 (1 + 14; (14)(15)/2 = 105) if you consider 0 as a valid solution.If you have 100 then you could use bijection (binary search); should be able to do it in 8...

Agree. My meaning was that if you know the ball breaks for sure, and only have one possibility left, that must be it. (Did you get it during the interview?)And speaking of binary search, shouldn't 7 be enough?

Yes sevvost I got it during an interview!!And you are right 7 should be enough for the binary search. As an engineer I tend to be conservative and add an extra 1; better be wrong and use up one extra resource, rather than having the code crash due to garbage memory access.

QuoteOriginally posted by: darkforceYou have two glass balls and a 100-story building. You would like to determine the lowest floor from which a glass ball will break when dropped. What is the strategy that will minimize the worst case scenario for number of drops?With only two balls you need to search more cautiously from the ground up to reuse the first ball. Start by dropping the ball from the 14th floor. If it does not break, drop the ball from the 27th floor (14+13). As long as no ball has broken, test at floors 39, 50, 60, 69, 77, 84, 90, 95, 99, and 100. (an number of modified arithmetic progressions also work). If the ball breaks, go down to the floor above the last floor that produced an unbroken drop and do drops floor by floor with the remaining unbroken ball. Sevvost is correct, the worst case scenario is 14 drops.