May 16, 2008
-
My Demoralizing Interview Question
I’ve been doing interviews all week, and this last Thursday, I was interviewing with Hi5.com. The interview had being going surprisingly well. The interviewer was really impressed with the work I’d done in grad school and at Xanga, and I’d just answered a pretty interesting question about optimizing data stacks for performance. Then I got this question:
You have two identical spheres that break when dropped from a height greater than X floors. You have a 100 Floor building and you’re guaranteed that X is less than 100. Give a strategy to determine the greatest height that the spheres can be dropped from without breaking. [edit: Assume that until a sphere breaks, it is just as strong as it was before you dropped it. ] Once a sphere breaks, you can no longer drop it (cause its broken duh!). Now give a strategy that minimizes the worst case number of times you drop a sphere.
I know the answer now, but only after being coached through the mud by the interviewer. >_< Feel free to give it a shot, and prove that you’re smarter than I am. I’ll post the solution later if nobody figures it out.
Over and out,
-Joe
[Edit: The solution can be found here. ]
Comments (20)
I’d create a ramp for the sphere’s to roll down, so as to minimize any damage. The ramp could also be used as a water slide for kids….and it would be wicked awesome!!!!
(I have no clue otherwise)
Intelligence c covers a vast spectrum. We just tend to claim some spectras are nobler than others.
or, in plain Enlish
I’m a lot stupider than you.
Good luck with the interviews Joseph.
Dang…no specifics on the nature of the spheres? What they are made of or how tough? Think I would drop one from level one and another from midway. Then if mid way survives, one up from there and midway from there. Like that. If one breaks it would have to be step by step from there.
But even that solution is bogus because every drop will effect the following integrity of the spheres. They are not the same spheres after even a few test drops. What is it…a fricken trick question?
I hate physics!
@BADBOYDOOMDADDY - @Divine_Diva_in_NC - It isn’t a physics question. ^_^
@joseph - Physics or not, I must…know…answer. I will try and be patient but I better get an answer or I’m going to give them floppy ears a yank. Oh, don’t give up hope…I have had interviews like that and still got hired for at least trying…ya did try…right?
This sounds like one of those you have x weights and a scale, figure out which one is the heaviest with using the scale the least amount of times.
So for this question you would drop one at 50 floors. If it breaks you know the number is less than 50, if it doesn’t you know it’s more than 50 floors, so you have eliminated half the choices. If it breaks I would use the second sphere to go downward one floor at time.
If it doesn’t break I would go to 75 and see if it breaks and if it doesn’t break I would go to 88 and so on. When it breaks I would us the second one to go downwards one floor at a time to see where the next one breaks.
This should greatly decrease the number of times you have to drop the spheres if you were going from floor 1 till it broke.
*shrugs*
@raindrops23 - that was my first answer! ^_^ However the worst case for that strategy is 50 drops. :p
Way out of my league.
Hope you find the best job for you soon!
Good luck!
@joseph - you’re right, so if it was your first answer, there must be a better answer… interesting. ^_^ this is like playing profession layton and the curious village again.
Well you could start at the 33rd floor
Which would mean the worst case is 33. It breaking at 33 or it breaking at 66 (you will have test between 33-66)
like a chicken in the coop?
Bawk bawk bawk.
It reminds me of the old science projects in school when you had to try to drop the eggs off the roof.. safely.
I dunno.. sounds like staircases or escalators or elevators, each at a level of 25 feet?
/
-
-
/
-
-
questions like these are hard to do over the phone
you could try every 10 floors until it breaks, then go up one by one from the last one that didn’t break. maximum drops: 18
i would drop from the 1st floor, and go in increments of 5? and then if the first one breaks, i’d take the second one and drop from the floor above the last floor that the first didn’t break? i’m just talking coocoo…TELL US THE ANSWER! or i’ll just message you later for the answer – this is like professor layton game…and that light bulb interview question that supposedly microsoft used to use in their interviews…
Start at floor 50. If it stays whole, drop from floors upwards…IE 52, 54, 56.
Skipping one floor in between means if it breaks, you know it was the one floor before that is left to test.
That method divides the amount of drops needed by half, and then half again for whatever it takes to reach breaking point, if it does not break at the first drop from 50 floors.
If it does break at 50, you still can start at the other end with floor two and go upwards two floors at a time till it breaks.
That’s probably wrong, but it’s how I’d do it.
@patrick - jerk. i was gonna post that and you had to go and post it first. you will pay for that.
i think its right though. i think the formula would be:
Worst Case # drops = ceiling( (x-2) + (100/x) ) where you drop the first sphere every x floors starting at the 1st. That value is lowest when x=10.
dang, i hope thats right because i feel pretty lame right now =P
@Justin - That formula looks right to me, but you’d want to start at the xth floor instead of the first.
If it doesn’t break I would go to 75 and see if it breaks and if it doesn’t break I would go to 88 and so on. When it breaks I would us the second one to go downwards one floor at a time to see where the next one breaks.