|
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.
|