J.P. Morgan

www.jpmorganchase.com
Employer Engaged

Interview Question

Applications Developer Interview

a brain teaser question: you have two balls and one

  100-story building. What is minimum tries to figure out which floor will break the ball if a ball is dropped from that floor.
Answer

Interview Answer

2 Answers

0

Basically a restating of binary search, which is find a value between a min and a max value with the minimum number of searches. Basically start at the 50th floor (in the middle), if the ball breaks, go to the 25th floor and try there; else go to 75th floor and try there. Each round would successively split the remainder in half until you get to the floor which is the solution. If you have unlimited balls, then it'll be about 7 or 8 iterations [(2 to the nth power) minus 1].

The problem is more complex because of the limit of the number of balls. This means that some sort of linear search may also be required--if the exact floor must be found. Drop one from the 50th floor, if it breaks, start at the first floor and go up. At that point, on average it'll take to the 25th floor to get an answer, but may take all 49 floors. If the first ball doesn't break on the 50th floor, try it again from the 75th floor. Whether or not it breaks determines whether the binary search continues or the linear search starts. The maximum tries gets smaller depending on when the search transitions from binary to linear, if it ever does. In this case the minimum is the situation where the search never transitions from binary to linear--in other words, a binary search is used the whole time--thus the minimum is the same as for a binary search. Where the ball breaks is somewhere between the 98th and 99th floor.

So the real point to take away from this is that they asked for the MINIMUM, not the maximum or average. Binary search always yields a minimum search for an ordered list (or 100 story building) so you can go straight to that answer.

Jim on May 18, 2014
2

Simple... The minimum would be 1 try duh.

Anonymous on Dec 5, 2014

Add Answers or Comments

To comment on this, Sign In or Sign Up.