A)You are the manager of a light bulb factory that makes super strong light bulbs. You only have 2 light bulbs you can break. You want to know what floor the light bulb breaks on when dropped and you have a 100 story building... What is the minimum number of drops in the WORST CASE you can make?

B) Explain your answer.



[Edited on October 20, 2008 at 7:42 PM. Reason : a]

10/20/2008 7:33:24 PM

14

call tech. support

10/20/2008 7:34:52 PM

^^ you start from the bottom, and keep dropping the bulbs, assuming it won't break after being dropped from the first floor, you can just drop it, pick it up, drop it again. I'd probably just alternate which bulb I dropped to minimize any weakening effect.

But i'm pretty sure a bulb would break after being dropped from 1 story high.

10/20/2008 7:47:36 PM

You can do a lot better than 100 drops worst case. This is a classic computer science problem without getting into the physics of it. I'm curious to see Omar's solution if that is indeed his answer.



[Edited on October 20, 2008 at 7:59 PM. Reason : a ]

10/20/2008 7:58:26 PM

i think it's 51

[Edited on October 20, 2008 at 8:05 PM. Reason : i don't see what is has to do with computers though. common sense.]

10/20/2008 8:04:37 PM

^

Getting there but you can get better than that as well... Why 51?

[Edited on October 20, 2008 at 8:05 PM. Reason : a]

10/20/2008 8:05:24 PM

The WORST CASE is 1. You drop them both at the same time, they both break, you don't find the answer, and you are subsequently fired.

[Edited on October 20, 2008 at 8:06 PM. Reason : .]

10/20/2008 8:05:37 PM

Also, why is a manager doing QA?

10/20/2008 8:06:59 PM

you drop it at every other floor (50 drops max). when it breaks, you move down one step and see if it breaks at one lower than where it broke before (1 drop in worst case).

50+1=51

that's my reasoning anyway

10/20/2008 8:08:40 PM

19 for the same reason?

[Edited on October 20, 2008 at 8:13 PM. Reason : 10/20/30/40/50/60/70/80/90/100 + 9]

10/20/2008 8:11:12 PM

^couldn't that require more than two eggs?

10/20/2008 8:16:36 PM

No, but I don't remember if that's best

if the first broke on 100 but not 90 (part of the worst case) then you'd try the other one on 91 through 99 until it broke (so max 19 drops in the worst case of the 99th floor).

10/20/2008 8:17:51 PM

19 is a good answer but i went with 14

http://www.lateral.co.za/5mins/100106_5mins_Lightbulbs_puzzle.pdf

10/20/2008 8:20:11 PM

^^i see. i think there's a better solution because all you have to get to is floor 99


lemme calculate a second

[Edited on October 20, 2008 at 8:22 PM. Reason : start at 14 and go up by one less that that (ie. 13) then up by 12 and so on b/c that will give 99..]

[Edited on October 20, 2008 at 8:22 PM. Reason : ^yeah, that]

[Edited on October 20, 2008 at 8:22 PM. Reason : except google is weak]

10/20/2008 8:20:38 PM

Ahhhhhh yeah

10/20/2008 8:25:27 PM

limited length from the edit so here was how i thought of it:

if you assume the bulb has to break within 100 floors, you only need to get to floor 99. if it doesn't break there it breaks on floor 100.

the max number of drops (worst case) is the greatest step interval

start at 0 and do first drop on 14. go up by one less than you went up the previous time.

14+13+12+11+10+9+8+7+6+5+4 = 99

if you make it all the way to 99, you've dropped 11 times and have 3 more drops. conveniently there are 3 drops that haven't been tested between 95 and 99. 11+3=14

10/20/2008 8:30:45 PM

I got asked that in an interview. I got 19 then I got asked to code an example for 1 trillion floors with optimizations. Fun shit.

10/20/2008 8:37:53 PM