>>>>>>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.
Ok. I can not concentrate on this problem at work, may be that's the reason, I didn't find your solution by myself. The idea is that M could be variable, but I can not solve it without writing some algorithm...
If it's not broken, fix it until it is.
My Blog