Qualcomm

# `Qualcomm` `Engineering` Interview Question

`"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."`

Part of a `Engineering` Interview Review - one of `982` `Qualcomm` Interview Reviews

`Qualcomm`

Answers & Comments

votes

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

votes

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.

votes

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)

votes

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.

votes

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.

vote

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.

votes

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.

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

votes

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

votes

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.

votes

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.

votes

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

votes

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.

votes

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

vote

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

votes

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.

votes

Read the manual people!!!!or call the company manufactoring those bulbs!!!

20k in the bank.

vote

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.

vote

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

votes

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

votes

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

votes

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

votes

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.

votes

Why would you need to know that?

votes

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.

votes

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.

votes

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.

vote

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

votes

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

votes

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

votes

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.

vote

$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

votes

DownOn3 has it.

votes

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.

votes

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

vote

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.

vote

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.

votes

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.

vote

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

votes

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?

votes

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.

votes

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

votes

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.

votes

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

votes

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

votes

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

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

votes

I agree with Jose, the same answer is mine

votes

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

votes

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.

votes

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!

votes

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.

Comments

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:

There are now several versions of this question being asked. It only takes one or two words to completely change the problem and answer. The very point of many questions is not test for higher reasoning and problem solving skills but rather to see how carefully you read the question and how easily you make assumptions or jump to unfounded conclusions. It is the profession of testing groups and HR professionals to keep these test effective. Be aware that the easiest questions to cause someone to slip up on are the most common questions that have been slightly changed. A few years ago I had to hire twelve document reviewers in a week and used a group format in our conference room for the first interview and to test a theory I had. I gave each group a short multiple choice assessment test and instructed them to read the instructions and questions very carefully. The instructions at the very top of the first page were, "Read each question carefully and select the correct choice to not pass this test. Do answer the odd questions all option 'a' and leave the even questions unanswered." It took three groups before anyone followed the instructions. We didn't eliminate anyone over this, but we now use it regularly as a training tool to drive home the importance the details and not making assumptions when reviewing legal documents.

** To comment on this question, Sign In with Facebook or Sign Up **

votes

binary search

Jun 10, 2011