Thursday, May 24, 2012

Reverse

Three tiny puzzles:
  1. Given the following interface:

    interface
     INode
    {
             INode Next { getset; }
             object Data { get; }
    }

    and a reference to root 
    INode root reverse a one-linked list. Do not use any additional collections, as arrays, lists or stacks.
    
    
  2. The same for this interface:

    interface INode
    {
             INode Next { get}
             object Data { getset; }
    }

  3. And the same for this:

    interface
     INode
    {
             INode Next { get}
             object Data { get; }
    }
First and second tasks are almost the same, the 3rd solution will be good for 1st and 2nd as well.

6 comments:

  1. Are there any complexity constraints?

    ReplyDelete
    Replies
    1. Ideally, O(1) :). But O(N) will be cool too. For memory, I'm not sure, whether all puzzles could be solved within O(1).

      Delete
  2. Should resulting linked list be also in canoncal form, i.e. the head item? If so, can one introduce an alternative implementation to #3? Otherwise, how can immutable interface be reversed?

    In other words, can helper INode objects (not collections!) be used to solve #3? Should the resulting list contain exactly the same INode instances or just Data order needs to be reversed?

    ReplyDelete
    Replies
    1. > Should resulting linked list be also in canoncal form, i.e. the head item?
      Yes.
      > If so, can one introduce an alternative implementation to #3? Otherwise, how can immutable interface be reversed? In other words, can helper INode objects (not collections!) be used to solve #3? Should the resulting list contain exactly the same INode instances or just Data order needs to be reversed?
      You need to satisfy the INode contract only.

      Delete
    2. Simple recursive solution:
      http://pastebin.com/yYPy5yVk

      Delete