The lost art (Was: The VAX is running

Jim Battle frustum at pacbell.net
Mon Apr 6 17:37:08 CDT 2009


John Floren wrote:
> On Mon, Apr 6, 2009 at 5:25 PM, Chris Kennedy <chris at mainecoon.com> wrote:
>> Ian King wrote:
>>
>>> I used to ask college grads to write a function in C to convert a
>>> null-terminated string representing an octal number into an int.
>> Mine has always been to postulate a singly-linked list with each node
>> containing a string value, then ask them to write something to print out
>> the list in reverse order.  There's a bunch of obvious ways to solve
>> that problem; the nice thing about it is that depending on the answer
>> that they give you can apply more constraints (copying isn't allowed,
>> memory is constrained, optimize for speed, whatever) in order to better
>> estimate their approach to solving problems.
>>
> 
> I hope the answer is recursion. The answer should ALWAYS be recursion,
> right Professor McCarthy? :)

Recursion will eat up a lot of memory if the list is long.

If memory is tight and nobody else is using the list, flip the pointer 
direction as you go down the list.  When you hit the end, print it out, 
follow the pointers back to the beginning, flipping them back again.

Or perhaps the singly linked list already stores the XOR of the forward 
and back pointers and so no flipping is necessary.



More information about the cctalk mailing list