## Monday, August 8, 2016

### Google – Rain Drop Problem

1. 模拟整个下雨过程，返回总共需要的雨滴数
2. 算期望值。
[Analysis]
(1) 首先这道题我在模拟的过程中碰到一个问题，因为double精度的关系，在[0.0, 1.0]之间相当于有"无数"个点，导致在模拟过程中下了几十万滴雨都没有把整个side walk覆盖。因为想象一下，比如现在下了2滴雨, range分别为
[0.2000000000000001, 0.2100000000000001]
[0.2200000000000001, 0.2300000000000001]

(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都能被覆盖。

1.01 * Math.random() – 0.01

[Solution]

__[Solution #1]__
merge interval + rand2 to rand6 + binary search

__[Solution #2]__

[期望]

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)，后面那一串称为调和级数。

`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;`
`    ``}`
`  ``}`
`}`