Interview Questions And Answers 
-
There is a building with 100 floors (can be any positive integer). You have 2 light bulbs. They are special type of bulbs and you have only 2 of them. The specialty of the bulb is that they don’t break easily when dropped from a height. The idea is to find the minimum floor of the building from which the bulb would break. You need to suggest a solution which will take the least number of iterations (for the worst case scenario) to find the minimum floor from which the bulb breaks. Remember that the answer should be mathematically proven to give the minimum iterations. Also note that once you throw a bulb and it doesn’t break, you can automatically recall the bulb without going down the building to fetch it.
10,700 Views |
(48 votes, avg: 4.02)
Loading ...
Answers »
Our Sponsors
Our Sponsors
1) You can start the bottom of the building and keep throwing the bulb from every floor. This will use only 1 bulb. In this scenario the worst case is if the bulb breaks on the 100th floor for which you would have done 100 iterations.
2) You can throw from a fixed interval let say every 10 floors. So if the bulb doesn’t break from the 40th but breaks at the 50th floor, you can use the second bulb to check from 41st to 49th floor iteratively to get the minimum floor from where it breaks. Here the worst case if the bulb breaks at the 99th or 100th floor for which you would have done 19 iterations. But in this case how do you know 10 is the fixed interval size which will give you the least number of iterations.
The first bulb should be thrown at fixed intervals of 10 floors until it breaks (10, 20, 30,…). If the bulb breaks, the second bulb should should be used to check all the floors between the floor it broke at and the previous interval. So if it broke at floor 40, floors 31 to 39 should be checked.
Proof: Assume X is the size of the fixed interval (in my answer it is 10). Then the most number of iterations that will be done: x+100/x
Want to minimize x+100/x.
Let f = x+100/x
f’ = 1-100/x^2
Minimum occurs when f’ = 0 => 0 = 1-100/x^ => x = 10
Therefore, interval of 10 should be used.
Both answers are unfortunately wrong, because they assume a fixed interval size. The right answer is as follows:
The interval size must decrease by one with increasing tries, since one try less is available. This way the number of
trials is much better distributed.
For example, if we start with the 15th floor, if the bulbs not breaks, the next one is the 29th, then the 42th and so on.
Now we only have to determine the optimal starting floor(
and thus the initial interval).
We have to calculate
min (sum(i= 0 to n) i >= 100), n an integer
n
min (n*(n+1)/2 >= 100)
n
n = 14.
Thus one throws the first bulb till it breaks from the floors
14,27,39,50,60,69,77,84,90,95,99,100, and the second one from the last floor level before breaking in 1-storey steps.
The worst number of trials is 14 (much better than the 19
iterations in the answers above).
I have an objection to the above answers..
let’s say the 8th floor is the minimum. In this case, the 10 floors method takes 1+8 = 10 throws.
The 14 floors solution takes 1+8 = 10.
Here’s my strat,
Throw bulb no. 1 (B1) from every (3*n)th floor where n runs from 1 to 33(in this case).
If B1 breaks on the 3rd floor, try B2 on the first floor. If B2 breaks on the first floor then we are done, else floor 2 is the answer.
If B1 breaks on floor 6 (remember only 3*n floors are being considered for B1), try B2 on the 4th floor (i.e. (3*n -2) for the nth iteration). If B2 breaks on 4th we are home, else floor 5 is the answer.
So, if floor 8 is the answer, I’ll try B2 on 3,6,9 and I’ll use B1 on floor 7.
This takes only 4 iterations.
But, the above solutions beat this approach when the destiny floor is higher up in the skies.
My conclusion: The best approach must incorporate a way of guiding the search towards an answer. Right now, we are just sweeping across without a map.
Using Fibonacci search is the best way to find the solution. This method is faster than traditional binary search algorithms, with a complexity of O(log(x))
I think that bulb should be dropped from half height
like if total 100 floors are there then drop it from 50 floor, if it breaks take second bulb drop it from lower half i.e. 25 floor else if it won’t break drop from 75 floor and by taking average again repeat same procedure
IT’S disadvantage is it will take more number of bulbs but number of iterations will be least
The worst case of 14 is not accurate, the worst case will be 15 in that case. If the bulb breaks in 14th floor then we need 15 tries. First try at 15th the first bulb breaks, then we will start with second bulb from 1st floor until 14th, so we need worst case scenario of 15 tries.
this is similar to a binary search algorithm. if there are 100 floors, throw from 50 th floor.if it does not break, continue in the upward direction to throw from (the median of 100 and 50-tat s 75) else,if bulb breaks,continue with 25 th floor, repeat the same for each of the iterations..
This problem can be solved using Divide-and-Conquer method and Minimization method.
If 100 floors re divided into k sub-groups then the number of tries needed are 100/k+k-1
d/dk(100/k+k-1) = 0
=> -100/k^2 +1 = 0
=> k = 10
Number of iterations = 100/10 + 10 -1 = 19.
Throw from 25 ——->
if it breaks … next one you can try 1 to 24 turns
Worst case 24 + 1 = 25———-(1)
if it does not break on 25 go to 50 ——–>
if it breaks … next one you can try 50 to 25 turns
Worst case 24 + 1 = 25———-(1)
Similary 75 and 100 in steps of 25.
Therefore worst case you will find in 25+3 =28 turn.
Leave an Answer/Comment