|
I just read "How Would You Move Mount Fuji", a great new book by William Poundstone about puzzles as technical interview questions. I enjoyed it a lot - it is an easy read, and kind of "fluffy"; I blew through it in two days. I think it would be helpful for anyone seeking a technical position who is likely to be asked some of these questions. I'm more often in the position of interviewing people and asking these questions, and I found it terrifically helpful.
It isn't as Microsoft-centric as you might think based on the subtitle ("How the World's Smartest Company Selects the Most Creative Thinkers") - this was a pleasant surprise. I found it relevant to the startups I've been involved in as well as bigger companies.
Besides being useful, it was quite entertaining. I enjoyed the background on IQ testing, political correctness, and how puzzles came to be asked in technical interviews. I enjoy puzzle solving, and it was fun to be able to take a stab at the various "hard" questions given as examples in the book. I don't know if I would be hired at Microsoft, but at least I wouldn't hate their interview process.
The book is also pleasantly "current"; there are interviews with Joel Spolsky and Chris Sells, and links to a number of technical interview websites:
Interview Question Bank (Kiran Bondalapti)
Techinterview (Michael Pryor)
Interviewing at Microsoft (Chris Sells)
Riddles (William Wu)
How to hack the Microsoft interview
Ace the Interview
Key takeaways for me:
- Each interview question has a purpose. Typically you are trying to guard against "false positives", hiring people who don't work out. ("false negatives" or passing on people who would have been great is not nearly as harmful.) So you want to ask questions which all qualified candidates can answer well, so as to identify non-qualified candidates. Asking questions which only a subset of qualified candidates can answer is bad.
- Trick questions are not helpful. The candidate might know the trick or guess it, but that doesn't tell you much. Questions which require a steady logical approach but no great leap of insight are much better.
- There are two kinds of puzzle questions - those which have "an answer", and those which are asked to elicit a discussion but which don't have one right answer. The former are good as filters - if a candidate can't find the answer, you give a thumbs down. The latter are good for comparison purposes - you can contrast candidates' approaches and answers - and also they give you a better "feel" for the person.
Two points I think the booked missed:
- It is good to ask all the candidates for a position the same questions. Microsoft might be able to hire from a pool of 10,000 applicants, but in the real world you have an open position, you narrow the field to three qualified candidates you like, and you have to decide. Being able to evaluate their approach and answers to the same questions is very helpful - it makes for more of an apple-to-apple comparison.
- Interviewing is two-way, you want to qualify the candidate for the position, and you want to sell the candidate on the company/position. Perhaps Microsoft doesn't need to "sell", but in every real world situation I've been in my company did. Viewed this way, puzzle questions need to do two jobs, first, they need to help qualify candidates, and second, they convey information about the company and you, the interviewer. In the context of this second job, a question is better if it is "cool", fun, and relevant to what the company does. I sometimes take a puzzle question and shift it into a more relevant and entertaining context (instead of dwarves and pirates, use program managers and investors, instead of gold pieces, use iPods).
The book did a nice balanced job on whether puzzles are really a good technique in interviewing. On the one hand they are a good proxy for IQ tests, maybe better, because you really get some insight into how people think as well as how smart they are, and on the other hand they're pretty artificial, they don't necessarily relate to the tasks of the open position.
Clearly puzzles cannot take the place of "real work". If you're hiring a programmer, you have to see their code. Ask them to bring some examples with them, and ask them to code something during the interview. If you're hiring a marketing person, ask them to describe a product they worked on, how they characterized the market, how they designed the feature set, etc. If you're hiring a manager, ask them about management challenges ("give an example of a case where you turned an unmotivated employee around").
Puzzles do have an important role to play. First, they give you a good idea of how smart someone is. Maybe this isn't the only metric, or the main metric, but it is really important. You can't teach speed, and you can't teach intelligence, either. Second, they give you an idea of how people think. When they get stuck, can they get themselves un-stuck? Do they ask good questions? Do they enlarge the scope of the problem to look at a bigger picture? Do they simplify and try for something easy? Finally, puzzles give some indication of the type of personality a candidate may have. Some people like puzzles, like competition, like challenges. Some people don't. I'm not claiming either is better, but knowing this about a candidate is helpful in assessing whether they're a fit for your company and position.
Okay, okay, I'll give some examples. Here are my favorite questions from the book:
[ Later: There is more possible complexity to this question, please see Revisiting the Bridge of the Programmers. ] Finally, here is the worst question asked in the book:
- Mike and Todd have $21 between them. Mike has $20 more than Todd. How much does each have (you can't use fractions in the answer). [This question has no answer!]
Apparently sometimes people ask questions which have no answer to see how candidates react. This might be helpful in some situations (if you're hiring for a company with a confrontational culture!), but I would never use it; I don't like what it says about me and my company, and I can't imagine what it would say about the candidate, either.
[ Later: This question does have an answer - please see The $21 Question. ]
The book has more good questions, as do the websites linked above; if you're into solving puzzles, check them out...
Oh, and here's my personal favorite "work related question" (not from the book):
I just want to wrap up with one observation, which is also highlighted in the book. The interviewer's attitude when asking puzzle questions is very important. Ideally this should be fun, like "here's a cool problem, how would you solve it?" If the candidate has trouble getting started, gently guide them with hints. Generally I lead them around until they've definitely gotten an answer, so at least they don't feel like they've failed (even if I'm thinking they're not very smart because I had to pretty much give them the answer). You don't want the interview to be confrontational or unpleasant. You might decide not to make the candidate an offer, but you don't want them to form a negative impression of your company.
Got a favorite technical interview question or anecdote? Please share!
How many piano tuners are there in the world?
This is one of those questions which doesn't have a "right" answer; nobody really knows the answer, and you probably can't Google to find it. But there is a way to come up with a reasonable estimate, and this is obviously what the interviewer wants you to do. (I sometimes have asked "how many gas stations are there in the United States", which is the same sort of question. Other variations include "how many ping pong balls would fit in this building", "how much does a 747 weigh", and of course, "how would you move Mount Fuji".)
Here's one form of the answer:
- Estimate the number of people in the U.S.
- Estimate how many of them own pianos.
- Estimate how many "other" pianos there are.
- Estimate how long it takes to tune a piano.
- Estimate how often a piano needs tuning.
- Using 4 and 5, estimate how many piano tuners per piano.
- Using 2, 3, and 6, estimate how many piano tuners there are in the U.S.
- Estimate the number of people in Europe, Japan, etc. (First World)
- Using 7 and 8, estimate the number of piano tuners in the First World.
- Estimate the number of people in Russia, China, etc. (Second World)
- Estimate the ratio of First World to Second World pianos.
- Using 9, 10, and 11, estimate the number of piano tuners in the Second World.
- Estimate the number of people in the rest of the World (Third World)
- Estimate the ratio of First World to Third World pianos.
- Using 9, 13, and 14, estimate the number of piano tuners in the Third World.
- Sum 9, 12, and 15 to estimate the total number of piano tuners.
Plugging in the "right" numbers is not nearly as important as coming up with the approach. If you gave the above schema for computing an answer, the interviewer would be pleased.
[Return to question...]
How do you cut a rectangular cake into two equal pieces with one straight cut when someone has already removed a rectangular piece from it? (The removed piece can be of any size or any orientation.)
 This question definitely has a right answer. It might be argued that it involves a bit of a "trick", but I still like it. The trick is knowing or realizing that any line passing through the center point of a rectangle bisects it. Before you remove the rectangular piece from the cake, there are infinitely many lines which bisect the cake. After you remove the rectangular piece, there is only one - the line which passes through both the center of the cake, and the center of the removed rectangular piece. This line necessarily divides the removed piece in half, and hence the same amount of cake was removed from each half of the remaining portion.
The value in this question is not only seeing if a candidate can compute the answer, but watching them eliminate non-solutions. The fact that there is no constraint on the location of the removed rectangular piece is key. Perhaps they will ask for constraints ("can I assume the removed piece is along an edge"). I wouldn't say "no", I'd say "in what way is that helpful". They would probably realize after a little trial-and-error that such a constraint is not helpful, and that might guide them toward the solution.
P.S. There is another solution - cut the cake in half vertically! (With a single horizontal slice.) I'd say this gets points for creativity, but I'd still want to see the candidate solve the problem the other way.
[Return to question...]
You have five jars of pills and one scale. All the pills in one jar only are "contaminated", they weigh 9 grams instead of 10. How do you tell which jar is contaminated with just one weighing?
This is a classic technical interview puzzle. There really isn't a trick - it is a matter of working through the possible solutions to find one which works. There are possibly some assumptions you have to get out of the way - make sure you've framed the problem correctly - and then the answer emerges.
You basically have five unknowns - each of the jars could be the one which is contaminated. You are only allowed to perform one weighing, and the answer must discriminate amongst the five unknowns. So how does one weighing give you one of five possibilities? Well, clearly the result of the weighing is a number, so you have to design the experiment so the numeric result tells you what you want to know.
One of the assumptions you have to get through is that weighing the jars themselves is helpful. After a little thought you realize it isn't. Another assumption is that you can only weigh one pill from each jar. This is not a stated constraint, and in fact weighing only one pill from each jar won't get you the answer. The solution is to weigh a different number of pills from each jar. Say you take one pill from jar#1, two from jar#2, three from jar#3, and four from jar#4. (You can take five from jar#5 or more elegantly zero from jar#5, either way you'll get the answer.) Now there are five cases and five possible results:
- Jar#1 is contaminated. The weight will be 1x9 + 2x10 + 3x10 + 4x10 = 99.
- Jar#2 is contaminated. The weight will be 1x10 + 2x9 + 3x10 + 4x10 = 98.
- Jar#3 is contaminated. The weight will be 1x10 + 2x10 + 3x9 + 4x10 = 97.
- Jar#4 is contaminated. The weight will be 1x10 + 2x10 + 3x10 + 4x9 = 96.
- Jar#5 is contaminated. The weight will be 1x10 + 2x10 + 3x10 + 4x10 = 100.
This would be a pons asinorum for me, that is, if a candidate couldn't figure this out after a while, I'd probably consider them non-qualified.
[Return to question...]
Count in base negative 2.
This question is a little troublesome in that if the candidate has encountered it before, they'll probably breeze through it, and if they haven't, it might take them a moment to get their mind around the concept of a "negative base". I still like it.
So, a negative base. What does "base" really mean? Well, it determines the base for an equation of the form:
cnbn + cn-1bn-1 + ... + c1b1 + c0b0
The c coefficients are the digits in a number. If b < 0, then the factors with even exponents will be positive, but the factors with odd exponents will be negative. This makes for some slight weirdness. A system with base -2 needs two digit values, let's call them 0 and 1. Then:
1 = 1
10 = -2
100 = 4
1000 = -8
10000 = 16
And so on. Counting is a little counter intuitive. Here's the first few integers:
1 = 1
2 = 110 (4 + -2!)
3 = 111
4 = 100
5 = 101
6 = 11010 (16 + -8 + -2, if you get this, you've got them all)
7 = 11011
8 = 11000
9 = 11001
If a candidate got this far, I'd give them full credit. However, for extra credit they might note that this binary sequence also contains negative numbers! Here are the first few negative integers:
-1 = 11 (-2 + 1)
-2 = 10
-3 = 1101 (-8 + 4 + 1)
-4 = 1100 (-8 + 4)
-5 = 1111 (-8 + 4 + -2 + 1)
-6 = 1110
-7 = 1001
-8 = 1000
This is a pretty cool thing, that by using a negative base, all the integers are representable in binary! If a candidate thought this was cool, too, I'd think they were cool :)
[Return to question...]
You have three baskets filled with fruit. One has apples, one has oranges, one has a mixture of both. You cannot see inside the baskets. Each basket is clearly labeled, and each is labeled incorrectly. How can you determine what's in each basket by choosing only one fruit from one basket?
This question is kind of standard-issue; like the pill jars, it requires that you work through the possibilities logically. There is really no "aha", except maybe to pay attention to the given fact that each basket is labeled incorrectly. This is the key to the solution.
There are really only three choices - you can pull a fruit from the "oranges" basket, the "apples" basket, or the "mixed" basket. Let's see what happens in each case.
Suppose you walk up to the basket labeled "oranges", and pull out an orange. Since you know the basket is mislabeled, this cannot really be the oranges-only basket, so it must be the mixed basket. The other two baskets are labeled "mixed" and "apples". They're both wrong, so the one labeled "mixed" must be "apples", and the one labeled "apples" must be "oranges". Next suppose you pull out an apple. This could be the apples-only basket or the mixed basket, you can't tell! So pulling a fruit from the "oranges" basket is not helpful. By symmetry pulling a fruit from the "apples" basket would be equally, er, fruitless.
Now suppose you walk up to the "mixed" basket and pull out an orange. Since the basket is mislabeled, this cannot really be the mixed basket. And it can't be the "apples" basket, so it must be the "oranges" basket. The other two baskets are labeled "apples" and "oranges". They're both wrong, so the one labeled "apples" is really "mixed", and the one labeled "oranges" must be apples. The same logic applies if you pull out an apple, so this is the solution.
As with the pill jars, I really would expect to be able to coax a candidate through this problem successfully. Actually it is pretty easy, so I would hope they could figure it out for themselves. What I like about it is that it is a simple matter of working through a fixed number of choices, and this comes up in programming design all the time.
[Return to question...]
Four programmers must cross a rickety bridge at night. The bridge can only hold two of them at a time, and they have one flashlight between them. The four programmers cross at different speeds, Alex only requires one minute, Sam requires two, Pat requires four, and Francis requires eight. What is the shortest time in which they can all cross?
The most obvious solution which occurs to most people after working on this problem for a bit is as follows:
Alex + Sam -> far side (2 minutes)
Alex -> near side (1 minute, total = 3 minutes)
Alex + Pat -> far side (4 minutes, total = 7 minutes)
Alex -> near side (1 minute, total = 8 minutes)
Alex + Francis -> far side (8 minutes, total = 16 minutes)
This is a good solution because it uses Alex to ferry the flashlight back after each trip. Alex is the fastest, so this seems to make sense. Sam, Pat, and Francis each need to cross the bridge, so that's 2 + 4 + 8 = 14 minutes, and Alex has to come back twice, so that's 2 more minutes for a total of 16. How could that not be optimal?
Note: sometimes people give variations of this puzzle with non-power-of-2 values. That's fine, the problem still works, but I find this version to be best. Once you derive an answer of 16 to a problem with powers of 2, you really feel like "I got it".
After giving a sub-optimal answer to this problem, many people refuse to believe it is wrong. I love this problem for exactly this reason. If a candidate works it out by themselves, terrific, they get full credit, but if they get the good-but-wrong answer and accept that it is wrong, and continue digging, I give them full credit for that, too. (There is a bit of an "aha" involved.) Sometimes people don't believe there's a better answer, and start to argue with you; that's a bad sign; it is good to have confidence, but not good to be closed to new ideas.
So, how could this be done any better?
Before giving that part of the answer, let me digress for something else. The optimal answer to this question is actually 15. (Yep, it is, I'll tell you how in a moment.) Now if you were to ask: "how can the four programmers cross in 15 minutes", you may very well stump the candidate. This isn't what you want. Ideally you want the candidate to chew on the problem, work out a solution, and then defend it. This gives you a lot more insight into how the candidate thinks, and they have a sense of accomplishment. Otherwise if they fail to get 15, they'll feel bad, and you'll feel like you tricked them.
Okay, back to the optimal answer. The key insight - the thing which is a bit of an "aha" - is to have Francis and Pat cross at the same time. They're the two slowest, so essentially this gives you the second-slowest crossing for free. It isn't obvious how to make this happen, though; here's the most likely first attempt:
Francis + Pat -> far side (8 minutes)
Pat -> near side (4 minutes, total = 12 minutes, already something seems wrong)
Pat + Alex -> far side (4 minutes, total = 16 minutes, you know this won't work...)
Pat had to come back with the flashlight. This made his 4 minutes far from free, because not only does he have to come back, he has to cross again. Not good. So what if Pat didn't have to come back? What if a faster programmer were already on the far side and could bring the flashlight back instead? Aha!
Alex + Sam -> far side (2 minutes)
Alex -> near side (1 minute, total = 3 minutes)
Francis + Pat -> far side (8 minutes, total = 11 minutes)
Sam -> near side (2 minutes, total = 13 minutes, this is the key!)
Sam + Alex -> far side (2 minutes, total = 15 minutes)
Excellent, eh? And yet it is quite logical. An exhaustive analysis of all the possibilities in a relatively small solution space would find this easily.
[Return to question...]
Consider a pool table with the balls setup for a break. You must write a program which models the table, so you can predict where all the balls will end up. How do you approach this?
This question doesn't have a "right answer". I've found that candidates are usually a little bewildered by the problem - there seem to be a lot of hidden gotchas, like the fact the balls will hit each other - but good programmers methodically work through the situation and come up with a decent model. There are three things to look for in the candidate's answer.
First, do they deal all the physical constants out of the deck? Hopefully they can immediately ignore all that stuff, treat them as constants, and move on. When people ask detailed questions about the masses of the balls, pool cue velocity, etc., I get worried.
Second, do they take an object-oriented approach? To model a problem with sixteen identical balls, six identical pockets, etc., one would hopefully do so... If they don't go there themselves I'll ask "what objects would you need?", and "what are the properties and methods of each object?" If they can't think about the problem in this way, that's a red flag.
Third, how do they deal with time? Sometimes it takes a candidate a little while to realize time is a factor. (Some candidates never realize time is a factor!) Ideally they'll come up with some sort of discrete time simulation, where they have an outer loop that cycles through units of time, and computes the new position of each object. If they don't deal with time correctly their solution is incomplete. Sometimes candidates try to solve this problem with a completely analytical solution, where they model the table and then laboriously compute the trajectory of each ball. Naturally this involves the other balls, and so this becomes a computational nightmare. Strong candidates recognize this approach is too hard to be right, and backtrack.
A couple of things to watch out for on this problem... Occasionally I've interviewed candidates who were unfamiliar with the details of a pool table. You have to walk them through the shape of the table, the fact there are sixteen balls, the break position, etc. This definitely makes the hurdle higher. Fortunately most people have at least passing familiarity with pool. Also, some people get hung up on implementing their solution in a particular computing language. They start writing C++ classes or whatever. Although it is helpful to watch candidates code, this question isn't the right one to get them coding, because an actual solution is going to be too detailed and take more time than you have in an interview. So you have to gently lead them back to the concepts.
[Return to question...]
|
The wave of the future? Inter-species traffic signs in Vancouver. [ via 
