Programming

Reading this post at RethinkDB I decided to take my chances at solving the problem they present to the candidates to work with them, which is:

Write a C function that reverses a singly-linked list.

Took me six minutes to solve it, plus circa 10 minutes to write the test, for a total of 16 minutes. It was not the best in class.

So I took more time to come up with another solution. It took me 30 minutes to solve it the best fashion I could.

Both solutions are shown below.

Solution #1

The first solution is based on recursion. Let’s see:

struct node *reverse_list(struct node *current, struct node *last) {
    struct node *next = current->next;
    current->next = last;
    if (next != NULL) {
        return reverse_list(next, current);
    } else {
        return current;
    }
}

Recursion is a beautiful thing. It lets you solve some tricky problems with a very simple code, no visible clutter in the code. Most of us would find it an elegant solution. And this is, for a duct tape solution, for a prototype.

Although elegant, recursion can easily blow your stack away. That’s because recursion uses the process stack a lot, to allocate stack frames. So, for some serious business this code is suboptimal. A few dozens of entries in this list, and the program would crash and burn.

What separates good programmers from the ones that excel at the craft (so I’ve been said) is the itch to fix their own code. And man, that was itching. So I spent some more time thinking and came up with a better idea, one that doesn’t use recursion.

Solution #2

The second solution is as follows.

struct node *reverse_list2(struct node *top) {
    struct node *next, *last = top, *first = top;
    while (top->next != NULL) {
        next = top->next;
        top->next = last;
        last = top;
        top = next;
    }
    top->next = last;
    first->next = NULL;
    return top;
}

So, 19 out of 20 miss this solution. I’ve actually have seen some pretty bad candidates in the industry, that make their resumes to appeal to the managers. “XML, CSS, Javascript, Java, C#” and, well, no real knowledge of the basics.

And this seems to be even worse. Some guys get really close and miss at the last point. Don’t get it? The guy attributed the right answer in a variable that will be destroyed at the block’s end. Which is the next line. Failed.

My take on this: being a master of the craft of programming pays off. Hard work pays off. Those who are reading should at least spend more time learning to do the real work instead of trying to fill their resumes with buzzwords.

My full answer is here. Thank you for you time and patience.

Extra bonus: I you came here looking for an answer to the riddle (which you shouldn’t), you can take the answer to the FizzBuzz for free.