Brainteasers draw from a much broader and more diverse body of knowledge than programming and technical problems, so a comprehensive review isn’t possible here. The following
Suppose you are in a hallway lined with 100 closed lockers. You begin by opening all 100 lockers.
In a hall with
lockers, how many lockers
This problem is designed to seem overwhelming. You don’t have time to draw a diagram of 100 lockers and count 100
Start by choosing an arbitrary locker, 12, and determining whether it will end open or closed. On which passes will you toggle locker 12? Obviously on the first pass, when you toggle every locker, and on the twelfth pass when you start with 12. You don’t need to consider any pass after 12 because those will all start farther down the hall. This
The factors of 12 are 1, 2, 3, 4, 6, and 12. Correspondingly, the operations on the locker door are open, close, open, close, open, close. So locker 12 will end closed. The solution seems to have something to do with factors. Primes are
The task has now been reduced to finding how many numbers between 1 and 100 have an odd number of factors. The two you’ve examined (and most others, if you try a few more examples) have even numbers of factors. Why is that? If a number
is a factor of
, what does that mean? It means that
times some other number
is equal to
. Of course, because multiplication is commutative (
), that means that
is a factor of
, too, so the number of factors is usually even because factors tend to come in pairs. If you can find the numbers that have unpaired factors, you will know which lockers will be open. Multiplication is a binary operation, so two numbers will always be involved, but what if they are both the same number (that is,
)? In that case, a single number would effectively form both
Based on this reasoning, you can conclude that only lockers with numbers that are perfect squares end open. The perfect squares between 1 and 100 (inclusive) are 1, 4, 9, 16, 25, 36, 49, 64, 81, and 100. So 10 lockers would remain open.
Similarly, for the general case of
lockers, the number of open lockers is the number of perfect squares between 1 and
, inclusive. How can you best count these? The perfect squares
This task is trivial when
is a perfect square, but most of the time it won’t be. In these cases, the square root of
will be a noninteger. If you round this square root down to the
The key to solving this problem is trying strategies to solve parts of the problem even when it isn’t clear how these
You are standing in a hallway next to three light switches, all of which are off. Each switch operates a different incandescent light bulb in the room at the end of the hall. You cannot see the lights from where the switches are. Determine which light corresponds to each switch. You may go into the room with the lights only once.
The crux of this problem comes quickly to the fore: There are only two possible
When confronted with a seemingly
How can these properties help you solve the problem? Which of them can you detect or measure? The properties of a switch don’t seem too useful. It’s much easier to look at the switch to see whether it’s off or on than to measure current. The light bulbs sound a little more
You can determine which switch goes with each bulb by turning the first switch on and the second and third off. After ten minutes, turn the first switch off, leave the second off, and
Although there’s nothing truly outlandish about this question - it’s not just a stupid play on words, for instance - it is arguably a trick question. The solution involves coming up with something somewhat outside the definition of the problem. Some interviewers believe that questions like this will help them identify people who can “think outside the box” and develop nontraditional, innovative solutions to difficult problems. In the authors’ opinion, these problems are cheap shots that don’t
A party of four travelers comes to a
What is the least amount of time in which all the travelers can cross from one side of the bridge to the other?
Because there is only one flashlight, each trip to the far side of the bridge (except the last trip) must be followed by a trip coming back. Each of these trips consists of either one or two travelers crossing the bridge. To get a net movement of travelers to the far side of the bridge, you probably want to have two travelers on each outbound trip and one on each inbound trip. This strategy gives you a total of five trips, three outbound and two inbound. Your task is to assign travelers to the trips so that you minimize the total time for the five trips. For clarity, you can refer to each traveler by the number of minutes it takes him to cross the bridge.
Number 1 can cross the bridge at least twice as fast as any of the other travelers, so you can minimize the time of the return trips by always having 1 bring the flashlight back. This suggests a strategy whereby 1 escorts each of the other travelers across the bridge one by one.
One possible arrangement of trips using this strategy is
This solution is logical, obvious, and doesn’t take long to discover. In short, it can’t possibly be the best solution to an interview problem. Your interviewer would tell you that you can do better than 19 minutes, but even without that hint you should guess you arrived at the
This puts you in an uncomfortable, but
Consider your assumptions, checking each one to see if it might be false. First among your assumptions was that outbound and inbound trips must alternate. This seems correct - there’s no way to have an outbound trip followed by another outbound trip because the flashlight would be on the wrong side of the bridge.
Next, you assumed that there would be two travelers on each outbound trip and one on each return trip. This seems logical, but it’s harder to prove.
You also assumed that 1 should always bring the flashlight back. What basis do you have for this assumption? It minimizes the time for the return trips, but the goal is to minimize total time, not return trip time. Perhaps the best overall solution does not involve minimized return trip times. The assumption that 1 should always return the flashlight seems hard to support, so it probably merits further examination.
If you’re not going to have 1 make all the return trips, then how will you arrange the trips? You might try a process of
You might also try analyzing some of the individual trips from your previous solution. Because 1 escorted everyone else, there was a trip with 1 and 10. In a sense, when you send 1 with 10, 1’s speed is
Using this strategy, you might begin by sending 10 and 5 across. However, one of them has to bring the flashlight back, which you already know isn’t the right solution. You’ll want to already have someone faster than 5 waiting on the far side. Try starting by sending 1 and 2 across. Then have 1 bring the flash-light back. Now that there’s someone reasonably fast (2) on the far side, you can send 5 and 10 across together. Then 2 returns the flashlight. Finally, 1 and 2 cross the bridge again. This scheme is illustrated in Figure 12-2.
The times for the respective trips under this strategy are 2, 1, 10, 2, and 2, for a total of 17 minutes. Identifying the false assumption improved your solution by 2 minutes.
This problem is a slightly unusual example of a class of problems involving optimizing the process of moving a
You have eight marbles and a two-pan balance. All the marbles weigh the same, except for one, which is heavier than all the others. The
The first step in solving this problem is to realize that you can put more than one marble in each pan of the balance. If you have equal numbers of marbles in each pan, then the heavy marble must be in the group on the heavy side of the balance. This saves you from having to weigh each marble individually, and it enables you to eliminate many marbles in a single weighing.
Once you realize this, you are likely to
This may seem to be the correct answer. The solution wasn’t completely obvious, and it’s an improvement over weighing the marbles one by one. If you’re telling yourself that this seemed too easy, you’re right. The method described so far is a good start, but it’s not the best you can do.
How can you find the heavy marble in fewer than three weighings? Obviously, you’ll have to eliminate more than half the marbles at each weighing, but how can you do that?
Try looking at this problem from an information flow perspective. Information about the marbles comes from the balance, and you use this information to identify the heavy marble. The more information you derive from each weighing, the more efficient your search for the marble will be. Think about how you get information from the balance: You place marbles on it and then look at the result. What are all the possible results? The left pan side could be heavier, the right side could be heavier, or both sides could weigh exactly the same. So there are three possible results, but so far you’ve been using only two of them. In effect, you’re only using 2/3 of the information that each weighing provides. Perhaps if you alter your method so that you use all of the information from each weighing you will be able to find the heavy marble in fewer weighings.
Using the binary search strategy, the heavy marble is always in one of the two pans, so there will always be a heavy side of the balance. In other words, you can’t take advantage of all the information the balance can provide if the heavy marble is always on the balance. What if you divided the marbles into three equal-
There’s still a minor wrinkle to work out before you can apply this process to the problem at hand. Eight isn’t evenly divisible by three, so you can’t divide the eight marbles into three equal groups. Why do you need the same number of marbles in each group? You need the same number of marbles so that when you put the groups on the balance the result doesn’t have anything to do with differing numbers of marbles on each side. Really, you need only two of the groups to be the same size. You’ll still want all three groups to be approximately the same
Now you can apply the three-group technique to the problem you were given. Begin by dividing the marbles into two groups of three, which you put on the balance, and one group of two, which you leave off. If the two sides weigh the same, the heavy marble is in the group of two, and you can find it with one more weighing, for a total of two weighings. On the other hand, if either side of the balance is heavier, the heavy marble must be in that group of three. You can eliminate all the other marbles, and place one marble from this group on either side of the balance, leaving the third marble aside. If one side is heavier, it contains the heavy marble; if
Generalize your solution. What is the minimum number of weighings to find a heavy marble among n marbles?
This is the part where the interviewer determines whether you hit on the preceding solution by luck or because you really understand it. Think about what happens after each weighing. You eliminate 2/3 of the marbles and keep 1/3. After each weighing you have 1/3 as many marbles as you did before. When you get down to one marble, you’ve found the heavy marble.
Based on this reasoning, you can reformulate the question as, “How many times do you have to divide the number of marbles by 3 before you end up with 1?” If you start with 3 marbles, you divide by 3 once to get 1, so it takes one weighing. If you start with 9 marbles you divide by 3 twice, so it takes two weighings. Similarly, 27 marbles require three weighings. What mathematical operation can you use to represent this “How many times do you divide by 3 to get to 1” process?
Because multiplication and division are inverse operations, the number of times you have to divide the number of marbles by 3 before you end up with 1 is the same as the number of times you have to multiply by 3 (starting at 1) before you get to the number of marbles. Repeated multiplication is
This works fine as long as
is a power of 3. However, if
isn’t a power of 3, then this equation calculates a noninteger value for
, which doesn’t make much sense, given that it’s extremely difficult to perform a
Does this make sense? Try applying it to n = 10 and see whether you can justify always rounding up. log 3 9 is 2, so log 3 10 will be a little more than two, or three if you round up to the nearest integer. Is that the correct number of weighings for 10 marbles? For 10 marbles, you would start out with two groups of 3 and one group of 4. If the heavy marble were in either of the groups of 3, you could find it with just one more weighing, but if it turned out to be in the group of 4 you might need as many as two more weighings for a total of 3, just as you calculated. In this case the fractional weighing seems to represent a weighing that you might need to make under some circumstances (if the heavy marble happens to be in the larger group) but not others. Because you’re trying to calculate the number of weighings needed to guarantee you’ll find the heavy marble, you have to count that fractional weighing as a full weighing even though you won’t always perform it, so it makes sense to always round up to the nearest integer. In programming, the function that rounds up to the nearest integer is often called ceiling, so you might express the minimum number of weighings needed to guarantee you’ll find the heavy marble among n marbles as ceiling(log 3 ( n )).
For the group of 4 (out of the total of 10 marbles), you would divide the 4 marbles into two groups of 1 and one group of 2. If the heavy marble
This is another example of a problem designed such that the wrong solution occurs first to most
This problem is a relatively easy example of a whole class of tricky problems involving weighing items with a two-pan balance. For more practice with these, you might want to try working out the solution to the preceding problem for a group of marbles in which one marble has a different weight, but you don’t know whether it’s heavier or lighter.