## Monday, August 8, 2016

### Google – Generate Strings Based on Probability

Google – Generate Strings Based on Probability

[Solution]

[Solution #1]
Cumulative sum + binary search, O(logn)

A的概率区间是 (0, 0.5]
B的概率区间是 (0.5, 0.6]
C的概率区间是 (0.6, 0.8]
D的概率区间是 (0.8, 1]

[Solution #2]
buckets, O(1)

[Note]

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