Randomly choosing k samples from a list of n items, where n is either a very large or unknown number. We are given a big array (or stream) of numbers (to simplify), and we need to write an efficient function to randomly select k numbers where 1 <= k <= n. Let the input array be stream[].

How does this work?

Case 1: For last n-k stream items, i.e., for stream[i] where k <= i < n

for item i in (k,n), it’s chosen P = k / i,

then for item i+1 not choose same as i: P=i/i+1,

then for item i+2 not choose same as i : P=i+1/i+2

So for item in (k,n), P = k/i (i/i+1) (i+1/i+2) * … (n-1/n) = k/n

Case 2: For first k stream items, i.e., for stream[i] where 0 <= i < k
The first k items are initially copied to reservoir[] and may be removed later

for item in (0,k), it’s not chosen to be replaced P=(k/k+1) (k+1/k+2) … * (n-1/n) = k/n

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

public int[] selectK(int[] nums,int k) {
	
	int[] result = new int[k];
	Random random = new Random();
	// init result
	for(int i=0; i<k; ++i) 
		result[i] = nums[i];
	// random replacement
	for(int i=k; i<nums.length; ++i) {
		// pick idx from 0 to i
		int idx = random.nextInt(i+1);
		if(idx < k)
			result[idx] = nums[i];
	}
	return result;
}

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:

1
2
3
4
5
6
7
8

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);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class  {

    int[] nums;
    Random random;
    
    public (int[] nums) {
        this.nums = nums;    
        this.random = new Random();
    }
    
    public int pick(int target) {
        int idx = -1, count = 0;
        for(int i=0; i<nums.length; ++i){
            if(nums[i] != target)
                continue;
            // x target, each 1/x probability
            if(random.nextInt(++count) == 0)
                // == count - 1 works as well
                idx = i;
        }
        return idx;
    }
}

Given a stream of numbers, generate a random number from the stream. You are allowed to use only O(1) space and the input is in the form of stream, so can’t store the previously seen numbers.

1) Initialize ‘count’ as 0, ‘count’ is used to store count of numbers seen so far in stream.

2) For each number ‘x’ from stream, do following

​ a) Increment ‘count’ by 1.

​ b) If count is 1, set result as x, and return result.

​ c) Generate a random number from 0 to ‘count-1’. Let the generated random number be i.

​ d) If i is equal to ‘count – 1’, update the result as x.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

int count = 0;
int result = 0;

// input element from stream
public int selectRandom(int x) {
	count++;
	if (count == 1)
		result = x;
	else {
		Random random = new Random();
		// i from o to count - 1
		int i = random.nextInt(count);
		if (i == count - 1) // i == 0 works as well
			// set result to x
			// probability = 1 / count
			result = x;
	}
	return result;
}

Random choose an element from a dict based on frequency

1
2
3
4
5
6
7
8
9
10
11

Let following be the given numbers.
  arr[] = {10, 30, 20, 40}  

Let following be the frequencies of given numbers.
  freq[] = {1, 6, 2, 1}  

The output should be
  10 with probability 1/10
  30 with probability 6/10
  20 with probability 2/10
  40 with probability 1/10

Using array and binary search:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

public int weightedSelect(int[] nums, int[] freq) {
	// get accumulated freq sum
	for (int i = 1; i < freq.length; ++i)
		freq[i] += freq[i - 1];
       Random random = new Random();
	int idx = random.nextInt(freq[freq.length - 1]) + 1;
	// uses binary search to find position
	int left = 0, right = nums.length - 1;
	while (left < right) {
		int mid = left + (right - left) / 2;
		if (freq[mid] == idx)
			return nums[mid];
		else if (freq[mid] < idx)
			left = mid + 1;
		else
			right = mid;
	}
	return nums[left];
}

Using TreeMap:

1
2
3
4
5
6
7
8
9
10
11
12

public int weightedSelect(int[] nums, int[] freq) {
	// using TreeMap
	int sum = 0;
	TreeMap<Integer, Integer> treeMap = new TreeMap<>();
	Random random = new Random();
	for (int i = 0; i < freq.length; ++i) {
		sum += freq[i];
		treeMap.put(sum, nums[i]);
	}
	int idx = random.nextInt(sum) + 1;
	return treeMap.ceilingEntry(idx).getValue();
}

Given an array, write a program to generate a random permutation of array elements.

The idea is to start from the last element, swap it with a randomly selected element from the whole array (including last). Now consider the array from 0 to n-2 (size reduced by 1), and repeat the process till we hit the first element.

Following is the detailed algorithm

1
2
3
4

To shuffle an array a of n elements (indices 0..n-1):
  for i from n - 1 downto 1 do
       j = random integer with 0 <= j <= i
       exchange a[j] and a[i]

1
2
3
4
5
6
7
8
9

public void shuffle(int[] nums) {
	Random random = new Random();
	for (int i = nums.length - 1; i > 0; --i) {
		int j = random.nextInt(i+1); // shoud i+1 not i
		int temp = nums[i];
		nums[i] = nums[j];
		nums[j] = temp;
	}
}

For position i:

(1) i is not swapped after shuffle = P(i is not selected from n to i+1) * P(i is selected at i)

P = (n-1/n n-2/n-1 … i/i+1) (1/i) = 1/n

(2) i is replaced by j P(j is at i):

1. j < i. P = P(i not selected from n to i+1) P(j is selected when i) = (n-1/n n-2/n-1 … i/i+1) * (1/i) = 1/n
2. j>i. P = P(j not selected from n to j+1) P(i is selected when j) = (n-1/n n-2/n-1 … j/j+1) * (1/j) = 1/n

For conclusion, all num from o to n, the possibility to at a position i is 1/n

Given a blacklist B containing unique integers from [0, N), write a function to return a uniform random integer from [0, N) which is NOT in B.

Optimize it such that it minimizes the call to system’s Math.random().

Note:

random5() returns[1,5] equal possibility, get random7() (return [1,7])equal possibility.

random5() => [1,2,3,4,5]

5*random5() => [5,10,15,20,25]

5*random5() + random5() - 5 => [1,2,3,…,25]

then get

1
2
3
4
5
6

public int random7(){
    int num = 5 * random5() + random5() - 5;
    if(num < 22)
        return num % 7 + 1;
    return random7();	// recursive call
}

7*rand7() + rand7() - 7 => [1,49]

then get[1,40] to get rand10()

1
2
3
4
5
6
7
8
9

public int rand10() {
    // get [1,49]
    int num = 7 * rand7() + rand7() -7;
    // get [1,40]
    if(num < 41)
        // % get [0,9]
        return num % 10 + 1;
    return rand10();
}