Massive Algorithms: Google

X.

落雨滴

第五轮是有一个0-1的线条，然后有一雨点掉下来(position)，这个雨点掉在这个线条上会散开成 0.01 m 长的范围，然后设计两个api，一个是掉雨点，一个是查询当前的线条是不是都已经被雨点覆盖了

思路：

见帖子雨滴落到线条

https://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=176388
you have 1 meter walkroad, and randomly generate rain, the rain is 1 cm. simulate how many rain drops to cover all the 1 meter [-0.01~1].

static class Interval {
double left = 0, right = 0.01;
boolean isWet() {
return left >= right;
}
}
public static void main(String[] args) {
simulateRainDrop();
}
public static void simulateRainDrop() {
Interval[] sidewalk = new Interval[100];
for (int i = 0; i < 100; i++) {
sidewalk[i] = new Interval();
}
int cnt = 0, wetCnt = 0;
while (wetCnt < 100) {
++cnt;
double p = Math.random();
double left = p - 0.005;
double right = p + 0.005;
if (left >= 0) {
int idx = (int) (left / 0.01);
if (!sidewalk[idx].isWet()) {
double iright = left - idx * 0.01;
if (iright < sidewalk[idx].right) {
sidewalk[idx].right = iright;
if (sidewalk[idx].isWet())
++wetCnt;
}
}
}
if (right <= 1) {
int idx = (int) (right / 0.01);
if (!sidewalk[idx].isWet()) {
double ileft = right - idx * 0.01;
if (ileft > sidewalk[idx].left) {
sidewalk[idx].left = ileft;
if (sidewalk[idx].isWet())
++wetCnt;
}
}
}
}
System.out.println(cnt);
}

定义一个
struct interv {
double left=0, right=0.01;
bool isWet() {
return left>=right;
}
};
就好了，然后生成0,1之间的一个均匀分布，模拟每个雨滴看落到哪个interval里，直
到100个都打湿。

vector<interv> sidewalk(100,interv());
int cnt=0, wetCnt=0, idx;
while(wetCnt<100) {
         ++cnt;
         double p= (double)(rand())/RAND_MAX;
         double left=p-0.005;
         double right=p+0.005;
         if(left>=0) {
            idx=left/0.01;
            if(!sidewalk[idx].isWet()) {
                  iright=left-idx*0.01;
                  if (iright<sidewalk[idx].right) {
                     sidewalk[idx].right=iright;
                     if(sidewalk[idx].wet()) ++wetCnt;
                  }
            }
         }
         if(right<=1) {
            idx=right/0.01;
            if(!sidewalk[idx].wet()) {
                  ileft=right-idx*0.01;
                  if (ileft>sidewalk[idx].left) {
                     sidewalk[idx].left=ileft;
                     if(sidewalk[idx].isWet()) ++wetCnt;
                  }
            }
         }
      }

用merge intervals
Google – Rain Drop Problem
有一个1m长的side walk, 假设是0到1。雨滴的宽度为0.01m，每次下雨的位置随机，雨滴和雨滴之间可能no overlap, complete overlap和partial overlap。问多少雨滴才能覆盖整个side walk。

模拟整个下雨过程，返回总共需要的雨滴数
算期望值。

[Analysis]
(1) 首先这道题我在模拟的过程中碰到一个问题，因为double精度的关系，在[0.0, 1.0]之间相当于有"无数"个点，导致在模拟过程中下了几十万滴雨都没有把整个side walk覆盖。因为想象一下，比如现在下了2滴雨, range分别为
[0.2000000000000001, 0.2100000000000001]
[0.2200000000000001, 0.2300000000000001]
但是其实这两滴雨之间还有"无数"个点没有被覆盖。
所以我觉得这道题应该要保留两位小数，这样像上面那两滴雨已经算把0.20 ~ 023这段完全覆盖了。
(2) 另一个需要保留两位小数的理由就是Java的double type真是能虐死人。

0.09 + 0.01 = 0.09999999999999999

(3) 还有一点需要注意的是，这道题random雨滴的范围不应该是[0.0, 1.0]，而应该是[-0.01, 1.0]，因为雨滴宽度的关系，如果random范围是[0.0, 1.0]的话，那么0.0被覆盖的概率和其他点被覆盖的概率是不一样的，只有当random到0.0的时候才会被覆盖，但是比如1.0这个点，random到0.99和1.0都能被覆盖。
所以我们需要等概率的来random[-0.01, 1.0]的之间的数并保留两位小数。方法有点类似于rand2 to rand6，保证概率的一致性。

1.01 * Math.random() – 0.01

[Solution]
模拟的过程有两种解法
__[Solution #1]__
merge interval + rand2 to rand6 + binary search
思路就是维护一个list of interval, 每次random一个新的雨滴，通过binary search来找插入位置。然后merge.
注意这道题的merge并不像一般的merge interval一样，因为这道题确定每个新的interval range都是0.01, 所以找到插入点后只需要merge前后两个就好了。
但是就算这样，其实这道题merge interval并不好做，因为比如[0.20, 0.21]和[0.22, 0.23]这两个interval就要merge了，而不是非要curr.start = prev.end才能和前面merge。另外binary search也是难写的一比。
后面有merge interval的code，但是真不知道对不对，binary search也偷懒了直接linear search了。
__[Solution #2]__
后来发现如果保留两位小数的话，其实0.0到1.0之间就是100个点。我们完全可以避免double带来的一堆麻烦。也可以不用merge来merge去的。
直接开个size为100的array作为bucket，每次random一个[-1, 100]的数，那么雨滴范围就是[start, start + 1]。看start和start + 1的bucket是否为空，是的话，bucket置1，bucketCnt++。直到bucketCnt为100为止。
[期望]
网上看来的：
一共100个buckets, 假设现在剩余x个buckets为空，那么
雨滴落在这x个buckets里的概率为x / 100，这样剩余的buckets就为x – 1
雨滴没有落在这x个buckets里的概率为(100 – x) / 100，剩余的buckets仍然为x
那么
f(x) = f(x – 1) * (x / 100) + f(x) * (100 – x) / 100 + 1
100 * f(x) = x * f(x – 1) + (100 – x) * f(x) + 100
f(x) = f(x – 1) + 100 / x
f(x) = 100 * (1 + 1/2 + 1/3 + 1/4 + … + 1/x)，后面那一串称为调和级数。
那么对于这道题来说，期望就是f(100) = 518.737752

这道题如果真被问到，模拟过程的算法肯定是重点。
期望的话可以说个大概的数字。能分析出概率情况写出上面第一个式子已经非常不错了。调和级数不调和级数这种东西，面试官是不会期待有人能答出来的。

class Solution {

  int N = 100;

  public int rainDrop() {

    Random rand = new Random();

    boolean[] buckets = new boolean[N];

    int cnt = 0;

    int bucketCount = 0;

    while (true) {

      int randStart = rand.nextInt(N) - 1;

      int randEnd = randStart + 1;

      cnt++;

      if (randStart >= 0 && !buckets[randStart]) {

        buckets[randStart] = true;

        bucketCount++;

}

      else if (!buckets[randEnd]) {

        buckets[randEnd] = true;

        bucketCount++;

}

      if (bucketCount == N) {

        break;

}

}

    return cnt;

}

}

class Solution2 {

  public int rainDrop() {

    List<Interval> intervals = new ArrayList<>();

    int cnt = 0;

    while (true) {

      double randStart = 1.01 * Math.random() - 0.01;

      randStart = round(randStart);

      double randEnd = randStart + 0.01;

      randEnd = round(randEnd);

      Interval newInterval =  new Interval(randStart, randEnd);

      int index = binarySearch(intervals, newInterval);

      mergeIntervals(intervals, index, newInterval);

      if (intervals.size() == 1 && intervals.get(0).start <= 0.0 && intervals.get(0).end >= 1.0) {

        break;

}

      else {

        cnt++;

}

}

    return cnt;

}

  private int binarySearch(List<Interval> intervals, Interval newInterval) {

    for (int i = 0; i < intervals.size(); i++) {

      if (newInterval.start <= intervals.get(i).start) {

        return i;

}

}

    return intervals.size();

}

  private void mergeIntervals(List<Interval> intervals, int index, Interval newInterval) {

    Interval curr = newInterval;

    if (intervals.isEmpty()) {

      intervals.add(newInterval);

}

    else if (index == 0) {

      if (newInterval.start == intervals.get(0).start) {

        return;

}

      else if (round(newInterval.end + 0.01) >= intervals.get(0).start) {

        intervals.get(0).start = Math.min(intervals.get(0).start, newInterval.start);

}

      else {

        intervals.add(0, newInterval);

}

}

    else if (index == intervals.size()) {

      Interval last = intervals.get(intervals.size() - 1);

      if (round(last.end + 0.01) >= newInterval.start) {

        last.end = Math.max(last.end, newInterval.end);

}

      else {

        intervals.add(newInterval);

}

}

    else {

      Interval prev = intervals.get(index - 1);

      Interval next = intervals.get(index);

      if (round(prev.end + 0.01) < newInterval.start && round(newInterval.end + 0.01) < next.start) {

        intervals.add(index, newInterval);

}

      else {

        if (round(prev.end + 0.01) >= newInterval.start && round(newInterval.end + 0.01) >= next

            .start) {

          prev.end = next.end;

          intervals.remove(next);

}

        else if (round(prev.end + 0.01) >= newInterval.start) {

          prev.end = Math.max(prev.end, newInterval.end);

          if (round(prev.end + 0.01) >= next.start) {

            prev.end = next.end;

            intervals.remove(next);

}

}

        else if (round(newInterval.end + 0.01) >= next.start) {

          next.start = Math.min(newInterval.start, next.start);

          if (round(prev.end + 0.01) >= next.start) {

            prev.end = next.end;

            intervals.remove(next);

}

}

        else {

          intervals.add(index, newInterval);

}

}

}

}

  private double round(double d) {

    return (double) Math.round(d * 100) / 100;

}

  private class Interval {

    double start;

    double end;

    Interval(double start, double end) {

      this.start = start;

      this.end = end;

}

}

}

Read full article from Google – Rain Drop Problem

Google – Rain Drop Problem

落雨滴

Labels

Popular Posts