Interview Question for Software Engineer at Facebook:

Start moving up in increments of 10 floors and dropping the bulb until it breaks (ie: drop from floor 10, if it doesn't break, drop from floor 20, etc.). Once the bulb breaks, move down to the floor above the last floor it broke on and start moving up floors in increments of one until the second bulb breaks. This results in a worst case scenario of 19 drops.

Surely a binary search method would be more efficient i.e. starting at 50 and either going up or down 25 floors based on if it breaks or not.

If you do a binary search, what happens if it breaks at floors 50 and 25?

Do you know what a binary search is?

You drop it from floor 12 next. If it breaks, you know it breaks between floors 12 and 1, inclusive. If it doesn't, you know it breaks between floors 13 and 25, inclusive.

The main principle of binary search is that with each step you reduce your search space in half. Now your search space consists of only 12 floors.

Wow, I want to get asked such a question in an interview!

>>you drop it from floor 12 next...

if you broke it on 50 and 25... you are out of luck and out of bulbs...

19 drops is not the best worst case scenario... imagine trying floor 16, if it breaks, you try 1 - 15 and thats 16 tries.

if it doesn't break, then try floor 31 and if it breaks, then try 17 - 30 (so 16 tries, including the try on floor 16).

And on and on (45, 58, 70, 81, 91, 100). If you reach 91, you'll have tried 7 floors so far and if it doesn't break, then there's 9 more tries to get to 100 (thus 16 in the worst case)

This post has been removed. Please see our Community Guidelines or Terms of Service for more information.

This post has been removed. Please see our Community Guidelines or Terms of Service for more information.

first do a binary search (agressive first step - fast) with 1 bulb.
when first breaks, you know X(last but one fall - success) and Y(last fall - failure).

now do a linear search starting from X(conservative but accurate second step - slow).

complexity = in between logN and N.

Use Binary search starting with the middle 50
The complexity of binary search is logN . So it will be log(100) < 7.

Based on my experience, I think it will be floor 1 itself .

Drop from 1st floor. If it didn't break, drop the same bulb from 2nd. If it still didn't break, drop the same bulb from 3rd... repeat as necessary. Only one light bulb required :)

Yes, but doing each floor, that will give you the most drops -- question relates to optimizing for "least" number of drops -- I didn't think about being able to re-use the bulbs...that obviously is helpful. Maybe a fibonaci sequence once you determine a "break" floor and a "non-break" floor. I'd probably fail completely at coding it...knowledge of optimization and prediction theory would certainly be useful.

Let f(m,k) be number of tries for m lamps and k floors. Obviously f(1,k)=k. let f(2,k) be s. k<=(s-1)+(s-2)...(1) =s(s-1)/2. Therefore f(2,100)=15.

Actually, 16 is not the optimal, nor is 15; you can do it in 14. Here is one solution (there are at least 5 other equivalents):

* Drop first bulb at 14th, 27th, 39th, 50th, 60th, 69th, 78th, 85th, 91st, 96th, and (optionally) 100th until it breaks.
* Go to the highest floor where the first bulb didn't break.
* Repeatedly go up one floor and drop the second bulb. When it breaks, you have your answer.

Why is 14 optimal? Since you are decrementing each time, you want (n) such that sum(1..n) barely reaches 100. The answer is n=14. Generally, if the number of floors is (f), the lowest number of drops is ceil((sqrt(8*f+1)-1)/2).

This is the best worst-case scenario. An interesting related question is what gives the lowest expected number of drops.

And no, I could not have gotten this in an interview.

In theory, use one bulb to determine an interval, and use the second bulb for a linear search within the interval. The solution that decreases the interval by one for each trial is quite clever.

In practice, however, take the nature of the problem into account: Start on the first floor and move up by one floor. That's the answer I would be looking for.

Start with bulb 1 and drop it from floor 2.
Doesnt break? then floor 4
Doesnt break? keep dropping the same bulb moving even number of floors all the way upto floor 100.

If on some even floor the bulb breaks drop the second bulb from the odd floor below the even floor, to detect if its the even or the odd floor that breaks the bulb

Best case detection: 2 tries (first bulb breaks on 2nd floor, second bulb breaks on 1st floor)
Worst case: 51 tries (the fist bulb breaks at 100 and second bulb breaks or does not break at 99th floor.. )

Go to the 100th floor and drop the first bulb. It WILL break. Done, 1 drop. It doesnt say whats the lowest floor it will break at, just at what floor will it break with least drops. Thus floor 100.

Alright guys...you have two light bulbs. ...the second one has to be used for linear search, let the worst case number of items to be searched be x, then your interval will also have to be x, which will result a worst case of 100/x drops for the first light bulb. So now you are just trying to minimize n=100/x+x, find n'=0 when x=19...the candidate's answer is correct.

I meant...x=10. and n=19.

0 drops, 1 bulb......stop thinking like computer nerds. Use physics or an engineering mindset.

They didn't prohibit the use of any tools.
Grab a scale, figure out force req'd to fracture bulb. Calculate acceleration due to gravity adjusting for air resistance/barometric pressure at location (trivial for anyone who took a 1yr physics course). Figure out how many meters up you need to be based on the req'd acceleration. Done....

@Rich: I am sure they were hoping for you to give them a computing answer since they don't do physics, and rather do computer science.

mer's answer is correct: 14.

Let F(s, n) be the optimal worst-case number drops for s stories and n bulbs.

Suppose we drop at floor f, constituting one drop. If it breaks, we must make up to F(f-1, n-1) drops. If it doesn't break, we must make up to F(s-f, n) drops. Thus, for a given floor f, we have up to 1 + max { F(f-1, n-1), F(s-f, n) } drops. Optimizing over f:

F(s, n) = 1 + min{ max { F(f-1, n-1), F(s-f, n) } for f in 1..s}

Using the appropriate base cases, we have F(100, 2) = 14, as mer has given.

Another way to think about it is in terms of decision trees. We want to construct a binary decision tree with leaf nodes for floors 1..100, and at most one "left" turn per path from root to leaf. To minimize the height of the tree, we want to reduce the variance in the length of each root-to-leaf path. This suggest we try dropping the first bulb at floors of the form: a, a-1, a-2, .. a-b, where the sum a + (a-1) + .. + (a-b) is equal to or barely over 100, so that determining almost any floor (possibly excluding the top few) takes a drops. Using this approach, we get the sequence of drops that mer has suggested.