A Programming Interview Question, Explored
TweetAt my office recently, we’ve been brainstorming often about programming interview questions. I especially dislike giving interviewees puzzlers or gotcha type questions. I define a gotcha question to be one that doesn’t have a good continuum of hints that you could provide. There is some trick that they either figure out or they don’t. It’s very black and white. There are a bunch of reasons that these questions are bad questions. The primary one is they don’t really give you the information you are naively hoping they will. They won’t tell you if someone is smart. But my interview ideology is something for a different day.
Let me give you some examples of gotcha style questions.
- Determine if there are any loops in a linked list? Now do so without marking any of the nodes, or any other supplemental arrays or other forms of book-keeping.
- Given a room with three switches connected to three light bulbs in
another room. There is no way to see from one room to the other. You
start in the room with the switches and are allowed to switch them as
you see fit. Once finished, you go to the room with the light bulbs.
Upon seeing the state of the bulbs, can you figure out which switches
controlled which light bulbs?
These questions, as posed, require lightning strike of cleverness that can’t be expected in an interview. Furthermore, though, what represents the fatal flaw in these types of questions is that most often someone who answers correctly does so only because they’ve heard the question before.
Good technical interview questions are the type of questions that have obvious trivial (and sub-optimal) solutions that allow you to iterate from least clever to most clever with some careful prodding. This allows you, the interviewer, to give them progressive hints that allow them to show how big of a leap make on their own. Compare this to a gotcha question where you’d sit there in silence where the only hints you can give are far too big. They are going to look around confused and pretty soon the combination of silence and lack of progress is going to distract them from the problem at hand. After a sufficient amount of awkwardness you are going to just tell them the answer, and they’re going to do their best acting job to make them seem as smart as possible upon discovering this incredibly insightful trick. In their own head, they’ll think you are a dipshit.
There are alot of good questions of the iterative variety but I’ve chosen one that illustrates the iterative nature perfectly. That said, this particular question probably isn’t suitable for an interview because a full discussion of it probably takes too long. The real reason I want to talk about this question is because the most often stated answer is, at best, flawed, but I prefer to think it’s just plain wrong.
A Knight and a Dragon
I first read this problem here: http://www.ocf.berkeley.edu/~wwu/riddles/easy.shtml. Here is my variation…
A dragon and knight live on an island. This island has six poisoned wells, numbered 1 to 6. If you drink from a well, you can only save yourself by drinking from a higher numbered well. Well 6 is located at the top of a high mountain, so only the dragon can reach it. One day they decide that the island isn’t big enough for the two of them, and they have a duel. Each of them brings a glass of water to the duel, they exchange glasses, and drink. Who dies and who lives?
Let me start by saying that the problem is not perfectly well defined. Some things are left to the listener to assume. I’ve taken the liberty of making some “reasonable” assumptions in my discussion (e.g., one doesn’t feel sick when he is poisoned, and drinking same-level poison does nothing). A good interview would likely contain discussion of these assumptions.
The Trivial Answer
Obviously, the dragon kills the knight by feeding him poison #6 which he cannot cure. Similarly, the dragon can cure any poison that knight has given him by flying up to #6 after the duel. This answer should immediately seem “too obvious” and therefore give anyone pause as choosing it as correct.
Step 2: The “Official” Answer
Once the trivial answer is stated, we can continue by getting to the meat of the issue:
If I told you that the Knight was very clever and the actual result was that he lived, and the dragon died? Can you figure out how this could happen?
The knight knows the dragon will try to poison him with #6. He can use this to his advantage. If the knight pre-poisons himself (say, by drinking from the level 1 well) before coming to the duel, the dragon’s offering of level 6 poison becomes a cure. Similarly, he can provide the dragon with fresh water at the duel. The dragon will then, believing himself poisoned, fly to the top and poison himself with now incurable level 6 poison.
This answer is usually how the riddle is “solved”. Note my scare quotes. This answer is incredibly unsatisfactory because it depends on an assumption of a (somewhat) stupid dragon. In some sense, it’s just plain wrong. A dumb dragon wouldn’t behave this way and neither should a smart dragon.
Step 3: The Real Answer
What if we assume both are equally clever? What’s the optimum strategy for both Knight and Dragon?
Would it surprise you if I told you that the Knight cannot kill the dragon? Want to stop and think about it? The dragon can only successfully cure himself with the level 6 poison if he is already poisoned. He cannot be sure he is poisoned after the duel. Is that enough of a hint? What if we go step by step? What does the dragon know before the duel. What about after? What happens if he knows he poisoned by levels 1-5 water? The answer should become increasingly obvious and I’m sure most of you figured it out relatively early in this paragraph.
The simplest way to do this is for the dragon to go to the duel, drink the knight’s water and then go to the level 1 well and drink. By drinking level 1 poison, the dragon has assured himself of being poisoned with at least level 1 water and at most level 5 water. This guarantees that level 6 water will cure him.
How about the Knight? Surely the disadvantage of no access to the level 6 well dooms him, right? What if I told you that the Knight, also, should always survive? Want to figure it out?
The logic follows almost identically from the dragon’s situation. If the Knight gets poisoned by level 6 water, he dies. Therefore, he must come pre-poisoned in order to avoid getting level 6 poisoned. Therefore, after the duel, the Knight is either cured by some higher level poison, or has his original level of poison. Given that knowledge, the Knight can pre-poison himself with level 1 and go to the duel. After the duel, he is either level 1 poisoned or cured. By re-drinking level 1, he guarantees himself to be level 1 poisoned. He can now cure himself at any of the higher level wells.
So as it turns out…
So, as it turns out, the dragon’s advantage of having the level 6 well isn’t really an advantage. The game as posed turns out to be alot like tic-tac-toe. Someone appears to have a huge advantage but only against sub-optimal play. Against optimal play, neither person can win.
The real interesting question: what variations of this problem could make it more difficult or produce more interesting results?
twitter
August 22nd, 2008 at 10:25 pm
Excellent, if this comes up in an interview I’ll know what to say
August 22nd, 2008 at 10:32 pm
Why are seven wells numbered from 1 to 6? which one is duplicated?
August 22nd, 2008 at 10:47 pm
“This island has seven poisoned wells, numbered 1 to 6.”
Where’s the seventh well?
August 22nd, 2008 at 11:53 pm
I believe he meant “several” not “seven”.
August 23rd, 2008 at 1:58 pm
Ugh. Typos. Actually what happened was when I wrote this, away from the internet, I thought the original had six, not seven, so when I wrote all the text as if there was six wells. When I pasted the problem into the blog, I missed changing one of the sevens into a six. The amount of wells is irrelevant as long as there are enough.
Sorry!
September 16th, 2008 at 5:03 pm
Curious question: can’t the dragon also drink level five well water before the duel, thus guaranteeing that he’s at least level five poisoned in advance?
September 16th, 2008 at 6:18 pm
What if the dragon “poisons” wells 2-5 with water from well 1 before the duel?
September 16th, 2008 at 7:54 pm
The simplest way is for the dragon to kill the knight. Big dragon. Small puny knight. Game over.
September 16th, 2008 at 9:55 pm
Isn’t this still a gotcha-style question?
You’re depending on the interviewee either asking or assuming that somehow the well #5 poison disappears when the knight drinks from well #1, and thus, even though he drank from well #6 (assuming that’s what the dragon handed him), he’ll be fine after drinking #1 and then #2.
September 16th, 2008 at 9:56 pm
Sorry- I meant the well #6 poison disappears when (…)
September 16th, 2008 at 10:57 pm
There were a couple of things that bothered me
-the fresh water thing, if that’s their answer i guess it shows thinking outside of the box, i guess you did say island.
-drinking the same level poison is not cumulative, so if you drink the level above your highest poison level cured of all previous poisonings.
September 16th, 2008 at 11:08 pm
1) How is this not a ‘gotcha’ style question? 2) They both die because their aren’t an infinite # of wells, only 6 (how can they cure the lvl 6 poison after ‘curing’ the lower levels)?
September 16th, 2008 at 11:20 pm
This question is weird. Say someone drinks from well 1, the problem (and subsequent “solutions”) seem to state that:
1) Drinking from well 2 will “save” them
2) Subsequently drinking from well 2 (in an unpoisoned state) will “poison” them.
This makes everything very murky. For example:
“Given that knowledge, the Knight can pre-poison himself with level 1 and go to the duel. After the duel, he is either level 1 poisoned or cured. By re-drinking level 1, he guarantees himself to be level 1 poisoned. He can now cure himself at any of the higher level wells.”
Alternatively, he could go and drink level 4 twice (either cure then re-poison, or poison, re-poison), then level 5.
In fact, this sequence is just as good: 4, (mystery), 4, 4, 5.
General solution:
First drink: X (X<=4)
Second drink: unknown
[poison level is now 0..X]
Third drink: Y (1 <= Y < X)
[poison level is now 0, or between Y and X]
Fourth drink: Y
[poison level is now between Y and X]
Fifth drink: X+1
[poison level is now 0]
Plenty of options there. The simplest solution would be 1, ?, 1, 2.
By the same reasoning, you can’t kill the dragon.
September 17th, 2008 at 12:38 am
if i was asked any of these types of “brain teasers” i would walk out of the interview.
September 17th, 2008 at 12:54 am
Another posting from the cult of stupid questions and technical trivia.
September 17th, 2008 at 7:16 am
Anyone who asks that sort of question for a programming interview should not be interviewing. It’s a ridiculous question.
September 17th, 2008 at 8:20 am
Another interview question:
A knight goes to an interview with a king of a nearby kingdom. The knight arrives expecting to be quizzed on topics such as dragon slaying and protecting the king, but much to his dismay, he is asked the following questions:
“You have an array of size ’2n’ of these, ‘n+1′ elements are distinct and 1 element is repeated ‘n’ times. You must find the repeated element and say how many times it has repeated. Your solution must use minimum no. of comparisons. Also, say how many comparisons your solution will make in the worst case?”
Unsure of what the hell the king was talking about and deciding that he is obviously insane for asking such a ridiculous question, he does the honorable thing by drawing his sword and running the poor old coot through, thereby releasing his kingdom from his deranged tyranny. He then returns to his own country and his own king who, while not the most generous of employers, at least knows what knights do for a living.
M@
September 17th, 2008 at 9:24 am
I find the “loop in a linked list” question to be very useful. But it depends on how you ask it.
We begin by asking the question with no strings attached: Can you find loops? Use as much memory and CPU as you wish. Take your time, and talk through it out loud if you can.
It’s in the “talking it through” bit that we learn the most. There is room for a lot of back and forth that lets us probe what the person understands and doesn’t understand about computer science and programming.
Then we gradually tighten the question. Again, we have a discussion about it.
By starting simple, getting more complex, and engaging the interviewee, it’s a very useful question, as part of a larger set of questions.
-alain
September 17th, 2008 at 9:36 am
You guys that are instantly dismissing any question that attempts to make a metaphor for algorithms in non-programming terms are making a critical mistake. The set of questions that are “brain-teasers” are not the same as the set of questions explicitly spelled out in programming terms. I agree that brain-teasers (or gotchas) make poor interview questions because of the reasons I stated at the top.
But if I dress up a simple programming problem as a problem involving a bridge or a building or a dragon and you don’t instantly recognize I’m just asking you to sort a list, we’ve got problems.
September 17th, 2008 at 12:22 pm
I don’t think that I or others are necessarily prejudiced against metaphors. After all, very few of us are accessing this page using the command line, so we are all participants in some of the most outrageous metaphors ever created (web, desktop, etc.). But when the problem is so fantastic that the laws of physics have to be suspended, it really isn’t very useful. By discounting everything that is familiar, you destroy the purpose of the metaphor, which is to frame an unfamiliar topic in a familiar context. This is an anti-metaphor. It frames a fairly familiar programming concept in a unfamiliar, alien physical world where the established rules don’t apply.
If you want to ask metaphor (or brain teaser or gotcha or whatever) questions, at least make them realistic on their own. Use luggage on airplanes or dogs and chickens crossing a river or something that we are all instantly familiar with the laws that govern their behavior. OK, I concede that luggage would not be a good example. Even airlines don’t have a grip on that reality.
M@
September 17th, 2008 at 10:52 pm
wow i wish i was a smart programmer like you guys…its fun to read anyway, so that is the first step toward higher levels of geekdom.
September 18th, 2008 at 9:41 am
I think there is a giant flaw in this kind of interview question. I couldn’t figure any of the steps of this riddle out, while reading it. Granted, I didn’t stop to think more than a few seconds, but still. I see my self as a rather good programmer, but I really suck at these kinds of riddles. I also suck pretty hard at algorithms in programming. I couldn’t tell a bubble sort and a quick sort apart, on sight. The thing is though, that it doesn’t matter in my daily work. If I need an algorithm, I friggin look it up. I don’t spend time to work it out on my own. If you need a developer who can crunch numbers, then perhaps this kind of question is appropriate. I’ll claim that this isn’t a relevant skill in most programming positions.
September 18th, 2008 at 10:16 am
The dragon does have an advantage, because he knows the knight has to have pre-poisoned himself. Therefore, all he has to do is give the knight un-poisoned water, and he wins.
September 20th, 2008 at 4:43 pm
No, after the duel, the knight has to drink from well 1 again followed by well 5. So, if the dragon gives him water from well 6, he’s not poisoned and goes through the cycle of poisoned/not poisoned. If the dragon gives him fresh water, which we assume exists on the island, he’s poisoned with well 1, he basically drinks more from well 1 and then well 5 to cure himself.
I have to say this is yet another stupid programming question. It doesn’t in any way pertain to domain space of building good software systems or products or even the domain space of what the software is suppose to solve.
Someone who is good a solving puzzles or possibly took a course in game theory could work this out. How does this question determine whether the interviewee is a good programmer?
My accountant who loves riddles could solve this puzzle but sucks at coding.
September 20th, 2008 at 6:55 pm
@mike, and others,
I sympathize with people who say this is a bad interview question. I even said as much in the article. I disagree on the reasons why, however.
The meat of the problem amounts to developing an algorithm (which is what an optimal strategy is). I don’t see how anyone can reject algorithm development as a necessary skill for programmers.
I think you could easily object that there’s alot of unstated rules that need to be assumed and therefore it’s a bit more of a brain-teaser or puzzler than a simple algorithm metaphor. I think that’s a valid point. But if we brush those issues aside and state the problem more clearly, it becomes a simple “make me an algorithm” question.
September 22nd, 2008 at 10:14 am
lbrandy.com » Blog Archive » Here be the Code Monkeys says:[...] started when I was completely struck by some of the responses to my post about the Knight & Dragon problem. For those of you that don’t want to read it, it is basically a puzzle which effectively [...]
October 27th, 2008 at 11:53 am
when i was in grade 8 we loved to play dungeons and dragons…
but now i’m 48 and don’t have time for trivialities and would ask you if you wanted to hire a person who knows all about WOW or someone who actually can do some work within the budget of your department and within the timeline of the customer.
Either you went to school and learned or else you just read WROX/o’Rielly books…talking with you for about 5 minutes would reveal that and any other “tests” like this will hint at someone having a “superiority complex” (which I mean in the nicest of ways of course).
wait another 20 years and re-read your posting…then grasshopper…you will understand
March 4th, 2009 at 5:05 pm
You’re mis-stating the original riddle.
Here are the differences:
1. There are no other sources of water in the Kingdom other than the wells.
2. Neither is permitted to go & drink subsequent to the duel.
3. The duel is actually: They each bring *two* glasses of well water to the duel. Each gives one glass to the other to drink. Each then drinks from a glass he brought with him.
4. The Knight lives & the dragon dies. How?
The canonical answer is that the dragon brings two #6 glasses, under the assumption that he will give the Knight water for which there is no antidote, & under the assumption that whatever the Knight brings, he has the antidote for.
The Knight drinks from well #1 prior to the duel. He drinks the #6 the dragon gives him, which is the antidote for the #1 he had prior to the duel. He then need to drink what he brought. What did he bring? He brought a mixture of well #1, mixed with well #2 which neutralized #1, creating a placebo.
The Knight gives the dragon a similar #1/#2 concoction. The dragon drinks the innocuous water, then poisons himself with his own #6 & dies.
There you go.
I’m a programmer, by the way.
20+ years on Wall St.
March 4th, 2009 at 5:06 pm
You’re mis-stating the original riddle.
Here are the differences:
1. There are no other sources of water in the Kingdom other than the wells.
2. Neither is permitted to go & drink subsequent to the duel.
3. The duel is actually: They each bring *two* glasses of well water to the duel. Each gives one glass to the othe
r to drink. Each then drinks from a glass he brought with him.
4. The Knight lives & the dragon dies. How?
The canonical answer is that the dragon brings two #6 glasses, under the assumption that he will give the Knight wa
ter for which there is no antidote, & under the assumption that whatever the Knight brings, he has the antidote for
.
The Knight drinks from well #1 prior to the duel. He drinks the #6 the dragon gives him, which is the antidote for
the #1 he had prior to the duel. He then need to drink what he brought. What did he bring? He brought a mixture
of well #1, mixed with well #2 which neutralized #1, creating a placebo.
The Knight gives the dragon a similar #1/#2 concoction. The dragon drinks the innocuous water, then poisons himsel
f with his own #6 & dies.
There you go.
I’m a programmer, by the way.
20+ years on Wall St.
May 16th, 2009 at 11:59 am
Tagz | "lbrandy.com » Blog Archive » A Programming Interview Question, Explored" | Comments says:[...] [upmod] [downmod] lbrandy.com » Blog Archive » A Programming Interview Question, Explored (lbrandy.com) 1 points posted 8 months ago by SixSixSix tags imported career interviews [...]
November 5th, 2010 at 6:30 am
As a biologist/would-be programmer (who happened to land here by typing “genetic algorithms”, heh), this question was nearly non-sensical to me.
Because, well, I mean, a “biologist” would instantly react to this by assuming that both would still be poisoned. The idea that a poison (e.g. from well #6) can be a cure for another one is actually very valid (hell, even arsenic, which is very, VERY toxic, is used as a drug in certain cases of leukemia), but for a substance to be effective both as a cure and a poison (which is the cas for the substances of wells #2 to #6), it has to be quite concentrated.
Therefore, if one was to drink from well #6 to cure oneself from another poisoning, one would still be poisoned because of the still-too-high concentration of the poison of well #6 in one’s blood (my my this is a complicated sentence).
I don’t know if I was clear enough, and of course this kind of considerations should not be taken into account for what is essentially a riddle. Yet, I think this shows that different people with different background would respond in very distinct ways to this kind of question.
By the way, your blog is really, really good. I’ve learned a lot of things, and you’ve even made me want to learn C.
Bruno
PS : Sorry if there are grammar mistakes, I try to improve my English as much as I can, but the mistakes you don’t see are the worst to get ride of.
PS 2 : Would you have any advice on a good textbook on pattern recognition and signal analysis ? You mentioned it a couple of times.
April 18th, 2012 at 3:34 am
First stage: the leader and subordinate meet, discuss and identify κλιματιστικά clear and well defined objectives of the activity to be performed by him for a certain period of time.
April 18th, 2012 at 6:27 am
This method consists in carrying on a conversation between manager климатици and employee evaluations of the results of his work.
May 17th, 2012 at 2:12 am
This summer the room temperature is lower than the pvc дограма standard and the winter is higher. Glass Sunenergy savings on heating and air conditioning, автоклиматици thanks to its excellent production technology.