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.
