Interview Question for Engineering at QUALCOMM:

binary search

start at the top floor and work down toward the first floor to see on which floor the bulb breaks first

Start at the lost likely point based on your experience – the first floor -- and see if the bulb breaks when dropped. If not, then a test is warranted. Start at half way point and keep going up or down to the next halfway point until you determine the height. You should be able to determine the floor within 7 bulbs or fewer and – assuming each floor is 10 feet high, you should be able to determine the exact height in feet within another 5 bulbs or fewer. The greatest number of bulbs you could break to reach the answer would be 12, plus the one for the initial test = 13 total.

In my interview at Apple, this question also stated:

"You will get a bonus of $1000 for each remaining glass bulb after the test. What is the highest bonus you can absolutely guarantee, and with what algorithm?"

The interviewer told me that he only had it answered correctly once, and that person had a master's degree in pure mathematics. The candidate explained the theory behind the answer using lots of appropriately mathematical terms.

The long-winded, logic-based solution to prove that you can earn an $18'000 bonus goes as follows:

• If you drop a ball from floor X and it shatters, you will need to drop the other from floors 1 to x-1 in that order to find out the lowest floor at which the ball would break.
• Therefore, if you started at floor 20 and the ball shatters, you have to drop the other from 1 to 19 to see at which that one will shatter.
• If it shatters at floor 19, your bonus is all gone (you're performed 20 drops, losing $20'000 from your bonus).
• If the ball does *not* shatter at floor 20, then you might try again at floor 40, but then you'd only have 18 drops left— if it broke at 40, but not at 38 (when you've used all your drops) you don't know if 39 or 40 was the breaking-point.
• Therefore, after trying 20, you go up 19 floors to 39 and try again there.
• You repeat, going up 18 floors to 58, then 77, then 86, etc.
• However, this isn't optimized. You can't *guarantee* a bonus by stepping up by [20 19 18 …], since you could conceivably deduce the amount only using a full 20 drops.
• Therefore we look at how we can divide up our 100 floors by a descending sequence:
    • 10 + 9 + 8 + … = 55 => No Good.
    • 11 + 10 + 9 + … = 66 => No Good.
• Try going the other way; starting at 1 and counting up (sort of like the Fibonacci sequence), at which point do we pass 100?
    • 1 + 2 + 3 + 4 + … + 12 + 13 + 14 = 105.
• Therefore, we can start dropping the ball at floor 14 using the algorithm above, and still have enough drops to determine the exact floor at which the ball breaks, even should it be floor 99 or 100.
• Using 14 as a base, this means that the *maximum* number of times we will drop the ball is 14 times, while still guaranteeing that we drop at $BREAK_HEIGHT and $BREAK_HEIGHT-1.

Therefore, the correct solution can be calculated using only two glass balls, a maximum of two of which will smash, guaranteeing us a bonus of $18'000.

QED :o)

Only one light bulb is needed.
Start at floor level, drop it, and if it does not brake USE THE SAME BULB for next trial higher up until the very same bulb brakes.

One light bulb is not sufficient because even if it does not break, after one drop, it will become more fragile, thus may break at a lower floor than a new bulb. Thus a different bulb should be used for each drop.

BTW, there is a closed formula giving the maximum number f of floors for which one can find the height with a given number b of bulbs and a given number w of bulbs that can be broken (and the algorithm can be deduced at the same time). This is probably a well-known combinatoric problem.

If the balls do not weaken, then one ball is sufficient and the guaranteed bonus is $19,000. If a different ball is required for each drop, then binary search will find the height of breakage with 7 drops or less (2^7 = 128 > 100), so the guaranteed bonus is $13,000. I believe it can be proven that you can't guarantee better than this.

Take the stairs...

1. the question does not say they break when you drop them, it could be air pressure. The question needs clarification
2. the question does not say the bulbs are all the same

The question was about light bulbs not about the building or its height. I would get $19000. Take a bulb hold it ,say, 1 inch above a hard surface. Drop it. If it does not break try 2 inches keep adding a inch until it breaks.
Nothing was said about testing it from a floor.
I could also drop it on a very soft surface and if soft enough make the $20000.
Sometimes we think too much. You were misdirected.

Take the elevator or walk up the stairs with just 1 light bulb. Once it breaks, check the floor number in the elevator or number on the stair well. You get $19,000 if it breaks, you get $20,000 if it never breaks. You never need 20 light bulbs in the first place.

The bulb always breaks against the tarmac so you don't even need to go to the top, just know that the bulb breaks at 0

This is a Newtonian math question. Go to the 50th floor. Does the light bulb break? if yes go to the 25th floor. If no go to the 75th floor. If on the 25th floor the bulb breaks go to the 12 floor if not go to the 37 floor. If on the 75th floor and it breaks go to the 62 floor. If it does not break go to the 87 floor. Basically you continuously do an break vs. not break analysis and divide the most recent floor delta by 2. If it breaks subtract the value from your current floor and go to that floor. If it did not break add the value to your current floor and go to that floor. This is the most efficient way (uses the least amount of bulbs) to find the highest floor that the light bulb will not break.

I think Apple took a good approach, but in general, the follow-up question to this one is more interesting, and one I would look for:

What is the desired OUTCOME?

There are a number of ways to determine the correct floor. But in most tasks, there are desired outcomes. Does the questioner wish the most efficient way to determine the floor number (that's not in the question)? Or does the questioner care more about having extra light bulbs at the end? People often jump into the programmatic solution first, without ever thinking to ask "What should my end state be?"

Agree with Andrew and Anthony........start walking down the stairs with one bulb. When it breaks you have your answer. 19 left.

I hold a light bulb with care because I know it will break if I drop it. I would question the competence of marketing for wanting to determine height of destruction of a light bulb. I would ask that they just slap a "fragile: contains glass" label on the package and shift resources to R&D to create a light bulb that burns longer and uses less energy because that is what people really care about in light bulbs.

Read the manual people!!!!or call the company manufactoring those bulbs!!!
20k in the bank.

I believe the answer to the question lies simply in the asking. The point is to get these responses, and more importantly put you into a different frame of mind. You are no longer providing canned responses to generic questions but are now faced with a situation or question that requires novel thought process. Again the answer is not necessarily important, but the result is.

You could put all 20 bulbs in a box and start walking up the stairs. Label each bulb as to what floor you were on when it broke. Is this too simplistic, or am I missing something??

Why are alot of people dropping the bulbs. A bulb will most likely break when dropped from almost any height. Who is the Einstein who said to start at the top floor. I think most of the bulbs would already be broken if you were on the tpo floor to start with. Nutbags!!!!

In response to Jim,

I think you can actually figure it out with only lightbulb lost. Assuming you started from the bottom floor and worked up to the top floor dropping the bulb and then picking it up and dropping it again on the next floor. It would take quite a while though. That is assuming you want to optimize the number of bulbs lost. If you want to optimize based on time, you would want to do a binary search algorithm

All of these answers implies two (2) important facts being overlooked.

Fact one - no one said you couldn't pick up an unbroken bulb and try it again.
Fact two - no one said you had to drop the bulb. It just said "breaks at a certain height."

None of you considered that...maybe by ascending the building carrying one (1) bulb...it might just...break?

Convergent thinkers!!!

I would first correct the grammar in the statement: "how do you determine the height *that* the light bulb breaks..." to "the height *at which* the light bulb breaks..." and proceed to not get the job.

Why would you need to know that?

The BA in me would seek clarification in the requirements. The questions being asked is unclear.

A) Does the question mean the bulb would break if placed on a certain floor of the building or is the asker really meaning the bulb would break if dropped from a certain height?

B) Is the goal to find the most efficient solution to the question (i.e. fewest number of tests)?

C) Assuming we are dropping the bulbs from the building, can we collect unbroken bulbs and reuse them?

Without this information, there is no way to answer the question. The answer depends on this additional information.

Simple: Do a Bruceton staircase analysis. This method is used to determine the mean failure height along with a confidence interval ("95% confident that 50% will fail at floor x") and percentile ("99% will fail by floor y") of packages all the time. It also takes into account variations in bulb fragility and minimizes the chance that you have a "bad" light bulb that was more fragile and thus failed early.

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

Me: Throw a bulb off at 50th floor, if it breaks go to the 25th. If it breaks go to the 12th and test out a bulb. At that point you have 18 bulbs and about 11 or 12 floors to test either above or below the 12th floor. The same applies if the bulb does not break at the 50th floor, try 75 and follow the same procedure.

work from bottom up and throw one at every 10 floors. if the light bulb breaks at this throw, then work downwards and throw at each floor to determine the exact point where the light bulb will break?

is it really that hard??

I will go with Bruce!
Given the condition that Jim Dovey added in above comments, if one is going to get bonus of $1000! algorithm depends on what you want to achieve.

1. Optimize number of trials:
    Solution- use binary search approach. guaranteed bonus=13k

2. optimize profit:
    solutino - start from 1st floor. go up one level. Only 1 bulb needed. guaranteed bonus = 19k

CG
Your logic is interesting.
But when you say (uses the least amount of bulbs) your word usage is incorrect.
Amount is for a measured quantity as in amount of sugar.
You should have said (uses the least number of bulbs) or (uses the least bulbs)
Number is for counted quantities

It's funny, variations of this question are so common in the industry I'm currently in that it's become a parody of itself...the answer I gave for an app engineer job after hearing it from the 11th different firm:

"I'm not answering it for the same reason you Googled the questions to ask: neither of us have time for this."

I kind of just blurted it out. As you might expect, I wasn't offered the engineer position.
I was instead offered the group supervisor position.

I would not try this at home -- but they told me they'd never had anyone answer it that way, and it was the reason they made me that offer. It's an extreme example of how these questions are as much about attitude as aptitude.

$19,000 bonus and one bulb is enough - drop as follws 1,3,6,10,15,21,28,37,47,58,70,83,97 contune untill all 1-100 distances are covered.

We can reduce trials and sacrifices some bonus, if each trial cost something that will impact bonus

DownOn3 has it.

The question didn't say anything about dropping. It said the bulb will break at a certain height, I'll say that means it will break at a certain atmospheric pressure.

Take one bulb, leave the rest at the bottom of the building. Walk up the stairs until the bulb breaks. At most, one will break. $19,000 bonus guaranteed.

Divide the # of floors in half each time and go to the nearest whole #. Drop a bulb from that floor, then go the next 1/2 way point (50, 12 or 25, and so on).

If this is not an atmospheric/pressurization question, all bulbs will break at a height of 0. I'm not even going to waste a bulb on that one.

There would be questions before doing the test.
What is more important to save time or save bulbs?
(Similar question as what is more costly the light bulbs or my time?)
If they are experimental bulbs that cost $1000 each, I'm pretty sure I could walk to eah floor in less than 16 hours (and unless I get payed $1000 an hour) then it is more economical to go up one floor at a time (although I would not quite do that).
If the bulbs are cheap (let say $1 each) then my time is more expensive. So the number of times over 1 that I drop it an it does not break is wasted time (or money). Then I would use a binary search algorithm. Also if there is an elctro magnet attached to a cable it may help in making the test shorter (ideally it needs to be 25 stories in length).
How accurate do the findings need to be? (down to a floor or down to an inch).

BTW, the minimum number of bulbs that would need to be destroyed is 3. Since the experiment (yes, it is a scientific experiment) needs to be verified at least 3 times.

BTW, LED light bulbs are very tough is is essentially a piece a piece of metal inside a piece of plastic. This bulbs are tough. I have drop an entire fixture from 20 feet (bulbs and metal casing) and it survived.

So for those who "ASSUMED" that all bulbs break at distance greater than 0. Thank you for applying, but the management positions are already taken, they were looking for an engineer. As I can tell many people here are not the core group Qualcomm was looking for.

This is similar to a question on the published "Cracking the coding interview" on chapter 6.5 in the "Brain Teaser". It is on P96 in 5th edition.

Given 20 destructable light bulbs and a 100 story building....

You know what? I don't need this job anymore, I have a 100 story building now!!!

I'll stand at the base of the building and smash a lightbulb into the floor. If it breaks, problem solved. If it doesn't break then I'll start taking steps up the stairwell banging on the lightbulb on each step. You only need one light bulb to figure out at what height it breaks, assuming that they're all the same.

I generally agree with all the people that say that the lightbulbs break at a height of zero though, assuming that you're dropping the lightbulbs off the building FROM any height. The question wasn't what height the bulb breaks when dropped FROM. Obviously the height that the bulb breaks is ZERO when it hits the ground. But that's assuming that you drop it on the ground next to the building and not on each of the 100 floors.

Then again, the bulbs might break at EVERY height. If you so much as touch these light bulbs they will break, let alone drop them! Maybe these lightbulbs and the new high-tech ultra-thin glass breaks in anything short of an absolute vaccuum and zero gravity. Maybe this really is an altitude issue. Maybe your 100 story, 350-foot tall building is insufficient and irrellivent because the bulbs break at an altitude of 35,000 feet.

Also, every single one of you assumed that you recieved these light bulbs intact. Maybe to answer the question you simply need to look at the light bulb where it already lies in pieces on the floor.

Alternatively, these could be self-destructable lightbulbs with an altimeter and an explosive charge built in. Walking up or down the stairs holding one of these lightbulbs would be suicide. The question then would be what might motivate you to figure this out if it would cost you your life?

First read the question and figure out what is being asked, then think outside the box. The question states that the bulbs break at a certain height. That is, not when you drop the bulb from that height, simply that they break at that height (presumably due to air pressure?)...

I lose zero bulbs. Simply wait until evening and look up. The number of floors that have lights turned on will tell you which floor they start breaking at.

Well I don't see how the number of floors of the building matter. It doesn't ask what floor you need. It asks at what height will the bulb break. Therefore, you just need to know the height at the time the bulb breaks, not what height it was dropped from. You need final height, not initial height. No matter the initial height, the final height will always be the ground. So the height will be zero when the bulb breaks. And I didn't even need a formula! :-)