Probabilities and Reservoir Sampling

Sample size 1

From Wikipedia

Keep the first item in memory. When the i-th item arrives (for i>1):

  1. with probability 1/i, keep the new item instead of the current item; or equivalently
  2. with probability 1 - 1/i, keep the current item and discard the new item.

Resulting probability: P(i) = 1 * (1 - 1/2) * (1 - 1/3) * ... * (1 - 1/n) = 1/n P(i): the probability of select the i-th item;

Sample size k

Put first k in result array. When i-th item arrives (for i > k):

  1. with probability k/i, replace the result with new value.
  2. with probability 1 - 1/i, keep the current item and discard the new item.

Resulting probability: P(i) = 1 * (1 - 1/(k+1)) * ... * (1 - 1/n) = k/n

Shuffle

for i from n−1 downto 1 do
     j ← random integer such that 0 ≤ j ≤ i
     exchange a[j] and a[i]

382. Linked List Random Node

Given a singly linked list, return a random node's value from the linked list. Each node must have the same probability of being chosen.

Follow up: What if the linked list is extremely large and its length is unknown to you? Could you solve this efficiently without using extra space?

Example:

// Init a singly linked list [1,2,3].
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
Solution solution = new Solution(head);

// getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.
solution.getRandom();

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    /** @param head The linked list's head.
        Note that the head is guaranteed to be not null, so it contains at least one node. */
    Solution(ListNode* head_) : head(head_) {
    }

    /** Returns a random node's value. */
    int getRandom() {
        if (!head) return -1;
        int res = head->val;
        auto node = head->next;
        int i = 2;
        while (node) {
            int j = rand()%i;
            if (j == 0) {
                res = node->val;
            }
            ++i;
            node = node->next;
        }
        return res;
    }
private:
    ListNode* head;
};

384. Shuffle an Array

Shuffle a set of numbers without duplicates.

Example:

// Init an array with set 1, 2, and 3.
int[] nums = {1,2,3};
Solution solution = new Solution(nums);

// Shuffle the array [1,2,3] and return its result. Any permutation of [1,2,3] must equally likely to be returned.
solution.shuffle();

// Resets the array back to its original configuration [1,2,3].
solution.reset();

// Returns the random shuffling of array [1,2,3].
solution.shuffle();

class Solution {
public:
    Solution(vector<int> nums) : data(nums) {
        srand(time(NULL));
    }

    /** Resets the array to its original configuration and return it. */
    vector<int> reset() {
        return data;
    }

    /** Returns a random shuffling of the array. */
    vector<int> shuffle() {
        auto res = data;
        int len = res.size();
        for (int i = len - 1; i >= 0; --i) {
            int j = rand() % (i+1);
            swap(res[i], res[j]);
        }
        return res;
    }
private:
    vector<int> data;
};

398. Random Pick Index

Given an array of integers with possible duplicates, randomly output the index of a given target number. You can assume that the given target number must exist in the array.

Note: The array size can be very large. Solution that uses too much extra space will not pass the judge.

Example:

int[] nums = new int[] {1,2,3,3,3};
Solution solution = new Solution(nums);

// pick(3) should return either index 2, 3, or 4 randomly. Each index should have equal probability of returning.
solution.pick(3);

// pick(1) should return 0. Since in the array only nums[0] is equal to 1.
solution.pick(1);

class Solution {
public:
    Solution(vector<int> nums) : data(nums) {
    }

    int pick(int target) {
        int count = 0, res = -1;
        for (int i = 0; i < data.size(); ++i) {
            if (data[i] != target) continue;
            if (count++ == 0) res = i;
            else if ((rand()%count) == 0) res = i;
        }
        return res;
    }
private:
    vector<int> data;
};

Random return maximum value

Given an array of integers. We have to find the max element of the array, which is at multiple places in the array and return any one of the indices randomly.

From CP

to complete this solution ,
start with 3 variable
1) currentMaxNum = current max number
2) currentMaxCount = how many instances of current max we have seen

every time we update currentMaxNum we update the currentMaxCount to 0.
initialize {currentMaxNum , CurrentMaxCount} ={a[0],1}
foreach a[i]
if (a[i] < currentMaxNum) -- continue;
else if ( a[i] > currentMaxNum)
{
currentMaxNum = a[i]; currentMaxCount = 0;
}
else
{
// a[i] == currentMaxNum
currentMaxCount ++;
replace currentMaxNum with a[i] with probability 1 / currentMaxCount;
}

This algorithm guarantees that currentMaxNum will be max number at the end.
now lets say there are 5 max in the array all over the array .
the first element will get selected with 100% (first time). the chances that it will remain the final outout that it has to survive the next 4 coin toss. which means
1* (1 -1/2) * (1-1/3)*(1-1/4)*(1-1/5) = 1*1/2/*2/3*3/4*4/5 = 1/5

prob that 2nd max becomes the final number = 
(1/2)*(1-1/3)*(1-1/4)*(1-1/5) = 1/5. .... 

though my first thought was to simply count the total number of max element in first pass and just generate a random number (x) between 1 to 5 ( if 5 is the total count) and in 2nd pass simply return the xth element.

Randomly Return 0 or 1

Write a function to get a positive integer n as input and return 0 or 1. The probability of returning 1 should be 1/(2^n)

因为是1/2^n，那么执行最多n次rand() % 2即可。连续n次随机到0的概率就是1/(2^n)，中途只要随机到1就立即返回0即可。

int rand_0_1(int n) {
    for(int i = 0; i < n; ++i) 
        if(rand() % 2 == 1) return 0;
    return 1;
}

Random Node in A Binary Tree

void randNodeImp(const TreeNode * node, int & idx, const TreeNode * & r) {
    if (!node) return;
    if (rand(idx) == 0)
        r = node;
    randNodeImp(node->left,  ++idx, r);
    randNodeImp(node->right, ++idx, r);
}

const TreeNode * randNode(const TreeNode * root) {
    int idx = 1;
    const TreeNode * r = 0;
    randNodeImp(root, idx, r);
    return r;
}

results matching ""

    No results matching ""