>>>>>Hi everybody,
>>>>>
>>>>>This is a puzzle, which could be asked on a interview. I could not find a best answer.
>>>>>
>>>>>There is a 100 floor building. You have two glass balls. You need to find out the floor number, starting from which these balls will broke by minimal number of steps.
>>>>>
>>>>
>>>>What is definition of a step in this case?
>>>
>>>I think, one dropping of a ball is a step.
>>
>>Here's an idea. Split floors in N groups of M floors in each. Go up M floors at time and drop the first ball until it brakes. Go down to the privious drop floor + 1 and drop the second ball on each floor moving up until it brakes. The number of attemts in worst case would be
>>
>>maxnum = N + M - 1.
>>M = 100/N
>>maxnum = N + 100/N - 1
>>
>>All you have to do is to find minimum for this function. I guess it woud be N=10 and maxnum = 10 + 10 - 1 = 19.
>
>That's a good idea and a good algorithm. I felt so stupid, after my colleague explained this solution to me. Hovewer, this is not the best algorithm, though a very good one. People, who gave this solution, passed this interview successfully.
Let me know when you find out the best one.
--sb--