Microsoft Interview Question Software Engineer / Developers
u can do it in min. of 14 throws
throw the ball 1st ball from 14th floor if it breaks thn use other ball n start throwing starting frm 1st floor
if it doesn't break, thn throw the 1st ball from 27th, if it breaks thn start throwing other ball from 15th floor
and so on keep throwing 1st ball from 39th, 50th, 60th, 69th, 77th, 84th, 90th, 95th, 99th floor.
so even in worst case comparisions r 14
bansal.abhi is right.
Assuming the minimum number of throwing is x, we have to begin throwing from x floor. Then if the glass is not broken(worst case), to make the minimum throw x, we can only begin from x + (x-1) floor. Keep throwing until xth throwing, at this time, no floor should be left. So, we have x + (x-1) + (x -2) + ... + 2+1 >= 100. That is, x*(x+1)/2 >= 100. We can get minimum x = 14.
The solution to the above problem is as follows:
You have to divide the total no of floors into groups in such a way that the worst case never increases across the groups. For e.g. lets say u decide to have the first group as floors 1 to 14. In the worst case this will take 14 trials. Now you have to choose the second group if you choose the second group of the same size as of the first group then the worst case will have 15 trials. So you have to chose the next group with size less by one than the size of first group. So you will end forming groups of sizes 14,13,12----1 which is nothing but a series. So what should be the optimum size of the first group. That should be equal to the no. of groups you can divide all the floors into. With 14 groups you can include all the 100 floors. If you think of 13 as the solution then its not possible as you can not divide 100 floors in 13 groups and ensuring that each group size is less by one than the previous group.
Can't we try binary search? Throw the ball from the 50th floor. If it breaks try from the floor set below it an recurse, else throw from the floorset above it and recurse. Ultimately, you will find a floor at which the recursion terminates but the ball does not break. It neighbouring higher floor is the correct answer. This takes only O(logn) time
guys the solution is simple ...and the answer is 14. this is the old question...can some one explain me the generalized solution for this porblem i.e Say we have n eggs and d-floor building then in how many drops we can find the max floor...plz help!
Hey friends the answer is 14 bcoz the minimum "m" turned out to be 14 in m(m+1)/2 >=100
so if u have n eggs u can use them to divide the inetrval into 2 wid each egg until the last 2 eggs remain. with which u can use the above formula m(m+1)/2 >= d/(n-2) to find the minimum m. So the answer would be a maximum of m+n-2 eggs.
Plz correct if i am wrong.
:)
There are several strategies in solving this problem.
- VIgorous March 14, 2008But Throw the first ball every 10 stories gives the best minimum number of throws, it guranteen that within 20 times, the target story can be found.
Suppose every K floors we will throw the first ball,
the maximum throws needed is bounded by 100/K+K,
the minimum reaches when K=10.
Other strategies might be more powerful, but they can't promise a minimum number of throws.