Random Selection

Today when I coded ads recommendation for my db project, it reminds me some classical problems about random selection.

Q1. How to randomly select an element from a linked list whose size is unknown.

Node *ret = NULL;
int cnt = 0;

for (Node *p = head; p != NULL; p = p->next){
    if (rand() % ++cnt == 0)
        ret = p;
}

Q2. How to randomly select K elements from a huge linked list whose size is unknown.

Since the linked list is huge, we can assign a random number in [0, 1] to each element as its weight, then we can pick first K maximum-weighted elements.

Another solutions is to select the ith element with probability 1/i. We can prove that each element is selected with probability 1/N.