Job Interview question: "Reverse a Linked-list. Write code in C."

[mbrubeck]

How does one manage to publish code that is so badly botched? [Update: The code in the blog post is fixed; the original versions are below.]

The recursive solution does not work. It never sets “next” to NULL for the original head of the list, so now the list ends with a cycle.

The non-recursive solution does not work either. It never assigns anything to “previous”, so it always returns NULL and sets all of the “next” pointers to NULL.

This is easy to see if you actually compile and run both of these on some sample input:

    #include <stdio.h>
    
    typedef struct Node {
        struct Node *next;
        int value;
    } Node;
    
    Node * reverse( Node * ptr )
    {
        Node * temp;
        if(ptr->next == NULL) {
            return ptr;
        } else {
            temp = reverse(ptr->next);
            ptr->next->next = ptr;
            return temp;
        }
    }
    
    Node * ireverse( Node * ptr )
    {
        Node * temp;
        Node * previous = NULL;
        while(ptr != NULL) {
            temp = ptr->next;
            ptr->next = previous;
            ptr = temp;
        }
        return previous;
    }
    
    void print(Node *head) {
        Node *curr;
        for (curr = head; curr != NULL; curr = curr->next) {
            printf("%d\n", curr->value);
        }
    }
    
    main() {
        Node a, b, c;
        a.value = 1;
        a.next = &b;
        b.value = 2;
        b.next = &c;
        c.value = 3;
        c.next = NULL;
        printf("Iterative:\n")
        print(ireverse(&a));
    
        a.value = 1;
        a.next = &b;
        b.value = 2;
        b.next = &c;
        c.value = 3;
        c.next = NULL;
        printf("Recursive:\n")
        print(reverse(&a));
    }

[Monkeyget]

Your comment reminds me of the experience Leslie Lamport performed : checking the ten first quick sort algorithms found with a search engine and how half of them were wrong.

[mjterave]

> How does one manage to publish code that is so badly botched?

It's just a blog. There's effectively no barrier to entry. :)

[tybris]

That's why we have peer review (you).

[jordyhoyt]

How to reverse a linked list in C is not hacker _news_.

Additionally, sites like these are a disease. At work, I overheard a phone screen in which the interviewer asked the question, "you have a collection of numbers, all of which appear twice, except one number which appears a single time. How do you find the number?" The person being interviewed gave the "clever" answer (xor all numbers together, result is your answer) within seconds. The interviewer said, "that's nice, but not what I'm going for. What if it's a collection of strings?" She couldn't do it.

[awa]

Agreed with the sentiment. The worse part is the post has 5 points which is more than some of the good posts/articles out there.

Also, to give some leeway to the OP he might have been trying to point out the fact that the code had errors (which was later corrected) and showing why blindly taking advice from random blogs might be harmful for your career. In that case I would have appreciated if he had left a comment.

[eru]

I agree.

(Sorry, couldn't resist:) You can extend the clever answer to XORing the strings, if you extend the XOR-operation to strings. But I probably would not use that in production code.

[z_]

Who couldn't do it? The Interviewer or the Interviewed?

[roschdal]

I actually once got this question in an interview for a big search company: "Reverse a linked list, in place".

I scetched a solution on the whiteboard, drawing nodes and pointer arrows. I didn't manage to write code to solve the problem, unfortunately, and I didn't get the job...

I consider myself a pretty decent programmer, but I know that I'm not very good at discovering solutions to tough new problems "on the spot".

What does such a interview question really reveal about my abilities? I know that I could have solved the problem in about 10 minutes given a Python interpreter, but given the turmoil of an interview, I didn't.

[gte910h]

Do people with blogs not have compilers?