To Joe Mabel's home page | To Joe Mabel's resume

1 | 2 | 3 | 4 | 5 | 6 | 7 | 8

The Interview Brainteaser and its Discontents - 6

(This is the continuation of an article about the use and abuse of brainteasers in job interviews. This page contains the third of three examples drawn from actual interviews.)

A Pirate as Emissary

The problem, as posed, reiterated:

The problem as posed: "There are two kings, each on an island. Each king has one valuable diamond, one box, one lock, and one key. The king on the first island has a daughter (so we'll call him the Daughter King). The king on the second island has a son (so we'll call him the Son King).>/q>

"The only way between the islands is a pirate ship. The pirate is open to doing a bit of commerce, but he's a pirate. If he can get the diamond and keep it, he will. The kings, on the other hand, are honest, which is to say that they don't steal and they keep their word.

"The kings are trying to arrange a marriage between their respective offspring. The diamond is what proves how great a king is. The Son King has demanded to see the diamond belonging to the Daughter King. The Daughter King is willing to show it to him. How can he show off his diamond (and get it back) without any possibility of its being stolen? "

Confusing? Inherently so, I think. I've actually eliminated a few red herrings from the original, even more complicated, statement of the problem; also, just to make it a little saner, let's stipulate some hidden assumptions that came out in the course of discussion:

  • There's no way to break the locks. Only the correct key will open the lock. The locks are totally distinct from one another.
  • The pirate can copy a key. Once the key has ever been in the pirate's hands, the corresponding lock is no longer secure.

There is a lot going on here. If you are into brainteasers and are trying to "solve" this, you might want to think about the problem before you read any further.

Naive "solutions"

There is a naive "solution" analogous to public key encryption: the Son King sends an empty, unlocked box, the Daughter King puts the diamond in the Son King's box and locks it. He sends it back to the Son King who unlocks it. The equivalent protocol is used with the other box to send the diamond back. The pirate never touches a key -- only boxes move back and forth, not keys -- so he can't unlock the box. This is exactly analogous to public-key encryption.

There is also a variant of the problem in which you don't need the key just to unlock the lock: you need the key to lock it. Under this variant, you cannot avoid eventually sending a key. At some point, the pirate has to get his hands on a key.

In this variant case, one might expect to solve this with something like: the Daughter King locks the diamond in the box and sends it. Once that has safely arrived, the Daughter King sends the key to unlock the box. The pirate has the key, but he'll never see the box again, so that's OK. The equivalent protocol is used (with the other box, lock, and key) to send the diamond back. Obviously, you can only do this once, but that's all the problem called for. You have exactly as many boxes, keys, and locks as you need.

As you will see below, I do not consider either of these "solutions" to be correct. I believe that the problem is, in fact, not solvable.

[Correspondent Arvind C. wrote me on December 9, 2002 to point out that the variant case has a more elegant solution drawing on public key encryption: "Daughter King sends locked box with diamond inside. Son King puts his lock on and sends everything back. Daughter King unlocks his lock and sends it back. Son King gets to see diamond. Similiar protocol followed for return." Arvind also agrees, though, that this answer ultimately fails for the same reason as my original "naive" solution. ]

How it went in the interview

The candidate immediately noticed the analogy to public key encryption and asked, "Can you lock the box without having the key in your hand?" The interviewer said "no." The candidate didn't use the expression "public key encryption"; the interviewer's answer had just eliminated that direction. The interviewer may or may not have known why the candidate had asked the question. [Again, Arvind's remark points out that this response didn't totally eliminate the relevance of the public-key encryption analogy, but I don't think that particularly changes the thrust of this: the interviewer was seeking "right" answers instead of creative exploration of the problem.]

The candidate tried another tack: "I know they can't send physical objects except via the pirate, but can they communicate?" The interviewer said "no."

The candidate, pursuing another intuition, asked about whether there was any way to authenticate a communication carried by the pirate -- that is, to know with certainty who it came from -- and that the answer to that was also "no".

The interviewer was repeatedly telling the candidate that his (the candidate's) intuitions about directions to pursue in solving the problem were wrong. The interviewer never asked the candidate to articulate these intuitions in more detail or to say why the candidate thought this particular information would be useful, and the candidate took the interviewer's answers at face value and simply lopped off the solution paths he (the interviewer) had eliminated and tried to seek a successful solution along the remaining branches.

Things only got further off the rails from there. The interviewer got to watch the candidate rack his brain, making semi-obvious statements like, "OK, you've got to get the diamond in the locked box to the Son King's island and then have the key follow, but I don't see how to do that. I don't see how to get to that state." As time ran out, the candidate was busy trying to work out some way to get one king's key inside the other king's locked box, which (I now believe) is not a productive direction to pursue for a solution.

More piracy

As explained in the sidebar, I was the candidate here. Why did I ask questions about communication after the interviewer eliminated the "public key" approach? At the time, sheer intuition, but in retrospect I believe my intuition was on the mark.

Remember that at the end of this process we were left with "you've got to get the diamond in the locked box to the Son King's island and then have the key follow." You may well ask -- and the interviewer certainly should have asked -- "OK, you say you want to get the diamond in the locked box to the Son King's island. Why don't you just lock the diamond in the box and send it over? The pirate can't steal it while it's locked in the box and he's never seen the key. Then send the key afterwards." And if he had asked, my answer would have been, "But if you have no way to communicate, the pirate is simply going to take the box with the diamond locked in it, pretend to deliver it but actually hold onto it, then when you give him the key he'll sail away with the diamond and the key."/

Hours after the interview, I realized that there is actually a deeper flaw in this brainteaser. Let's make it easy: assume the kings can communicate, or can at least observe physical events on each others island (such as observing the physical passing of the box from the pirate to a king, which would probably be as good as a receipt). Let's even assume that you don't need the key to close the lock. I still believe that this problem is not truly solvable and that the naive solutions proposed above won't actually work.

Anti-Solution >>> (Feel free to peek. It's not a test.)

Some Personal Reflections

This story is about something that really happened to me as a candidate in a job interview, so I have some personal reflections to add.

I'd been interviewed by six different people that day. Each interview had lasted about an hour. No two successive interviews were in the same building, let alone the same room; there was a shuttle ride between each pair of interviews. The interviewers (not all of them actually in the group) seemed to have not merely differing but conflicting concepts of the group's mission and of role of the open position.

Finally, I was speaking to the head of the group in question.

This was in the middle of the dot-com meltdown, and decent openings in the software field were few and far between. Combine this inherently high-stress situation with the fact that I was a candidate with twenty years of successful track record (rather more than the interviewer), and you have a picture-perfect inappropriate situation for an interview brainteaser.

I knew enough about this particular company to be sure that I'd done fine in my earlier interviews that day: if not, they would have just sent me home. I was talking a little about my own experience from being on the other side of the table, hiring people. I happened to mention my dislike of brainteaser questions, making (in brief) some of the same general points I make in this article.

The interviewer said. "Hmm. Well, as it happens, I find brainteasers useful to help me learn about a candidate, so I'm going to pose you one," then posed me the Pirate as Emissary problem above.

Maybe when the interviewer posed me a brainteaser right after I had explained my objections to this type of question, I should have burned my bridges and said, "Thanks but no thanks. I think we don't have a good fit here."

More likely, I should have said, "I am really tired at the end of a full day of interviewing, and if you want to give me a problem like that, first I'm going to need to take five quiet minutes to just chill out before I even start to think about it."

I didn't do either of these things. My bad.

Almost certainly, after he said that you cannot lock the box without having the key in your hand, I should have half-ignored his remark and gone on to say, "...because if you could do that, the problem would be exactly analogous to public key encryption," so he would at least know that I'd already spotted the easy answer to the easy question.

But I didn't say this. Also my bad.

On the other hand, I would hope that if I were the interviewer and a candidate asked about locking without the key or about authenticated communication, I hope I would have had the sense to say, "How would that help you solve this?" I could always route the discussion back to the other (tougher) case later. After all, the idea is supposed to be to find out how the candidate thinks.

But let's face it: technical managers (myself included) are not professional psychological interviewers. Creating an artificial situation to "learn how somebody thinks" calls for a lot of subtlety about controlling that artificial environment, subtlety in an area which is not necessarily our strong suit as technical professionals.

The pattern persisted throughout the interview: he didn't probe for the reasons for my questions and I didn't volunteer them. In retrospect, I should have volunteered my reasoning without being asked, but I was in pure techie mode, not manager mode and not even communicator mode. I was looking for a technical solution. I simply stopped thinking about each branch of the problem that his answers had eliminated.

The interview ended on a relatively sour note. I wasn't offered the job and (all things considered) I'm probably better off for that.

That evening, outside of the pressure of a job interview, I spent several hours trying to work the problem. I'm now quite certain that there is no valid solution to this brainteaser. In retrospect, I'd give odds that I'd seen more deeply into the problem than he had, but it wasn't until hours later that I realized this: during the interview, I was assuming I had a solvable problem on my hands.

Of course, it is possible that it was simply his plan to say "no" to any intuitions I had and see how I would react under the stress of an unsolvable problem and a time constraint (honest answer: not too well at the end of a tough day. Second honest answer: I wouldn't want to work for a boss who would do that on purpose).

I followed up by sending him my more complete analysis of the problem in an email the next day. He never responded, so I can only conjecture about his intentions and his degree of comprehension of the problem. I do know that, regardless of his these, he provided me with what I would consider to be a textbook illustration of counterproductive use of the interview brainteaser.


<<< Prev | Next >>>

1 | 2 | 3 | 4 | 5 | 6 | 7 | 8

Originally written: June 26, 2002
Last modified: December 9, 2002

To Joe Mabel's home page | To Joe Mabel's resume
jmabel@speakeasy.org



All materials copyright © 2002 Joseph L. Mabel
All rights reserved.

"Copyleft": With appropriate notification and appropriate credit, non-commercial reproduction is welcome: contact me if you have any desire to reproduce these materials in whole or in part.