Google Interview Question
SDE1sCountry: United States
I assume I eat a red bean only if I pick 2 red beans in a row.
For the case when there are only 2 beans in the jar, 1 white and 1 red, it's not difficult to derive the probabilities by considering all possible scenarios:
1. We pick the white and eat it. Probability 1/2. The red is the last.
2. We pick the red, place it back, and pick the red again, and eat it. Probability 1/4. The white is the last.
3. We pick the red, place it back, and pick the white, and eat it. Probability 1/4. The red is the last.
So, the probability of the white to be the last bean is 1/4, and probability of the red bean to be the last is 3/4 (1/2 + 1/4).
For the other amounts of white and red beans (like 3 white and 5 red), it doesn't look easy to derive a formula including w and r. The code simulates the process and calculates the probability for arbitrary amounts of w an r.
double LastBeanIsWhiteProbability(int w, int r, unordered_map<uint64_t, double> &memo, bool prev_red = false)
{
if (r < 0 ||
w < 0)
{
return 0;
}
if (r == 0) {
return 1;
}
if (w == 0) {
return 0;
}
uint64_t memo_key = (static_cast<uint64_t>(w) << 48) | (static_cast<uint64_t>(r) << 32) | prev_red;
auto it = memo.find(memo_key);
if (it != memo.end()) {
return it->second;
}
double prob =
(static_cast<double>(w) / (r + w)) * LastBeanIsWhiteProbability(w - 1, r, memo, false) +
(static_cast<double>(r) / (r + w)) * LastBeanIsWhiteProbability(w, prev_red ? r - 1 : r, memo, prev_red ? false : true);
memo[memo_key] = prob;
return prob;
}
The transition (W, R) -> (W - 1, R) has probability 1 - [R/(W+R)]^2, and the transition (W, R) -> (W, R - 1) has probability [R/(W+R)]^2.
After that you need just a couple of nested loops:
double last_white_prob(std::size_t nw, std::size_t nr)
{
const auto sq = [](double x) { return x * x; };
std::vector<double> prob(nr + 1);
prob[nr] = 1;
for (auto r = nr; r > 0; --r)
prob[r - 1] = sq(r) * prob[r] / sq(nw + r);
for (auto w = nw - 1; w > 0; --w)
{
prob[nr] *= 1 - sq(nr) / sq(w + nr + 1);
for (auto r = nr; r > 0; --r)
prob[r - 1] += (sq(r) * prob[r] - sq(r - 1) * prob[r - 1]) / sq(w + r);
}
return prob[0];
}
Trivial case: 0 white prob 0; 0 red prob 1
Otherwise each pick can have 3 outcomes 1. pick white and eat it. 2. pick red and eat, if last pick put red back 3. pick red and put back.
Each outcome gives a new sample (1) gives w-1,r while (2) gives w, r-1 and (3) gives w,r but last red put back is true
Recursively calculate probability of last white in each of 3 outcomes. Then multiply result of each outcome with the probability of that outcome. And you have your result. Here is a solution using DP with memoization:
- DO December 07, 2017