list flatten

// listflatten.cpp
//
#include <cctype>
#include <cassert>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <utility>
using namespace std;

const char lparen = '(';
const char rparen = ')';

struct node {
    bool atomp;
    int  val;
    struct node *sub;
    struct node *next;
};

struct node *
parse(char *str)
{
    if (!*str) return NULL;
    char *p = str;
    while(isspace(*p))
    {
        p++;
    }
    assert(*p == lparen);
    char *q;
    int lcnt = 1;
    for(q=p+1; ; q++)
    {
        if (*q == rparen)
            lcnt--;
        else if (*q == lparen)
            lcnt++;

        if (lcnt == 0)
            break;
    }
    assert(*q == rparen);
    *q = '\0';

    struct node *newnode = (struct node*)malloc(sizeof(struct node));
    for(p++; isspace(*p); p++)
        ;
    int val = 0;
    bool atomp = false;
    if (isdigit(*p))
    {
        atomp = true;
        while(isdigit(*p))
        {
            val = val * 10 + *p-'0';
            p++;
        }
    }
    newnode->atomp = atomp;
    newnode->val   = val;
    newnode->sub   = parse(p);
    newnode->next  = parse(q+1);

    return newnode;
}

typedef pair<struct node*, struct node*> pnn;

pnn flatten(struct node *head)
{
    pnn ret; ret.first=ret.second=NULL;
    if (!head) return ret;

    pnn subpair  = flatten(head->sub);
    pnn nextpair = flatten(head->next);
    head->sub=head->next=NULL;

    struct node dummy;
    struct node *subhead = subpair.first;
    struct node *subtail = subpair.second;
    struct node *nexthead = nextpair.first;
    struct node *nexttail = nextpair.second;
    struct node *tail = &dummy;

    // set up new head
    if (head->atomp) { tail->next=head; tail = tail->next; }
    if (subhead) { tail->next = subhead; tail = subtail; }
    if (nexthead) { tail->next = nexthead; tail = nexttail; }

    if (tail==&dummy) { ret.first=ret.second=NULL; }
    else { ret.first=dummy.next; ret.second=tail; }
    return ret;
}

void print(struct node *head)
{
    if (!head) return;
    cout << "( ";
    if (head->atomp)
        cout << head->val << " ";
    print(head->sub);
    cout << ") ";
    print(head->next);
}


int main()
{
    char list[] = "(1 (21 (339) ()))(410)(()(123))";
    //char list[] = "(1(3 ()))(2)";
    //char list[] = "(())";

    struct node *head = parse(list);
    print(head);
    cout << endl;
    cout << "flatten list\n";
    head = flatten(head).first;
    print(head);
    cout << endl;
}

swap odd even position in linked list

#include <cassert>
#include <cstdio>
using namespace std;

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

node* swap(node *head)
{
    node dummy;
    node *prev, *curr, *u, *tmp;
    if (head==NULL) return head;

    prev=&dummy;
    for(curr=head; curr!=NULL && curr->next!=NULL; ) {
        u = curr->next;
        tmp = u->next;
        prev->next = u;
        u->next = curr;
        prev = curr;
        curr = tmp;
    }
    prev->next = curr;
    return dummy.next;
}

void print(const node *head)
{
    for(const node *p=head; p; p=p->next)
        printf("%d ", p->val);
    putchar('\n');
}
int main()
{
    const int N=101;
    node v[N];
    
    for(int i=0; i<N; ++i) {
        v[i].val=10*i;
        if (i<N-1) v[i].next=&v[i+1];
        else v[i].next=0;
    }

    node *head=&v[0];
    puts("input");
    print(head);

    head = swap(head);
    puts("swap even odd");
    print(head);

}

sorting linked list

// =========================================================
// 
//       Filename:  listsort.cpp
// 
//    Description:  
// 
//        Version:  1.0
//        Created:  03/09/2012 04:06:26 PM
//       Revision:  none
//       Compiler:  g++
// 
//         Author:  LI YAN (lyan), lyan@cs.ucr.edu
//        Company:  U of California Riverside
//      Copyright:  Copyright (c) 03/09/2012, LI YAN
// 
// =========================================================
//
// notes:
// 1. insert into head does not need dummy node
// 2. insert into tail needs a dummy node to make code simple, there is no tail
// node in an empty list anyway
// 3. delete from head does not need dummy node
// 4. maintain a tail pointer if you need to insert at tail
// 5. it often helps use two pointers walking the same list
// 6. be careful in off-by-one
// 7. know the primitives, insert/delete at ptr->next and at head or tail
// 8. check NULL before dereference use -> or *p

#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <utility>
using namespace std;

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

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

    node ahead, bhead; // dummy ahead is not necessary since we only delete from head
    node *p1, *p2, *u;
    ahead.next=head; bhead.next=NULL;

    for(p1=&ahead; p1->next!=NULL; ) {
        u = p1->next; p1->next = p1->next->next;
        for(p2=&bhead; p2->next!=NULL; p2=p2->next) {
            if (u->val > p2->next->val) break;
        }
        u->next = p2->next;
        p2->next = u;
    }
    return bhead.next;
}

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

    node dummy; dummy.next=head; // use dummy head to simplify delete from head
    node *curr, *ptr, *u, *newhead=NULL;
    int vmax;
    while(dummy.next->next != NULL) { // keep going as long as list has >=2 items
        curr=ptr=&dummy; u=ptr->next; vmax = u->val;
        for(ptr=ptr->next; ptr->next!=NULL; ptr=ptr->next) {
            u=ptr->next;
            if (u->val > vmax) { curr = ptr; vmax = u->val; }
        } 
        ptr=curr->next;
        curr->next = curr->next->next;
        ptr->next=newhead;
        newhead=ptr;
    }
    dummy.next->next = newhead;
    return dummy.next;
}

// code from this point on inspired or learned from Robert Sedgewick
node* mergesort(node *head)
{
    node dummy;
    node *left, *right, *ptr, *p1, *p2;

    if (head==NULL || head->next == NULL) return head;
    for(p1=head, p2=head->next; p2!=NULL && p2->next!=NULL; p1=p1->next, p2=p2->next->next) ;
    left=head; right=p1->next; p1->next=NULL;

    //printf("p1 %d p2 %d\n", left.next->val, right.next->val);

    p1=mergesort(left);
    p2=mergesort(right);

    dummy.next=NULL;
    for(ptr=&dummy; p1!=NULL && p2!=NULL; ) {
        if (p1->val <= p2->val) { ptr->next=p1; ptr=p1; p1=p1->next; }
        else { ptr->next=p2; ptr=p2; p2=p2->next; }
    }
    ptr->next = (p1==NULL) ? p2 : p1; // this appends remain of p1 or p2 in one stmt
    return dummy.next;
}

// quick sort with Lumoto partition
// returns (head, tail) of sorted list
pair<node*, node*>
quicksort(node *head)
{
    node dummy;
    node *low, *high;
    node *pivot, *ptr, *u, *newhead, *newtail;
    int n, k, i;

    if (head==NULL || head->next==NULL) return make_pair(head, head);

    for(n=0, ptr=head; ptr!=NULL; ptr=ptr->next, n++) ;

    k=rand()%n;
    dummy.next=head;
    for(i=0, ptr=&dummy; i<k; ++i, ptr=ptr->next) ;
    pivot=ptr->next; assert(pivot);
    ptr->next=ptr->next->next;

    low=high=NULL;
    for(ptr=&dummy; ptr->next != NULL; ) {
        u=ptr->next; ptr->next = u->next;
        if (u->val <= pivot->val) { u->next = low; low=u; }
        else { u->next = high; high=u; }
    }
    //printf("low %d high %d\n", low.next->val, high.next->val);
    pair<node*, node*> pp1, pp2;
    pp1 = quicksort(low);
    pp2 = quicksort(high);

    if (pp1.first != NULL) newhead = pp1.first;
    else newhead = pivot;

    if (pp2.second != NULL) newtail = pp2.second;
    else newtail = pivot;

    if (pp1.second != NULL) pp1.second->next = pivot;
    pivot->next = pp2.first;

    return make_pair(newhead, newtail);
}

void print(const node *head)
{
    const node *p;
    for(p=head; p; p=p->next)
        printf("%d ", p->val);
    putchar('\n');
}

int main()
{
    srand((unsigned)time(NULL));
    int a[] = {10, 3, 4, 5, 1, 9, 8};

    int n=sizeof(a)/sizeof(int);
    node v0[10], v1[10], v2[10], v3[10];
    node *head;
    for(int i=0; i<n; ++i) {
        v0[i].val = v1[i].val = v2[i].val = v3[i].val = a[i];
        if (i<n-1) { v0[i].next = &v0[i+1]; v1[i].next = &v1[i+1]; v2[i].next = &v2[i+1]; v3[i].next = &v3[i+1]; }
        else { v0[i].next = v1[i].next = v2[i].next = v3[i].next = 0; }
    }

    puts("v0[]"); print(v0);
    puts("insertion sort:");
    head=selectsort(v0);
    print(head);
    putchar('\n');

    puts("v1[]"); print(v1);
    puts("selection sort:");
    head=selectsort(v1);
    print(head);
    putchar('\n');

    puts("v2[]"); print(v2);
    puts("merge sort:");
    head=mergesort(v2);
    print(head);
    putchar('\n');

    puts("v3[]"); print(v3);
    puts("quick sort:");
    head=(quicksort(v3)).first;
    print(head);
    putchar('\n');
}

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)
{
}

emacs undo redo and cursor movement

So you know that C-x u or C-_ will undo most recent change, but how to redo?
emacs keeps track of previous changes and as soon as there is a command other than undo, maybe C-f, then it thinks all previous changes are undoable.

So to redo, just type C-f or any command to interrupt the undo sequence, then the next undo will be redo.

Also for cursor movement, C-Space or C-@ will mark the current location, then C-u C-Space or C-u C-@ will return to this location. Esc-< back to top of buffer, and Ese-> to bottom of buffer.

C-x 2 gives two horizontally aligned windows and C-x 3 gives two vertically aligned windows.

Saving a position records a spot in a buffer so that you can move
back there later. Moving to a saved position reselects that buffer and
moves point to that spot.

`C-x r SPC R'
Save position of point in register R (`point-to-register').

`C-x r j R'
Jump to the position saved in register R (`jump-to-register').

To save the current position of point in a register, choose a name R
and type `C-x r SPC R'. The register R retains the position thus saved
until you store something else in that register.

The command `C-x r j R' moves point to the position recorded in
register R. The register is not affected; it continues to record the
same position. You can jump to the same position using the same
register any number of times.

SRM 536

div2 p1000
simple DP, recursion with memorization, dp[pos] is max score end at pos.
need to sort score from low to high.
caveat: score can be negative so need to use bool memo[60] to remember whether dp[pos] has been computed already. otherwise an easy 1000 problem.

my proof of Wilson's theorem

The Wilson's theorem says that (n-1)! + 1 is divisible by n iff n is prime.

The only if direction is easy. If (n-1)! = -1, then (n-2)! = 1 mod n, so each of 1,2,...,n-2 are relatively prime to n. Clearly n-1 is relatively prime to n,  then 1,2,...,n-1 are all relatively prime to n, but this can only happen if n is a prime.
The if direction is harder.


When n is prime, let 1 < a < n, then a, a^2, ..., a^n-1 will hit 1, 2, ..., n-1, so

a * a^2 * ... ^ a^(n-1) = (n-1)! all arithmetic under mod n

then a^(n(n-1)/2) = (n-1)!

From Fermat's little theorem we have a^(n-1)=1
so ((n-1)!)^2 = a^n(n-1) = 1

Because n is prime, then (n-1)! can have only trivial roots, which are +1 and -1.

If (n-1)! = -1 we are done, so we now argue that (n-1)! not equal to 1.

Suppose for contradiction that (n-1)! = 1 for some prime n.
then n-1 + (n-1)! = 0
(n-1) (1 + (n-2)!) = 0
since n-1 neq 0
we have 1+(n-2)! = 0
therefore (n-2)!=-1
so (n-1)=1 // this is false. no idea how to fix it.
but this can only be true when n=2. QED.