Qualcomm Interview Question Software Engineer / Developers
try from floor then 20 then 30 then... till 100
and start from previous mark when the 1st ball broke, +1 floor at time.
worst case: if nth floor is 99 the. Number of drops would be 20.
Can any one suggest a better method?
No (there's a lower bound). The method below is garbage because if the first ball breaks on floor 50, then you have to do a linear search starting at floor 2, which takes a long time.
The maximum drops is 14.
take it as n(n+1)/2 is just greater than or equal to 100.so n=14.
Algo:
i=14,j=13
1.drop the ball from ith floor
if ball breaks then
drop ball from (i-j)th floor and then go one floor up and keep droping(until req floor is found)
else
i=i+j
j--
if(j>=1)
goto step 1.
According to this formula max would be 20, which is when break occurs on 97th floor, since 7*14 for first 7 tries till it breaks on 98th plus next 13 tries from 85th to 97th.
No. The number of drops is still 14.
The strategy should be, drop it first at the kth floor. Next at the (k+(k-1))th floor, then the (k+(k-1)+(k-2))th floor...
According to this strategy, you should drop it as follows:
14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, ... (102, 104 and 105)
In this way, even if the ball breaks first at floor 99, you would require only 11 + 3 (floors 96, 97 and 98).
drop the ball at the interval of SQRT(n).
if n = 100 , drop at floors 10, 20,30 etc upto 100.
The ball shd break at one of those drop.
if the ball breaks at floor 60 and does not break at floor 50 then the floor must be within 50 and 60. so start a linear probe from floor 50 until you find the exact floor where the ball breaks.
Harish's method is correct. Here is how to prove.
Supposed the interval is x, trial number is y. This question is equivalent to find the minimum value of y in this equation : y = x + 100/x where x[1,50].
since x and 100/x are continuous function in [1,50]. so the min value occurred when the derivative is 0: y'=1-100/x^2 = 0 which x = 10.
Fuzz's answer is the correct one. This is why:
- Sandeep Mathias June 02, 2012Consider that the MAXIMUM number of drops is k, for an n floor building.
Now, if we drop the ball, from the kth floor, and it breaks, we require at most k-1 drops of the second ball to find out which floor the balls break. If the ball, does not break, we next drop the ball, from k+(k-1)th floor. If the ball breaks, we require k-2 drops to find out which floor the ball breaks on. Hence, we get the height of the building as
H <= k + (k-1) + (k-2) + (k-3) ... + 2 + 1, which is sigma n.
Hence, H <= k*(k+1)/2.
Hence, the number of drops is 14. You cannot get better than this.