der Mouse wrote:
I was once
asked the following trick question. Say you have a singly
linked list. This list might be a simple chain, or it might loop on
itself. For reasons that can't be explained, you are allowed to use
only two memory locations to decide if the list loops or not. After
a couple questions to clarify, it was allowed that speed wasn't
important and that the size of an integer and a pointer were the
same. A 0 pointer marks the end of the list.
I quickly answered with a dumb, brute force
solution: one location is
a pointer, one is a counter. [...if couter overflows it loops...]
The clever answer is to have two pointers. At
each step of the
algorithm, one pointer advances two steps and the other pointer
advances three steps (any relatively prime pair of increments would
work).
1 and 2 is actually the canonical pair of advancement steps.
OK, this just confirms this is a "well known" trick question. If
someone was to ask me this question again in an interview and I answered
it in four seconds, does it mean I'm any smarter than I was a few years
ago when I first heard it?
As an example of a good question (and one that is on-topic for this
list), I was asked this during an interview in 1986. The interviewer
was Carl Alsing, whom you might recognize as the manager of the
microkids in the book, The Soul of a New Machine. He asked if I had a
bunch of Apple II programs and wanted to continue to use them but my
Apple II had died and all I had available was an IBM PC, what could I do
about it. After answering, "write an emulator," he probed with
questions about how long I thought it would take to write, what parts if
it I thought would be the hardest, how would I validate it, what speed I
could expect to achieve, etc. That type of interview requires that the
interviewer be an active participant that has to think on his/her feet
as well, and recognizes that in the real world there are often multiple
approaches to the solution having varying tradeoffs. The black and
white world of clever interview questions is typically irrelevant.
As an aside, I did take that job and had a cube directly across from
Carl's office. I had read The Soul of a New Machine a few years before
but the details were hazy, and anyway, I didn't know for a few months
that Carl was in the book until a coworker told me. I then went back
and read the book again. The section where the author summarizes Carl's
appearance and the impression he first makes was just startling -- in a
paragraph the author really did capture truths that I hadn't realized
fully myself (such as giving the impression of being a lot less tall
than he is). Being the only point of reference that I could verify, and
finding it so dead right, it made me much more inclined to believe the
rest of the book was accurate.