Statically Typed

because Hindley-Milner rocks

Interview Questions, Reversing a Linked List


I found out yesterday that during an interview process, the interviewer gave candidates 20 min. to solve the reversing a linked list problem.  Personally, I can’t believe that it would take people nearly that long assuming there are no cycles present.  On the other hand I think this is a great warm-up interview question.  Here’s a little C++ code:

struct Node{
    Node(Node* _next) : m_NextNode(_next){}

    Node*   m_NextNode;
};

Node* reverseNode(Node* _previous, Node* _node){
    if( _node == NULL ){
        return _previous;
    }

    Node* nextNode = _node->m_NextNode;
    _node->m_NextNode = _previous;

    return reverseNode( _node, nextNode );
}

Node* reverseList(Node *_start){
    return reverseNode( NULL, _start );
}

So what are my extreme conditions?  Here’s a quick run down

  1. I pass in the NULL pointer into reverseList.
  2. My list has only a single Node.
  3. Some smart ass chose 0xDEADBEEF for the end term when not on a Solaris system.

Condition one is caught by wrapping the first call to reverseNode in reverseList with the previous node passed as NULL.  Condition two passes only once through the recursive call before the single Node pointer is returned.  Condition three passes as I don’t allow smart asses near my code.

Next up, reversing an immutable list in Scala.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Information

This entry was posted on May 20, 2010 by in C++, Intervew Questions.
%d bloggers like this: