 |
 |
|
|
|
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.
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:
Key takeaways for me:
Two points I think the booked missed:
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:
Finally, here is the worst question asked in the book:
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:
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.
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.)
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.
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:
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.
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:
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:
And so on. Counting is a little counter intuitive. Here's the first few integers:
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:
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 :)
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.
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:
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
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?
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:
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!
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.
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.
|
|
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.
