Google – Generate Strings Based on Probability

Google – Generate Strings Based on Probability
给一个label [A B C D], 和一个probability [0.5 0.1 0.2 0.2]表示每个label出现的概率, 要求生成一个满足概率条件的id序列。

[Solution]
思路就是每次得到一个0~1的random number，看它在哪个概率区间里。
[Solution #1]
Cumulative sum + binary search, O(logn)
要计算cumulative sum的目的是得到概率区间，比如
A的概率区间是 (0, 0.5]
B的概率区间是 (0.5, 0.6]
C的概率区间是 (0.6, 0.8]
D的概率区间是 (0.8, 1]
这样cumulative sum就是sums[] = [0.5, 0.6, 0.8, 1.0]，所以每次generate一个0到1的random number之后，binary search在sums[]里找它的ceiling，对应的位置就是要输出的label。
[Solution #2]
buckets, O(1)
但有限制，每个概略只能有1位小数。,
思路就是开个size为10的array, 比如题目的例子就可以得到[A A A A A B C C D D], 然后generate一个0~9的数字输出对应label。
这样可以避免binary search在O(1)时间内从random number得到对应label。

但是前提是概率只能有1以为小数。要是有2位小数，就要开size为100的数组，要是有k位，就要开size为10^k的数组。
而Java array的最大长度是一个不超过Integer.MAX_VALUE的值，如果k大于10的话，就要Overflow了。

[Note]
有一点需要注意，最近在刷其他题的时候差点被坑死。简直智商被狗吃了。

不是所有的cumulative sum都是递增的！如果出现负数的话就是无序的，不要看到cumulative sum就想着binary search. 这里因为是概率所以不会出现负数的情况。

  public String generateString(char[] label, double[] prob) {

 

    int n = label.length;

    double[] cumuProb = new double[n];

    cumuProb[0] = prob[0];

    for (int i = 1; i < n; i++) {

      cumuProb[i] = cumuProb[i - 1] + prob[i];

    }

 

    Random rand = new Random();

    StringBuilder sb = new StringBuilder();

    for (int i = 0; i < 10; i++) {

      double p = rand.nextDouble();

      int index = binarySearch(cumuProb, p);

      sb.append(label[index]);

    }

 

    return sb.toString();

  }

 

  private int binarySearch(double[] cumuProb, double p) {

    int l = 0;

    int r = cumuProb.length - 1;

    while (l <= r) {

      int mid = l + (r - l) / 2;

      if (cumuProb[mid] == p) {

        return mid;

      }

      else if (cumuProb[mid] < p) {

        l = mid + 1;

      }

      else {

        r = mid - 1;

      }

    }

 

    if (l >= cumuProb.length || r < 0) {

      return l >= cumuProb.length? r : l;

    }

 

    return cumuProb[l] < p? l + 1 : l;

  }

Read full article from Google – Generate Strings Based on Probability