Bowling ball

Question:

Your job is bowling ball tester. You have two identical bowling balls. Given a 100-story building, your challenge is to figure out from which floor a dropped bowling ball will shatter on the ground. You know nothing about the durability of the bowling balls; they may be very fragile and shatter when dropped from the first floor, or they may be so tough that they shatter from a drop from the one-hundredth floor only.

This is a bowling ball stress test. What is the most efficient way to determine the floor from which a dropped bowling ball will shatter? In other words, what is the minimum number of bowling ball drops you need to guarantee you can identify the floor from which they will surely shatter? You are allowed to destroy both bowling balls in the tests, provided that in doing so you uniquely identify the correct floor.

.

.

C

A

P

T

A

I

N

I

N

T

E

R

V

I

E

W

.

.

Solution: Candidates will want to clarify the problem. That’s to be expected. This is a tricky problem, and candidates will want to know they are solving the right problem. The standard query is to make sure that if a bowling ball shatters from a drop from, say, floor 66, it will never shatter from a drop from floor 65. But most people get trapped by working the problem up a floor at a time. The flash of insight required is to realize that one can skip floors and, because there are two balls, work backward.

The solution either requires knowledge of number theory, experience with sampling for quality testing, or a bit of trial and error. Most inter-viewers stop the candidate as soon as they articulate an understanding of how to divide the 100 floors in the most efficient way or otherwise demonstrate the backtracking strategy. Listen to how one candidate re-states the problem and then suggests a solution:

The challenge here is to find the highest floor of a 100-story building from which the balls can be dropped without breaking, right? So the goal is to devise an optimal procedure that can always locate that floor using not more than n drop tests. What is the smallest n can be? We need a system. We can’t use the obvious divide-by-2 search here because once the first ball breaks we’ll need to search all the untested floors below from bottom to top. To find the best strategy, I think we need to work backward from fewer floors using the following rule:

One drop allows us to test 1 floor.

Two drops can test 3 floors: Test the second floor first. If it breaks, test the first floor with the other ball. If not, test the top floor with either ball.

Three drops can test 6 floors: Test the third floor first. If it breaks, test the bottom 2 floors in order with the other ball. If not, test the top 3 floors as described above.

Four drops can test 10 floors: Test the fourth floor first. If it breaks, test the bottom 3 floors in order with the other ball. If not, test the top 6 floors as described above.

N drops allows you to test the number of floors equal to the sum of 1 to n. Fourteen drops can test 105 floors: Test the fourteenth floor first. If it breaks, test the bottom 13 floors in order with the other ball. If not, test the twenty-seventh floor next (14 13), and so on.

For any given drop, the number of drops you’ll need after that should be the same if that ball breaks or not (or sometimes they are off by 1 if your total is not an even sum-of-1-to-n).

The optimum test protocol for 100 floors, then, requires a maximum of 14 drops. The next step is to derive a testing strategy that divides the 100 floors using the series 14 +13 12 +11 +10 +9 +8 +7 +6 +5 +4 +3 +2 +1. The best testing strategy starts with a drop from floor 14; then a drop from floor 27 (14 13); then 39 (14 13 12); etc. The full pattern is 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100.

In practice, this series sacrifices the first ball to point to an ever-decreasing series of possible target floors. A small number of drops using the second ball then identifies the target floor. Simply go back to the previously tested floor and start working up a floor at a time. Eventually, you will determine the floor at which the bowling ball shatters. This is the most efficient testing algorithm.

The absolute worst case is that the ball shatters on floor 13. Here’s why. The first ball is shattered at floor 14. Then 13 more drops are required. Any other case requires fewer drops.

Let’s assume the bowling balls shatter on, say, floor 73. You will drop the first ball six times (from floors 14, 27, 39, 50, 69, 77) and it shatters on the sixth test (floor 77). At this point, you have narrowed the target floor between floor 70 (you know the ball survived a drop from floor 69), and floor 77 (at which point it shattered). To test the specific floor from which a bowling ball shatters, simply increment from the last floor the ball sur-vived and start testing according to the following protocol: 70, 71, 72, 73, at which point the second bowling ball will shatter and you will have your answer. For example, this test required 10 drops to identify the target floor.

If you get to floor 100 and the first ball hasn’t shattered, you know you have a darn strong bowling ball. And it required only 12 drops to prove it.

Answer: Anywhere from 1 to 14 bowling bowl drops.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s