3.6.4. Questions

3.6.4.1. Raindrop

You have 1 meter walk-road, and randomly generate rain, the rain is 1cm long. Simulate how many rain drops to cover 1 meter [-50cm~50cm].

Note:

  • Rain drop could overlap with each other.

  • You can assume the rain drops always at integer positions. The start position is always integer.

The following is an example of 3 rain drops at position 4 and 7.

                                             x
|_|_|_|_|_|_|_|_|_|_|   ==>   |_|_|_|_|x|_|_|x|_|_|
 0 1 2 3 4 5 6 7 8 9           0 1 2 3 4 5 6 7 8 9

Solution 1: Simple Simulation

To solve this problem, we can just simulate it with the following code.

Code Block 3.6.1 Simple Simulation
 1namespace rain_drop_v1{
 2    int simulate(int z=100) {
 3        int total_rain = 0, covered = 0;
 4        vector<int> rain(z, 0);
 5        while (covered < z) {
 6            int idx = rand() % z;
 7            if (rain[idx] == 0) {
 8                covered++;
 9            }
10            rain[idx]++;
11            total_rain++;
12        }
13        return total_rain;
14    }
15};

Follow up:

  • How about rain drops at any position, which means the start position could be a floating number?

  • Algorithm time complexity? \(O(NLogN)\)

Solution 2: Interval Tree

We can use the interval tree described in Section 3.13.4. Here is an implementation with all the interval length information. We can also implement it with std::list as the underlying data structure and use binary search(std::lower_bound) to find the insertion point, and the speed will be faster due to lower implementation overhead when the size of the list is not too long.

Code Block 3.6.2 Interval tree with all length information
 1struct interval_tree_with_len : interval_tree {
 2  multiset<int> lens;
 3  void insert(int head, int tail) {  // TC: O(N)
 4    auto it = m.upper_bound(head);   // O(logN)
 5    if (it != m.begin()) {
 6      it = prev(it);
 7      if (overlapped(it->first, it->second, head, tail)) {
 8        head = min(it->first, head), tail = max(it->second, tail);
 9        int tmp = it->second - it->first;
10        l -= tmp;
11        it = m.erase(it);
12        lens.erase(lens.find(tmp));
13      }
14    }
15    while (it != m.end()) {
16      if (overlapped(it->first, it->second, head, tail)) {
17        head = min(it->first, head), tail = max(it->second, tail);
18        int tmp = it->second - it->first;
19        l -= tmp;
20        it = m.erase(it);
21        lens.erase(lens.find(tmp));
22      } else {
23        it++;
24      }
25    }
26    m[head] = tail;
27    lens.insert(tail - head);
28    l += tail - head;
29  }
30  bool has_length(int x) { return lens.find(x) != lens.end(); }
31  int max_length() { return *lens.rbegin(); }
32};

Note the rain has length of 1 cm, so the start range is [-50, 49], instead of [-50, 50].

Code Block 3.6.3 Simulate raindrop
 1int simulate() {
 2  const double RAIN_LEN = 1;
 3  interval_tree_with_len itree;
 4  int r = 0;
 5  do {
 6    r++;
 7    int start = rand() % 100 - 50;
 8    itree.insert(start, start + RAIN_LEN);
 9  } while (itree.max_length() < 100);
10  return r;
11}

Solution 3: Harmonic Number:

Note

In probability theory, the coupon collector’s problem describes “collect all coupons and win” contests. It asks the following question: If each box of a brand of cereals contains a coupon, and there are n different types of coupons, what is the probability that more than t boxes need to be bought to collect all n coupons? An alternative statement is: Given n coupons, how many coupons do you expect you need to draw with replacement before having drawn each coupon at least once? The mathematical analysis of the problem reveals that the expected number of trials equal to \(N*H_n\) where \(H_n\) is the nth harmonic number. For example, when n = 50 it takes about 225 trials on average to collect all 50 coupons.

This problem is a variant of Coupon Collector’s Problem.

Code Block 3.6.4 is the harmonic function.

Code Block 3.6.4 Nth Harmonic number
1double harmonic_number(int n) {
2  double t = 0.0;
3  while (n > 0) t += 1.0 / n, n--;
4  return t;
5}

The simulation result should match 518.

3.6.4.2. Shuffle an Array In-Place

Fisher–Yates Shuffle Algorithm works in \(O(N)\) time complexity. The assumption here is, we are given a function rand() that generates random number in \(O(1)\) time.

1  void shuffle1(vector<int>& vi){
2    int L=vi.size();
3    for(int i=L-1; i>=1; i--)
4      swap(vi[rand() % (i+1)],vi[i]); // note: i+1

3.6.4.3. Uniform Distribution With Biased Base Function

Given a function get_01_pq(), which return 1 with probability p, and 0 with probability（1-p).

Create a function get_0_to_N_uniform(), return a number with in range [0-6] with equal probability

3.6.4.4. 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, so too much extra space is not allowed.

Example:

1int[] nums = new int[] {1,2,3,3,3};
2Solution solution = new Solution(nums);
3// pick(3) should return either index 2, 3, or 4 randomly.
4// Each index should have equal probability of returning.
5solution.pick(3);
6// pick(1) should return 0. Since in the array only nums[0] is equal to 1.
7solution.pick(1);