Chapter 12: Counting, Measuring, and Ordering Puzzles

In addition to technical and programming problems, you will often encounter brainteasers in your interviews. Brainteasers are mathematics and logic puzzles that have no direct relation to computer programming. Some interviewers feel these problems are silly because they have no direct bearing on the job at hand and won’t ask any of them. Many interviewers, though, think brain-teasers are useful in assessing problem-solving ability - perhaps the most important job skill for a programmer. Interviewers may also be influenced by the knowledge that industry leaders such as Google use brainteasers in their interviews. Whatever the motivation, in some interviews as many as a third of the problems you are presented may be brainteasers.

In the authors’ opinion, performance on brainteasers says a lot about your experience with working mathematical puzzles and very little about whether you will be a valuable employee. The discussion and examples in this and the next chapter aim to give you this experience so you can be successful with brainteasers. Brainteasers share many common themes, so gaining both familiarity with these commonalities and some experience with brainteasers in general can be a great help in solving these puzzles when they are presented during an interview.

Tackling Brainteasers

One of the most important themes to keep in mind is that the solutions to brainteasers are almost never straightforward or obvious. Unlike the programming or technical parts of the interview, where you will sometimes be given simple problems just to see whether you know something, brainteasers always require thought and effort. This means that any solution that seems immediately obvious is probably incorrect or not the best solution. For example, suppose you’re asked, “From the time you get on a ski lift to the time you get off, what proportion of the chairs do you pass?” Most people’s immediate gut-level response is that you pass half of the chairs. This response is obvious and makes some sense. At any given time, half of the chairs are on each side of the lift, and you pass chairs only on the other side. It’s also wrong - because both sides of the lift are moving, you pass all the other chairs.

Tip 

This answer assumes you get on and off at the extreme ends of the lift. On most real ski lifts, you pass almost all the other chairs.

This property of brainteasers works most strongly to your advantage when you are faced with a problem that has only two possible answers (for example, any yes or no question). Whichever answer seems at first to be correct is probably wrong. Of course, it’s probably not a good idea to say, “The answer must be yes because if it were no this would be a very simple problem and you wouldn’t have bothered to ask it.” You can, however, use this knowledge to guide your thinking.

Tip 

Remember that the obvious answer is almost never the right answer.

Although the correct solutions to brainteasers are usually complex, they rarely require time-consuming computations or mathematics beyond trigonometry. Just as writing pages of code is a warning sign that you’re headed in the wrong direction, using calculus or spending a long time number-crunching is a strong indicator that you’re not headed toward the best solution to one of these puzzles.

Solve the Right Problem

Many of these problems are difficult because they suggest an incorrect assumption that leads you to the wrong answer. Based on this knowledge, you might conclude that the best approach is to avoid making any assumptions. Unfortunately, that’s not really practical - even understanding a problem is very difficult without making a whole series of assumptions. For example, suppose you are given the problem of finding an arrangement that maximizes the number of oranges you can fit in the bottom of a square box. You would probably automatically assume that the oranges are small spherical fruit, that they are all about the same size, that “in the bottom” means in contact with the bottom surface of the box, and that the oranges must remain intact (you can’t puree them and pour them in). These assumptions may seem ridiculous - they are all rather obvious and they are all correct. The point is that assumptions are inherent in all communication or thought; you can’t begin to work on a problem without assumptions.

Carrying this example further, you might assume you could model this problem in 2D using circles in a square, and that the solution would involve some sort of orderly, repeating pattern. Based on these assumptions and the knowledge that a honeycomb-like hexagonal array provides the tightest pack of circles covering a plane, you might conclude that the best solution is to place the oranges in a regular hexagonal array. Depending on the relative sizes of the oranges and the box, this conclusion would be incorrect.

Although you can’t eliminate assumptions, it can be useful to try to identify and analyze them. As you identify your assumptions, categorize them as almost certainly correct, probably correct, or possibly incorrect. Starting with the assumption you feel is least likely to be correct, try reworking the problem without each assumption. Keep in mind that these puzzles are rarely trick questions, so your definitional assumptions are usually correct.

For instance, in the preceding example, it would be reasonable to classify the assumptions that oranges are spherical fruit and that they must remain intact and in contact with the bottom of the box as almost certainly correct. How would you categorize the assumption that you can reduce this puzzle to a 2D problem of circles in a square? If you think about it, you can see that the oranges make contact with each other in a single plane, and that in this plane you’re essentially dealing with circles inside a square. This isn’t exactly a proof, but it’s solid enough to decide that this assumption is probably correct. On the other hand, you’ll find you have more trouble supporting the assumption that the oranges should be in an orderly repeating pattern. It seems reasonable, and it is true for an infinite plane, but it’s not clear that the similarities between a plane and the box bottom are sufficient for this assumption to be true. In general, beware of any assumption that you “feel” is true but can’t quite explain - this is often the incorrect assumption. You would therefore conclude that the assumption that the oranges must form an ordered array is possibly incorrect. In fact, this assumption is incorrect. In many cases the best packing involves putting most of the oranges in an ordered array and the remaining few in unordered positions. Analyzing your assumptions is a particularly good strategy when you think you’ve found the only logically possible solution but you’re told it’s incorrect. It’s often the case that your logic was good but based on a flawed assumption.

Tip 

If the solution that seems logical is wrong, you made a false assumption. Categorize your assumptions, and try to identify those that are false.

Don’t Be Intimidated

Some problems are intimidating because they are so complex or difficult that you can’t see a path to the solution. You may not even know where to start. Don’t let this lock you up. You don’t have to devise a plan for getting all the way to the solution before you start - things will come to you as you work:

• Break a problem into parts - If you can identify a subproblem, try solving that, even if you’re not sure it’s critical to solving the main problem.

• Try a simplified problem - Try solving a simplified version of the problem; you may gain insights that will be useful in solving the full problem.

• Try specific examples - If the problem involves some sort of process, try working through a few specific examples. You may notice a pattern you can generalize to other cases. Above all, keep talking, keep thinking, and keep working.

The pieces of the puzzle are much more likely to fall into place when your mind is in motion than when you are sitting at the starting line praying for a revelation. Even if you don’t make much progress, it looks much better to the interviewer when you actively attack a problem than when you sit back stumped, looking clueless and overwhelmed.

Remember that you came to the interview to demonstrate that you will be a valuable employee. Analyzing the problems and patiently trying a variety of approaches shows this almost as well as solving problems does.

Tip 

Don’t be intimidated by complexity. Try a subproblem, a simplified version, or some examples. Be patient, keep working, and keep talking.

Beware of Simple Problems

Other problems are tricky for the opposite reason: They are so simple or restricted that it seems that there’s no way to solve the problem within the given constraints. In these circumstances, brainstorming can be useful. Try to enumerate all the possible actions that are legal within the constraints of the problem, even those that seem counterproductive. If the problem involves physical objects, consider every object, the properties of every object, what you might do to or with each object, and how the objects might interact.

When you’re stuck on a problem like this, there may be something allowed by the problem that you’re missing. If you make a list of everything allowed by the constraints of the problem, it will include the key to the solution that hasn’t occurred to you. It’s often easier to enumerate all the possibilities than it is to specifically come up with the one thing you haven’t thought of.

When you do this enumeration, don’t do it silently; think aloud or write it down. This shows the interviewer what you’re doing and helps you be more methodical and thorough.

Tip 

When you’re stuck on a simple, restricted problem, brainstorm all the possibilities to identify the one you’re missing.

Estimation Problems

There’s one more type of problem worth discussing. This is the estimation problem, where you’re asked to use a rational process to estimate the size of some statistic you don’t know. These problems are relatively rare in interviews for pure development positions, but they may be more common in interviews for jobs that include a significant management or business aspect. One estimation problem is “How many gas stations are there in the United States?” It has been so widely reported that this problem was posed by Microsoft that it seems almost certain to be apocryphal; nevertheless, it is a good example.

These problems are usually not difficult compared with the more common brainteasers. You’re not expected to know the actual statistic or fact. Instead, you are expected to do a rough order of magnitude calculation based on facts you do know. Because everything is an estimate anyway, try to adjust or round your figures so that any large numbers you use are powers (or at least multiples) of ten - this will significantly simplify your arithmetic.

Taking the gas station problem as an example, your calculation might go like this: “It takes me about six minutes to fill up my car. I go to the gas station about once a week, and there are usually two other cars there. If I assume this is average for Americans, each gas station services about 30 cars an hour. Suppose a gas station were open 12 hours a day, 7 days a week. That would be 84 hours a week. In reality, a gas station is probably open more than 12 hours a day, so I’ll say the average gas station is open 100 hours a week. That means it services 3,000 cars a week. There’s somewhere upwards of 250 million people in the United States. Not everyone has a car, so suppose there are 100 million cars on the road. If every car goes to the gas station once a week, like mine does, and each station sees 3,000 cars a week, there would have to be about 33,000 gas stations in the United States.” This figure is probably off by a lot, but it’s likely within an order of magnitude (that is, there are more than 3,300 gas stations and fewer than 330,000). It’s much more important that you are able to form a framework for the estimation and rapidly work through the calculations than that you accurately estimate the statistic. For more practice, try estimating the number of kindergarten teachers in your state, the circumference of the earth, and the weight of a ferry boat.