CHAPTER 19

Interview Puzzles

It's perfectly reasonable for a job interview to include questions that require you to use your skills to solve a problem. Each of this book's chapters contains exercises that might make good interview questions—at least if the candidate is well-versed in algorithms. Many of those questions would be quite difficult if you hadn't recently been reading about the relevant algorithms.

Recently, certain kinds of puzzles have also become popular in interviews at companies such as Microsoft and Google. The puzzles are intended to measure a candidate's creativity and critical-thinking ability. Unfortunately, these sorts of puzzles come with a large set of assumptions that may not be true. Most business situations, even in programming, are not phrased as puzzles involving balance scales, marbles, rickety bridges, and goats. They usually don't involve a clever trick or an amazing insight that is blindingly obvious after you hear it but that is practically impossible to figure out in a 10-minute interview.

It's true that finding the best solution to a real-world problem often requires creativity, but many of these kinds of puzzles don't measure creativity. Instead, they measure whether you've scoured the Internet long enough to find the problem that the interviewer is asking about, or something similar.

For example, consider the following questions:

1. Why are manhole covers round?
2. On which side of a car is its gas cap?
3. What is the significance of the phrase “dead beef?”
4. What is the next number in the sequence 17, 21, 5, 19, 20, 9, 15?

Take a moment (but only a moment) to think about these questions. Here are the answers, with some comments:

1. So that you can't pick one up, turn it on its edge, and drop it into the manhole. That's clever (although other shapes will work, particularly if the opening is relatively small and the cover is fairly thick), but the question asks you to work backwards from the solution to find the problem. How often does that occur in a real programming situation?
2. It's on the side opposite the exhaust pipe (unless the exhaust pipe or the gas cap is in the middle, in which case all bets are off). This question also requires you to work backwards from the solution (how to prevent gasoline from spilling on a hot exhaust pipe) to the problem.
3. Back in the days of mainframe and assembly programming, programmers could put the hexadecimal value 0xDEADBEEF in the code to make it easy to spot that particular location. This question doesn't test the applicant's creativity or intelligence; it just determines whether he or she ever programmed in assembly. And saw that trick. And remembered it. It would be easier to just ask how much experience the applicant has with assembly programming. (For the record, I studied some assembly programming, and I didn't run across this trick.)
4. The answer is 14. If you assign numbers to letters so that A = 1, B = 2, C = 3, and so on, the sequence in the question spells QUESTIO. If you figure that out, it's fairly easy to guess that the final letter should be N, which is assigned to the number 14. This question fools the applicant into thinking about numbers when he or she should be thinking about letters and encodings. Unless you're hiring a cryptographer, this probably isn't relevant. (If you are hiring a cryptographer, you're probably better off asking the applicant about Laplace transforms and hyperbolic curves.)

The Journal of Applied Psychology article “Why Are Manhole Covers Round? A Laboratory Study of Reactions to Puzzle Interviews” questions the usefulness of these kinds of interview questions. The article says this kind of question is not a very effective method for gauging an applicant's reasoning ability. Applicants may also feel these questions are unfair or arbitrary, and that may cause them to become uncooperative or to turn down the job if it is offered.

Does that mean these questions are worthless in interviews? They certainly are if you use them incorrectly.

The next two sections discuss how to handle these sorts of questions as an interviewer and as an interviewee.

Asking Interview Puzzle Questions

The preceding section gave some examples of bad interview puzzles. They rely on knowledge of trivia or, at best, the ability to work backwards from a solution to a problem. Working backwards does take creativity, but you can certainly be creative without that ability.

More than anything else, those problems tell you how well the candidate combed the Internet, looking for potential interview puzzles. There's some benefit in knowing that the candidate prepared thoroughly for the interview, but it doesn't really tell you much about his or her creativity or problem-solving ability.

To get useful information from a puzzle, you need a question that the candidate hasn't seen before. On the other hand, the puzzle can't be so impossibly hard that the candidate panics. It shouldn't rely on a trick or point of trivia that only measures whether the candidate happened to see a particular issue of some obscure magazine.

Unfortunately, that rules out a lot of puzzles. Those that remain include puzzles that ask the user to perform a calculation, make an estimate, or otherwise do something that may be straightforward but that gives the candidate room to explore possible approaches.

For example, one popular interview question has a form similar to this: “How many baseballs fit inside a school bus?” The candidate is highly unlikely to have memorized that fact, so this question is really asking the user to come up with an estimate. A good answer will list the assumptions that go into the estimate and perform a calculation. (Suppose a school bus is 36 feet long, the interior is 7 feet high, a baseball is 3 inches in diameter, and so on.) It doesn't really matter whether the assumptions are correct, as long as the process makes sense.

This question determines whether the candidate can perform back-of-the-envelope calculations, which is relevant to software engineering.

Another kind of calculation puzzle comes in a form similar to this: “If I'm three times as old as my brother, and in two years I'll be twice as old as he is, how old am I now?” (See Exercise 6 for the answer.) This is mainly an exercise in translating a word problem into a set of equations. That skill is certainly useful, but many people don't like word problems, and most real-world problems don't take this form anyway.

Clock puzzles have this form: “How many times do the hour and minute hands on a clock cross each other between noon and midnight?” (See Exercise 7 for the answer.) This puzzle and others usually can be solved by using a table and plugging in some values. That approach doesn't really let the candidate show off his creativity, but it does show that he can be organized.

Another way puzzles can be interesting is if you discuss the puzzle afterwards. For example, you could use a relatively simple puzzle that you're pretty sure the candidate can solve. Afterwards you can discuss why the solution works, how the candidate found the solution, what other approaches might have been worth trying even if they wouldn't work, and so on.

Alternatively, you could give the candidate a very hard puzzle, give him time to think about it so that you're sure he understands the constraints, and then discuss the solution. Now you can talk about different approaches you might take to reach that solution.

Probably a better approach than a simple puzzle is to describe a situation that resembles one you might encounter in your business. For example, you might say, “Let's design a database to store vacation plans for aliens from other planets.” This problem is big enough to give the candidate plenty of room to show his or her database design skills and creativity but is silly enough that the candidate probably won't panic. If you like, you can work through the problem together to see how the candidate interacts with others. You can propose strange twists and ask the candidate what might go wrong under different circumstances to see how creatively he or she handles unexpected problems. This kind of interactive challenge is harder to control, and different candidates may come up with very different solutions, so it may be hard to judge among them. But this challenge can teach you a lot more than a simple puzzle.

Puzzles can be interesting and entertaining but they're probably not the best way to measure the qualities you want in your job candidates.

Answering Interview Puzzle Questions

The preceding section argued that puzzle questions don't really measure the characteristics an employer wants in a job applicant. Instead of measuring your creativity and critical-thinking ability, they measure your ability to memorize trivia and scour the Internet to find these sorts of problems.

Just because these puzzles don't measure the qualities they seem to doesn't mean you won't see these sorts of questions in an interview. Some interviewers may use them to see how you handle pressure, respond to unreasonable demands, and cope with impossible problems. These sorts of puzzles may not measure creative thinking ability, but they may provide information about your psychological makeup.

So how should you respond to this kind of puzzle question? First and foremost, don't panic. Whether the interviewer expects you to solve the problem or just wants to see how you react, panicking won't help. This will make it nearly impossible to solve the problem and will create a bad impression.

Instead, focus on the problem. Once you start working on the problem, you won't have as much time to panic.

Many puzzles at technical interviews are related to programming. They may ask you to reverse the characters in a string, sort objects in an unusual way, copy a data structure, or perform some other straightforward but confusing task. In those cases, think about the algorithmic techniques you know. Here are some techniques you should consider:

• Divide and conquer—Can you break the problem into pieces that are easier to solve?
• Randomization—Does the problem include worst cases that could be avoided with randomization?
• Probability—Can you think of a probabilistic method that uses guesses to find a solution or that solves the problem with some probability?
• Adaptive techniques—Can you think of an approach that focuses on specific parts of the problem? Are there really only a few true areas of interest, with most of the problem being there to confuse the issue?
• Data structures—Does a certain data structure (linked list, array, stack, queue, tree, balanced tree, network) map naturally to the problem? Does a certain data structure have behaviors similar to the ones you need to solve the problem?
• Problem structure—Is the problem's structure naturally recursive, hierarchical, or similar to a network? Can you use tree or network algorithms to search the data?
• Decision trees—Can you apply decision tree search methods to the problem? (Often you can, but it would take too long.) You might say, “Well, we could try examining all possible combinations of the data, but that would take forever. Perhaps a divide-and-conquer approach would be better.”

If you get stuck, you can also try some of the following general problem-solving tips:

• Make sure you understand the problem. If it contains ambiguities, ask for clarification.
• Restate the problem to be sure you understand it. If you have made a bad assumption, the interviewer may correct you.
• Compare the problem to other problems you have seen in the past.
• Break the problem into smaller pieces. If the problem is large, look for pieces you can solve separately.
• Focus on the details. Sometimes the smaller details are easier to handle.
• Focus on the big picture. Sometimes the details don't make sense except when seen together as a whole.
• Make a list of facts you know.
• Make a list of facts you would like to know. List ways you might learn those facts.
• Make a table of values. See if you can extend the table to new values.
• Guess and check. You can solve some problems by making a guess and then adjusting to get the result you need.
• Think outside the box. If the problem is about numbers, think about letters, shapes, and other nonnumeric values. If the problem is about letters, think about numbers.
• Brainstorm. Talk out loud about the kinds of approaches you might take. This may be a good time to let the interviewer know what techniques you understand. “Binary subdivision probably won't work... the problem is naturally recursive, but that would lead to an infinite series of operations...” Again, the interviewer may correct you. At a minimum, you'll be telling the interviewer some of the techniques you know.
• Draw a picture if one makes sense. Sometimes seeing a problem graphically instead of textually can help.
• If you get stuck with one approach, try another. The interviewer doesn't want to see you struggling to use the wrong approach long after it's clear that it won't work.
• Stick with it, or give up. If you have the time and the interviewer clearly wants you to spend a lot of time on the puzzle, do so. If it doesn't seem like you have enough time, it may be better to ask the interviewer if you should continue.

Failing to solve an interview puzzle doesn't necessarily mean you failed the interview. If you try hard, exhaust all the approaches you can think of, and are clearly getting nowhere, it may be better to ask whether you should stop. You might say something like, “It seems like a recursive approach would be promising, but I think I'm missing something. Do you want me to keep working on this?” If the interviewer wants you to continue, he can say so.

Even if you fail to solve the problem, the interviewer probably will learn something from your attempt. If you talk as you work, he probably will learn about some of the approaches you know and something about how you think about problems. He also will see what you do to understand the problem before trying to solve it and how long you work before giving up.

One thing you should never do is try to pick apart the interviewer's questions to prove how stupid they are. While looking for websites that contain puzzle-style interview questions, I came across an article in which the author gave a series of “snappy comebacks” to the interview question “How would you design a routine to copy a file?” The article had the applicant ask all kinds of questions about what kind of file it is, whether the file's permissions should be copied, whether the file should be encrypted, whether it should be marked for backup, and other detailed questions until the fictional interviewer was frustrated to the point of saying, “Look, just copy the damn file.”

The article's point was that this is a stupid question, because no one writes his or her own routines to copy files. That's true in most cases, although I've worked on projects where copying files was particularly tricky due to file locking issues. In fact, the biggest bottleneck in their whole operation involved copying tens of thousands of files per day multiple times across a series of computers that performed various operations on them. Even a small mistake in copying files resulted in lost files or a backlog of hundreds of thousands of files. Even if a question seems pointless, you can't be sure of that until you know the background behind the question.

Proving how smart you are and how stupid the question is won't land you the job. At best, you'll show impatience and a lack of interest when confronted with a problem. At worst, you'll alienate the interviewer, imply that you cannot solve the puzzle, and give the impression that you don't care about the employer's problems.

A much better approach is to inquire why the interviewer is asking the question so that you can understand his point of view and come up with an appropriate response.

Summary

Interviewers sometimes use puzzle questions in an attempt to measure a candidate's creativity and critical-thinking skills. Those puzzles don't do a very good job of that, although they may provide some insight into how a candidate deals with frustrating situations.

If you're an interviewer, avoid puzzles that rely on trivia, that require the candidate to work backwards from a solution to a problem, or that are so difficult that the candidate would be lucky to solve them. Puzzles that make the candidate perform back-of-the-envelope calculations are better and more relevant.

Better still are questions that are similar to those the candidate may actually encounter at work. You also can use exercises similar to the ones included in this book or other books about algorithms and programming in general. You should be careful not to pick questions that are too difficult, however. Only someone who has studied algorithms extensively or fairly recently will remember the finer points of balanced-tree rotations or how to show that Optimization ≤_p Reporting (or even know what that means).

You can usually learn more about what the candidate knows by asking questions and discussing problem-solving approaches than you can by posing a single puzzle that may happen to fall outside the candidate's experience.

If you're a candidate, try not to panic or be offended by puzzle questions. Make sure you understand the problem, and give it your best shot. Remember, failing to solve a problem doesn't necessarily mean you've also failed the interview.

You can find a huge number of puzzle questions online by searching for “interview puzzle questions.” Read a bunch and get a feel for the kinds of things interviewers ask and the kinds of approaches required to solve them. Even if you don't face these sorts of puzzles in an interview, they can be interesting and fun, so you won't have wasted your time.

However, don't forget to work on the other parts of your interview skills. Brush up on your algorithms, database design, architecture, project management, and other relevant skills. Last but not least, don't forget to get a good book or two about how to prepare for interviews more generally.

See the following links for some sites that provide particularly interesting puzzles, puzzles that have been used by companies such as Microsoft and Google, and information about puzzle questions:

• How effective are puzzle interview questions?: http://resourceszone.com/blog/how-effective-are-those-puzzle-interview-questions
• 10 Google interview puzzles: http://www.mytechinterviews.com/10-google-interview-questions
• 10 famous Microsoft interview puzzles: http://www.mytechinterviews.com/10-famous-microsoft-interview-puzzles
• How to Ace a Google Interview: http://online.wsj.com/article/SB10001424052970204552304577112522982505222.html
• techinterview: http://www.techinterview.org
• Facebook interview puzzles group: https://www.facebook.com/interviewpuzzles
• Haidong Wang's interview puzzles (note that the answers to many of these are not posted on his site): http://www-cs-students.stanford.edu/~hdwang/puzzle.html
• Top 5 Microsoft interview questions: http://dailybrainteaser.blogspot.com/2010/08/top-5-microsoft-interview-questions.html
• A2Z Interviews: puzzles (these have answers but not explanations): http://www.a2zinterviews.com/Puzzles/logical-puzzles
• Interview aptitude questions: http://www.knoowgle.com/Puzzles
• CoolInterview puzzles: http://www.coolinterview.com/type.asp?iType=619
• CareerCup: http://www.careercup.com
• Math Olympiads (This site supports the Math Olympiads organization, which organizes math competitions for students in grades 4 through 8. Many of the problems are similar to interview puzzles, and they're pretty fun.): http://www.moems.org

Many books also cover these sorts of puzzles. Look for them in your favorite bookstore.

One book I've seen that includes puzzles that are mostly relevant to programmers is Cracking the Coding Interview by Gayle Laakmann McDowell (CareerCup, 2011). Many of the puzzles test your understanding of important data structures and programming techniques, although a few “clever trick” problems require you to have encountered a particular technique (such as the tortoise-and-hare algorithm). (I'm sure other good books are available. This is just one that I found interesting.)

Exercises

The following exercises are brief examples of some common types of interview puzzles.

1. A man has a dresser drawer containing 10 brown socks and 10 black socks. He gets up early and wants to find a pair of socks without turning on the bedroom light and waking up his wife. How many socks should he take into the living room (where he can turn on the light) to guarantee that he has a matching pair of socks?
2. You are given 10 black marbles, 10 white marbles, and two bowls. You may divide the marbles between the bowls any way you like. Then you are blindfolded, the bowls are shuffled, and you reach into a bowl and pick out a marble. How should you distribute the marbles to maximize your chances of picking a white marble?
3. If you randomly arrange four red marbles and eight blue marbles in a circle, what are the odds that no pair of adjacent marbles has the same color?
4. If you randomly arrange four red marbles and eight blue marbles in a circle, what are the odds that no pair of adjacent marbles is red?
5. What would be the best data structure for reversing a list of customer records without using additional memory?
6. If I'm three times as old as my brother, and in two years I'll be twice as old as he is, how old am I now?
7. How many times do the hour and minute hands on a clock cross each other between noon and midnight?
8. The people in a certain country particularly value boys, so every couple has children until they get a boy, and then they stop having children. Assuming boys and girls are equally likely, what is the total percentage of girls in the population?
9. You hire a consultant who wants to be paid in gold. The job will take between one and seven days (you don't know ahead of time). If the job takes the full seven days, you will give the consultant a small brick of gold. If the job takes less time, you will give the consultant 1/7th of the brick per day worked. What is the fewest number of pieces into which you must cut the brick so that you can pay the consultant no matter how many days the job takes?
10. You have eight golden eggs, but you know that one is only gold-plated, so it's lighter than the others. You also have a two-pan balance. How can you find the gold-plated egg in only two weighings?
11. You have five unlabeled pill bottles containing between 10 and 20 pills each. Four of the bottles contain 1-gram pills. The fifth contains placebos that weigh 0.9 grams. How can you use a digital scale (one that shows you a weight in grams, not a two-pan balance) to determine which bottle contains the placebos in a single weighing?