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

4 Answers

▲

3

▼

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

▲

0

▼

Actually the minimum would never be 1 (well not never, it would be 1 if the ball breaks at lvl1) if you want to prove the lowest exact level that will break the ball you need to use at least one other try to prove that the immediately lower level won't break the ball. o even if you use physics to calculate the floor you still need another try to prove your theory.

But this is a programming interview so you have to use a mix of binary and linear search, you have to use the mix because of the 2 balls limit as specified above :).

▲

1

▼

The answer is 1. go to the 100th floor. drop the ball, if it breaks, the answer is 100. if not, the ball will not break in the building.

note the question does not say to figure the lowest floor that would break the ball. it just says "which floor will break the ball ". obviously, the question can have multiple answer, and 100 is definitely one answer...if indeed the building can break the ball.

To comment on this, Sign In or Sign Up.

Would you like us to review something? Please describe the problem with this {0} and we will look into it.

Your feedback has been sent to the team and we'll look into it.

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.