3 Apr
2006
3 Apr
'06
8:25 a.m.
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.
The two-pointer way actually has practical advantages. "Speed [isn't]
important" isn't quite the same thing in practice as "speed truly
doesn't matter at all". Your way, clever as it is (and actually, I
consider it quite clever, not least because you really did take
advantage of the latitude the questioner carelessly gave you) will not
terminate in even vaguely reasonable time in most real-world cases,
whereas the two-pointer method will.
To draw a rather stretched analogy. this is somewhat like saying that
you can do any in-core sort in O(1) time because you can't store more
than a fixed number of objects: theoretically true but practically
useless.
A friend of mine was once asked something like "You are given an 8x8
array of bits and supposed to return its transpose. How long would it
take you to wtiyr?". The interviewer was surprised to hear "Probably
about 15 minutes". Thing is, the solution this person was thinking of
was something along the lines of (to use C-ish syntax)
64-bit-int transpose(64-bit-int v)
{
v = (v & 0xf0f0f0f00f0f0f0f0f) |
((v & 0x0f0f0f0f00000000) >> 28) |
((v & 0x00000000f0f0f0f0) << 28);
v = (v & 0xcccc3333cccc3333) |
((v & 0x3333000033330000) >> 12) |
((v & 0x0000cccc0000cccc) << 12);
return( (v & 0xaa55aa55aa55aa55) |
((v & 0x5500550055005500) >> 7) |
((v & 0x00aa00aa00aa00aa) << 7) );
}
which I think is a clever adaptation of a standard blitting trick.
(Perhaps fortunately, the interviewer was not following a script, and
asked enough followup questions to determine that.)
/~\ The ASCII der Mouse
\ / Ribbon Campaign
X Against HTML mouse at rodents.montreal.qc.ca
/ \ Email! 7D C8 61 52 5D E7 2D 39 4E F1 31 3E E8 B3 27 4B