## Google Interview Question for SDE1s

• 0

Country: United States

Comment hidden because of low score. Click to expand.
1
of 1 vote

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:

``````#include<iostream>
#include<vector>
#include<map>

using namespace std;

map<vector<int>,float> M;

float
recGetLastWhiteProb(int w, int r, bool lastRedPutBack)
{
// Simple cases
if(w==0)
return 0;
if(r==0)
return 1;

// Memoization: if we have seen this before we have the probability
vector<int> S = {w, r, lastRedPutBack ? 1 : 0};
auto it = M.find(S);
if(it != M.end())
return (*it).second;

// If we pick white now(and eat it) whats probability of lastWhite in remaining
float p1 = recGetLastWhiteProb(w-1,r,false);
float p2;
// If we pick red now, whats probability of lastWhite in remaining
if(lastRedPutBack)
// Eat red case
p2 = recGetLastWhiteProb(w, r-1, false);
else
// Put red back case
p2 = recGetLastWhiteProb(w, r, true);
// The probability of picking white in this iteration X probability of lastWhite after that +
// The probability of picking red in this iteration X probability of lastWhite after that
float prob = (float(w)/float(w+r))*p1 + (float(r)/float(w+r))*p2;
M[S] = prob;
return prob;
}

float
getLastWhiteProb(int numWhite, int numRed)
{
return recGetLastWhiteProb(numWhite,numRed,false);
}

int
main(int argc, char *argv[])
{
int numWhite, numRed;
cin>>numWhite>>numRed;
getLastWhiteProb(numWhite,numRed);
vector<int> S = {numWhite, numRed, 0};
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

@DO. I was wrong. Sorry. The probability in case of 1 white and 2 red is 2/3 * 2/3 * 1/2 * 1/2 = 1/9 ~ 0.11. Your solution is absolutely correct!

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.