>>>>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.
If it's not broken, fix it until it is.
My Blog