Questions
=========================================


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.

.. code-block:: c++

                                                 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.

.. literalinclude:: raindrop_test.cpp
  :language: c++
  :lines: 11-25
  :emphasize-lines: 5-12
  :linenos:
  :caption: Simple Simulation


**Follow up**:

- How about rain drops at any position, which means the start position could be a floating number?
- Algorithm time complexity? :math:`O(NLogN)`

**Solution 2: Interval Tree**

We can use the interval tree described in :numref:`interval_tree`. 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.

.. literalinclude:: raindrop.h
  :language: c++
  :lines: 14-45
  :emphasize-lines: 2, 12, 21, 27
  :linenos:
  :caption: Interval tree with all length information

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

.. literalinclude:: raindrop.h
  :language: c++
  :lines: 57-67
  :emphasize-lines: 7
  :linenos:
  :caption: Simulate raindrop

**Solution 3: Harmonic Number**:

.. note::

  In probability theory, the `coupon collector's problem <https://en.wikipedia.org/wiki/Coupon_collector%27s_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 :math:`N*H_n` where :math:`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**.

:numref:`harmonic` is the harmonic function.

.. literalinclude:: raindrop.h
  :language: c++
  :lines: 47-51
  :linenos:
  :name: harmonic
  :caption: Nth Harmonic number

The simulation result should match 518.


Shuffle an Array In-Place
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

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


.. code-block:: c++
  :linenos:

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


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


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:

.. code-block:: c++
  :linenos:

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