Re: Fun linked list problem




Steve O'Hara-Smith wrote:
On 29 Apr 2006 17:35:36 -0700
"Gene" <gene.ressler@xxxxxxxxx> wrote:

Murali wrote:
Given a singly linked list (implemented using pointers) implement a
Data Structure which allows you to traverse the list in either
direction. More specifically given any sequence of {next,prev}, you
should be able to print the corresponding elements of the list.

You just reverse the links as you go forward and restore them as you go
backward. So you need only constant space overall and O(1) time per
node traversed.

Plus O(N) on the total distance into the list at the end for
backing out and restoring the original pointers. If there's going to
be a lot of traversing and you need the list usable from the start
afterwards double linking (with the xor trick if space is that important)
would seem to be a win.


Absolutely right.

As you imply, these cute solutions to problems are fun as puzzles, but
real programming projects seldom benefit from this kind of thinking.
They're too "fragile" in that they add all kinds of necessary
conditions to the system.

Having never interviewed for a programming job, I find it surprising
that anyone would rely on questions like this to assess ability (as the
OP observes). I guess at the entry level they might reflect
cleverness. But in the long run, you'd want to _discourage_ such
trickiness because it would almost always make a program more
expensive overall.

On the other hand, such a mindset is perfectly consistent with the
kinds of problems you see in MS and other run-of-the-mill software. So
maybe I shouldn't be surprised...

.