Qualcomm Interview Question: given 20 "destructable" light... | Glassdoor

## Interview Question

Engineering Interview San Diego, CA

# given 20 "destructable" light bulbs(which breaks at certain

height), and a building with 100 floors, how do you determine the height that the light bulb breaks.

27

binary search

Anonymous on Jun 10, 2011
2

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

elsie on Dec 29, 2011
22

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.

John on Dec 29, 2011
10

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 =&gt; No Good.
• 11 + 10 + 9 + … = 66 =&gt; 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)

Jim Dovey on Dec 29, 2011
56

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.

Jose Sousa Martins on Dec 31, 2011
7

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.

vinc17 on Dec 31, 2011
0

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.

vinc17 on Dec 31, 2011
7

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 &gt; 100), so the guaranteed bonus is \$13,000. I believe it can be proven that you can't guarantee better than this.

Bruce on Jan 4, 2012

This post has been removed.

5

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

Clive on Jan 10, 2012
1

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.

rayz. on Jan 10, 2012
6

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.

Andrew on Jan 10, 2012
1

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

Joe Clarke on Jan 10, 2012
2

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.

CG on Jan 10, 2012
2

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?"

Christian on Jan 10, 2012
0

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

Sean on Jan 10, 2012
4

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&amp;D to create a light bulb that burns longer and uses less energy because that is what people really care about in light bulbs.

Chris on Jan 10, 2012
4

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

Bishope on Jan 10, 2012
1

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.

Jason on Jan 10, 2012
1

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??

Dr. Common Sense on Jan 10, 2012
3

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!!!!

Stooge on Jan 10, 2012
2

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

Alex on Jan 10, 2012
3

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!!!

Mike on Jan 10, 2012
5

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.

Grammar Nazi on Jan 10, 2012
2

Why would you need to know that?

Anonymous on Jan 10, 2012
2

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.

Business Analyst on Jan 10, 2012
0

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.

Packaging Engineer on Jan 10, 2012

This post has been removed.

0

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.

Paul on Jan 10, 2012
0

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??

haylie on Jan 10, 2012
1

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

Tu on Jan 10, 2012
0

CG
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

claudem on Jan 10, 2012
3

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.

DownOn3 on Jan 10, 2012
1

\$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

Lightbay on Jan 10, 2012
0

DownOn3 has it.

Manduke on Jan 12, 2012
2

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.

Doug on Jan 13, 2012
0

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).

vcollogan on Jan 14, 2012
0

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.

Silly People... on Jan 17, 2012
1

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.

The Guy Who would get hired on Jan 19, 2012
0

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.

pulseball on Jan 22, 2012
1

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!!!

Pat on Jan 24, 2012
0

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?

Smartr than the averag moron on Jan 24, 2012
0

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.

Anonymous on May 4, 2012
0

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! :-)

Stephanie on May 8, 2012
0

The question does not mention why the bulbs would break. The only reason a bulb would just break at a certain height without impact is because of air pressure. Bulbs are in a vacuum and because of the shape of a typical bulb, positive external pressure will not be a factor. However, a negative external pressure may have an effect depending on the pressure inside the bulb. Also varying barometric pressure will also have an effect. On a bright sunny summer day, the bulb would burst at a greater height. On a cloudy day the barometric pressure is lower so the bulb would burst at a lower height. And the question does not ask for height above sea level or above ground level. This is an open-ended question that leaves for more questions than answers.

But if I really want to come up with an definite answer, I would say the "certain" height is the height at which I smash the bulb. So if I am in a building that has a foundation 535 feet above sea level and I smash the bulb on the 100th floor and each floor is 12 feet above the one below: (12 X 99) + 535 = 1723 feet. You do not add 12 feet for the 100th floor because the 1st floor is 0 feet above 535.

Ricochet on May 28, 2012
0

actually its very hard to understand the question only ..
and d ans given here all crap //
guys atleast if u dnt knw d ans plzzz dnt give your opnions..
ty

dipesh on Jun 27, 2012
0

It needs just 2 bulbs to efficiently know the floor from where it will break.

Assume you have just 1 bulb, then there is no other way to test except trying it one by one from each floor. i.e. start with 1st, if it breaks, well, we know the answer, otherwise go to the next...

Now take 2 bulbs...go to the 1st floor, throw one bulb at ground and the other at the height of 2nd floor at the same time. If 1st bulb doesn't break and second one breaks, then 2nd floor is the answer, and we knew it in just one attempt.

If neither of the bulbs breaks, we need go to 3rd floor, as we tested already for the 2nd floor. And from 3rd floor, throw one bulb at he ground and the other at the height of 4th floor...we just need to repeat it until one of the two bulbs breaks or we reach at the 99th floor and test the same...

But in case you want to use all the 20 bulbs...you need more resources to test...

DKumar on Jun 28, 2012
0

&gt;given 20 "destructable" light bulbs(which breaks at certain
&gt;height), and a building with 100 floors, how do you determine
&gt;the height that the light bulb breaks.

Ha! You ALL failed. This wasn't an interview question to think outside the box. It wasn't a complicated math question, it was a SPELLING test. You failed.

"destructable" is spelled destructible.

And those of you that used "destructable" in your posts? You're fired....

PACSMan on Sep 5, 2012
0

I agree with Jose, the same answer is mine

Mr. Connor on Nov 2, 2012
0

The question doesn't say you have to drop them. I would place them inside a pressurized container and take them all the way up to the 100th floor and get the full \$20k :)

Xocoatzin on Nov 8, 2012
0

I used to work in a 110 story building. If you handed me a box of lightbulbs and told me to toss them off the roof, I'd call Security on you and keep the lightbulbs. End of story.

Herself on Apr 27, 2013
1

The true maximum bonus acquirable is \$19,000, for you would understand that the bulb will break at some floor above floor one, otherwise the question itself would be insensible to ask. with this being said, starting at floor one (for assurance), drop a bulb. if the bulb breaks, you have your answer, and a nice \$19,000 bonus. if the bulb survives, you simply drop the bulb from a higher point, i.e. the next floor up. you repeat this process until you find which floor the bulb breaks, since it will break at some height above the ground. all that mumbo jumbo about an algorithm from a person with a masters in mathematics is complete garbage. very simple question with a very simple answer, -Andrew Romero, ChE Major, Junior, University of South Florida. Go Bulls!

Andrew Romero on Sep 15, 2013
1

This question catches people who are not wired to pick up on details and who also make assumptions or jump to conclusions quickly. I was a licensed EMT-SS in college and similar questions were notorious for being on patient assessment exams. If is fundamental to a full assessment to observer everything and assume nothing.

Read the problem carefully and don't make any assumptions, ""given 20 'destructable' light bulbs(which breaks at certain height), and a building with 100 floors, how do you determine the height that the light bulb breaks."

Premise:
Light bulbs are air tight and are filled with an inert gas or evacuated to prevent oxidation of the filament.

Inferences:
1. The problem to solve is "HOW DO YOU DETERMINE the height that the light bulb breaks."
2. The solution to the problem is a "method" (eg. How?) and not "a quantity of units."
3. The light bulbs break "at certain height" which is a single height and not at any or many heights.
4. The problem to solve has nothing to do with the 100 foot building. It could be a resource that could be used to help solve the answer but it is not a variable of the problem.

Solutions
1. Light bulbs will break when the difference between their internal and external air pressures exceeds the tolerance of the glass globe of the light bulb. Higher or lower elevations have lower and higher air/barometric pressures, respectively. Therefore, raising or lowering an object changes it ambient air pressure. Hence, the solution is to raise or lower a light bulb until the differences in the internal and external air pressures exceed the tolerance of the light bulb and it breaks.

1. The problem to solve is NOT "determine the height that the bulb breaks when dropped." If it was the answer would be "the ground" because the bulb would break when it hits the ground, not where it is let go to drop.
2. The problem to solve is NOT "determine the height that dropping a light bulb from will cause it to break."

NOTE:

Mark Metcalf on May 23, 2014
0

the statements says the bulbs break at a certain HEIGHT - then why not just take a bulb and start walking up and see at what floor/height the bulb breaks .....

Dhali on Nov 26, 2014
0

Go up in 1/5th intervals to the the top

Anonymous on May 3, 2015
0

Wouldn’t you just contact the lightbulb manufacturer if this was important information to consider? The bigger issue is not breaking the lightbulbs because that’s not what they’re designed to do. The goal is to receive 100% of the bonus without damaging any of the lightbulbs.

Linda on Sep 14, 2018