Interview Question

Engineering Interview Boston, MA

Given a building with 100 floors and 2 glass balls, how can

  you most efficiently find the maximum floor from which when dropped, the glass balls will not break.
Answer

Interview Answer

2 Answers

1

This is the official question from our super official and super awesome internal wiki:
"You have two glass balls and a 100-story building. You need to find out the maximum height from which a ball can be dropped without breaking. Describe the algorithm to find this out that provides the best worst case performance, i.e. the least number of ball drops for the worst case."

The chances that we asked this question as it's phrased are very small and we generally follow up with a bunch of other cases.

We're looking for a divide and conquer approach, by halving the remaining floors before each drop your worst case is 7 drops if the ball breaks on the 100th floor.

Tim @ HubSpot on May 11, 2011
3

To add to what Tim said, divide an conquer is one approach, but there are others as well.

In fact, divide and conquer doesn't work so well with a building, because your binary search can only work going up the building, but not down.

There are a couple of chunks that I typically looked for when asking a candidate this question: The optimal fixed-interval solution, and the optimal variable-interval solution.

For the fixed-interval, people typically start with the idea of dropping the ball every floor. The worst case in that scenario is that you need to drop the ball at every floor to determine where it breaks. To improve, you might try dropping at the 50th floor and then do either work your way up from 50, or up from 1 depending on if the ball breaks. You've just reduced your worst case scenario by half. But if you keep going, you'll find that steps of 10 allow you to cover the whole 100 story building, and the worst case would be a break at floor 99 which requires 19 drops to determine.

After someone figures out the fixed-interval solution of 19, I ask if we can improve it. Working in bigger steps than 10 does not work, because your worst case becomes larger if the intervals increase steadily. But if you reduce the interval as you move up the building, you can reduce the worst case scenario. So for the 100 story building, the variable-interval is 14, 13, 12...1 The worst case scenario is that the ball breaks at the 14th floor and then you have to work your way from floor 1 up to floor 13.

Either of these solutions can be expressed mathematically but we didn't require that. In fact, this problem was asked to non-Engineering candidates as a way to test problem solving ability. It's more important to be able to reason through the problem than it is to come up with the right answer. As they said in school: "Show your work."

Dan @ HubSpot on May 13, 2011

Add Answers or Comments

To comment on this, Sign In or Sign Up.