A better solution to a programming book's linked list problem

As astute readers of my blog know, I left my job at Sun last month. After taking some well-deserved time off, I have been looking for something new.
Despite 14 years professional experience, 20 years coding experience, and a lengthy résumé, I was stumped by some coding puzzles at a couple of large companies.
So, last monday, I picked up a book at Barnes & Noble titled "Programming Interviews Exposed, 2nd edition", to help get past the torture tests I have to endure in this tight job market. I have been reading it as a leisurely pace, trying to find the problems first on my own, before checking the solution.

I am writing this article and reprinting the problem with the author's permission.

On page 31, the author defines a typical linked-list structure :

typedef struct Element {
    struct Element *next;
    void *data;
} Element;

After some fairly basic coding discussion of linked lists, a slightly more complicated problem appears on page 35.

head and tail are global pointers to the first and last element, respectively, of a singly-linked list of integers. Implement a C function for the following prototype :

bool remove(Element *elem);
The argument to remove is the element to be deleted.


The authors spend much of pages 36-38 discussing that the problem is mostly about
"special cases", in particular when deleting elements at the beginning or the end of the list.

The author's final solution reads as follows :

bool remove(Element* elem) { 
    Element* curPos = &head;

    if (!elem)
        return false;

    if (elem == head) {
        head = elem->next;
            delete elem;
        /* special case for 1 element list */
        if (!head)
            tail = NULL;
        return true;
    }
    while (curPos)  {
        if (curPos->next == elem) {
            curPos->next = elem->next;
            delete elem;
            if (curPos->next == NULL)
                tail = curPos;
            return true;
        }
        curPos = curPos->next;
    }
    return false;
}

While my first inclination was to also have a special case, I quickly stroke that part out on paper. I think the code really does not have to be so long if you use a double pointer to refer to the
head. This eliminates the first special case for updating the head pointer when removing the first element. And therefore, there is no longer a need to update the tail pointer in two different places, which further reduces code size.

bool remove(Element* elem) {
    Element** curPos = &head;

    if (!elem)
        return false;

    while (*curPos) {
        if (elem == *curPos) {
            *curPos = elem->next;
            if (elem == tail)
                tail = elem->next;
            delete(elem);
            return true;
        }
        curPos = &((*curPos)->next);
    }
    return false;
}

The only thing I changed from my piece of paper was the name of the temporary variable, and the formatting, to match that of the book's authors.

Better not get sick at Netflix !

This post is more than 2 years overdue, but I felt that my story needed to be heard, especially by past, current and prospective Netflix employees, as well as management.

In the summer of 2006, I was looking for a new position and ended up interviewing and landing what I thought was a great opportunity at Netflix working on security in the Electronic Delivery Systems group, and with a hefty paycheck. My first day was October 31, 2006.

Unfortunately, on November 1, my second day there, I got very bad news from my physician : my HIV test, performed the week before, had turned positive. This was of course devastating news. I became severely depressed, and was not able to make it to work on my third or fourth day. I missed plenty more work time. My boyfriend also turned out HIV positive 2 weeks after I did. I will be the first to admit that I was completely ineffective at my job for the next 2 months. Learning both about this new major disease and a new very challenging job at the same time simply was more than I could chew.

Finally, in January of 2007, I went on short-term disability for the depression and ended up in IOP at Kaiser. I was covered under Netflix's generous disability policies. After 1 month, I had still not been released back to work, and received a letter with an ultimatum to return to work by mid-february, 6 weeks after the start of my disability, or be terminated.

Unfortunately, I was ineligible for an FMLA, a Family Medical Leave of Absence, which would have allowed me to take 3 months medical leave, because I was a recent hire, and the law only covers those with at least 1 year of service.

One week before the ultimatum, I pleaded my case with Netflix HR, explaining the reason for my absenteism and disability. This did not make any difference. I was told that it was standard company policy for this situation - to terminate the new employee who had an extended illness ! The date passed, and I was terminated while still on disability. That was the first and only time I had ever been involuntarily terminated. No severance of any kind was offered. I was now both HIV positive, and jobless.

I was released by my doctor to work again about a month after my termination, and returned to my previous employer, Sun Microsystems, another month later, working 60% (3 days a week) for the remainder of 2007, and then back to full time in 2008.

As I write this post, I am enjoying some much-needed time off, having left Sun out of disinterest in September in the wake of the acquisition of Sun by Oracle, and seeking another opportunity. Few Silicon Valley companies are hiring at this time. But I noticed that Netflix was, and my old position still had not been filled. I inquired with my former manager at Netflix, who was aware of the details of the situation. I was told that per Netflix company policy, there are no second chances there - once you are fired from Netflix, you can never apply there again.

The moral of the story is this : make sure you don't get seriously sick if you want to work for Netflix, especially in your first year.