Another interview question:
You are in a 100 story building. You have two iPhones. Assume the iPhones are identical and will break when dropped out the window (ie. they fall all the way to the street below) from floor X or higher, but they will not break if dropped from below floor X. If an iPhone doesn't break, it doesn't grow weaker (ie. you can safely drop it from floor X - 1 an infinite number of times, if you have the time).
X can be 1, it can be 100, or any number in between.
What is the fewest number of drops you need to find X?
Answer: “Here, hold this.” [Hand interviewer an iPhone, shove him out the window.]
thirty three
It seems like there’s a problem with the test being over when the two phones are broken… You could start on floor 2 and move up by 2’s until the first phone broke, then move back one floor and see if the second phone breaks there, then you would know X after X/2 + 1 tries. I don’t know if there’s any quicker way to do it.
here’s how to do it in 18 drops:
drop at 10. if it breaks, drop the other from 1, then 2, 3, 4, … 9. but if it doesn’t break at 10, go to 20, 30, 40, etc..
you can also divide it into chunks of 25 (drop @ 25, 50, 75, then start counting up by 1 @ 1, 26, 51 or 75). that’s 27 drops.
or chunks of 20 (drop @ 20,40,60, etc. then back up to 1,21,41, etc. and count up by one). 23 drops.
i think 10 is the best, with same-sized chunks. but the guy hinted that there was a better solution if the chunks were not all the same size.
i couldn’t figure it out.
“What is the fewest number of drops you need to find X? ”
You have to drop it at least once, isn’t one the smallest number? Maybe two just to confirm you guessed right the first time?
You have to drop it at least once, isn’t one the smallest number?
X is the lowest floor from which the iPhone breaks. knowing that it breaks on floor Z only tells you that Z >= X .
isn’t one the smallest number?
No nono, one is the loneliest number. Easy to get confused of course.
I think this was taken from a list of Google interviews that was released recently, except that they used eggs instead of iPhones (way behind the times there, Google)
And, if you need to actually break the phone, then you’d need 19 drops, since with 18 you can only infer that the 9th floor would break it, but you havent *confirmed* that.
i made the iPhone/egg change. the magic bird was something else, too.
And, if you need to actually break the phone, then you’d need 19 drops, since with 18 you can only infer that the 9th floor would break it
if it breaks on 10, then you only need max 10 drops to find X.
10, 1, 2, 3, 4, 5, 6, 7, 8, 9.
worst case is the 99th floor:
10, 20, 30, 40, 50, 60, 70, 80, 90 : 9 drops
91, 92, 93, 94, 95, 96, 97, 98, 99 : 9 drops
but if it wasn’t 99, then 100 must be the one.
i am assuming it breaks on one of the floors, though, since i think that’s the way the question was put to me. not sure if that’s in Google’s version, though. if it might not break, then yeah, worst case min is 19 for the ten-floors method.
but is there a better way than that ?
You say: if it breaks on 10, then you only need max 10 drops to find X.
10, 1, 2, 3, 4, 5, 6, 7, 8, 9.
I say: 9 drops only because when it didn’t break at 8, but broke at 10, then shouldn’t 9th be the ‘safe floor’.
what if 9’s the floor that it breaks on ?
If you don’t drop it from 9, it will be like Schrödinger’s iPhone, simultaneously broken and not broken. (Also sort of like the program I’m currently working on, which resolves to a buggy state when the customer opens the box but to a non-buggy state when I open the box.)
worst case: 14 drops
first phone: 14,27,39,50,60,69,77,84,90,95,99
13,26,etc all take 14 drops. (100 only takes 12 drops and you’ve still got a phone left over, so you could tweak this for a better average case, but I don’t think you can improve the worst case).
No way I could get that in real time, though. No Google job for me!
cool!
now how did you come up with that ? :)
can you generalize it to work for any number of floors ?
I didn’t come up with it efficiently. You want to keep all the worst cases for the second drops about equally bad. So that means each first drop wants to increment one fewer floors than the last one. So give me a worse case and I can show you the set of drops that makes that work, if it does. Give me 18, I give you 18 35 51 66 80 93, which only requires 13 for 100. Give me 13, I give you 13 25 36 46 55 63 70 76 81 85 88 90 91, which can’t make it to 100.
If you were a little smarter than I was, you could use the sum (1 to n) = n(n+1)/2 trick to figure out the worst case right away.