my facebook interview experience

So far I have failed 3 facebook phone interviews in the past 3 years, fairly consistent, huh. It seems I am now in a position that any time I was interviewing with facebook, my nerves will be so tense that I could not think or write code as I would have done otherwise, and collabedit, which is an excellent online tool, makes me feel bad as well.

The most recent one is particularly frustrating and the problem is simple, write a function to sort a linked list. OK, so what do you do? I didn't prepare this one, I have to admit, but chances are very small that you have prepared some problem and it did get asked, plus it amounts to cheating, although I do recommend to prepare as many interview problems as you can find. I am not particularly good at linked list manipulation and recursion, which are fundamentals.

So my first idea is to do selection sort, and I even had a neat idea to repeatedly get the max element and then you can insert into the front which is way easier than insert to the tail. The interviewer said OK when I asked whether he wants a more efficient way, which I am not sure at that moment, although I did mention heap and binary search tree. I know merge sort and quick sort, and shell sort, but didn't quite think they are applicable to linked list.

So I started coding, almost immediately I am a bit lost. Seems the list is changing and the loop condition is not as simple as for i=0 to N-1, and I need to keep track of one node ahead of the node I want to delete. I had something barely works and the interviewer asked why I have some repeated code. I told him that I need them to keep track of pred of curr node that was about to delete. Then everything is practically over. And the thank you letter is just a matter of time, although I did realize that merge sort is doable and told me so. He asked about quick sort, but Hoare's partition cannot be implemented on a linked list, Lumoto's will, but has a penalty into O(n^2) when the list has a lot of duplicates, plus it is a bit tricky to get any quick sort implemented correctly. If that was facebook wanted, then their engineers have to be superb.

When offline, selection sort seems not that hard and I have most correct ideas, although to get it right take some effort.

struct node {
int val;
node *next;
};

node* selection_sort(node *head)
{
if (head==NULL || head->next==NULL) return head;

while(head->next) // loop as long as list has 2 or more elements
{
int maxval=head->val;
node *prev=NULL, *curr, *newhead=NULL;
for(node *p=head; p->next!=NULL; p=p->next)
{
curr=p->next;
if (curr->val > maxval) { maxval=curr->val; prev=p; }
}
if (prev==NULL) { // remove head from list
head=head->next;
}
else {
prev->next = prev->next->next;
}
// insert curr into sorted list
curr->next=newhead;
newhead=curr;
}
head->next = newhead; // deal with last element in list
return head;
}

node* merge_sort(node *&head)
{
if (head==NULL || head->next==NULL) return head;
int n, i;
node *p, *left, *right, *tail=NULL;
for(n=0, p=head; p!=NULL; n++, p=p->next) ; // count number of nodes
for(p=head,i=0; i+1next) ; // find split point, which is p->next
left=head; right=p->next; p->next=NULL;

merge_sort(left);
merge_sort(right);
// merge
while(left!=NULL && right!=NULL)
{
if (left->val <= right->val) { p=left; left=left->next; }
else { p=right; right=right->next; }
// insert into tail
if (tail==NULL) { head=tail=p; }
else { tail->next=p; tail=p; }
}
while(left!=NULL) {
if (tail==NULL) { head=tail=left; }
else { tail->next=left; tail=left; }
left=left->next;
}
while(right!=NULL) {
if (tail==NULL) { head=tail=right; }
else { tail->next=right; tail=right; }
}
tail->next=NULL;
}

you can try to write quick sort with Lumoto partition here.

Second most recent one is write a function to flatten the list.

struct node {
bool is_atom;
int val;
node *child;
node *next;
};

node* flatten(node* &head)
{
}