Google Interview Question for SDE1s


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};
    cout<<"Answer: "<<getLastWhiteProb(numWhite,numRed)<<endl;
}

- DO December 07, 2017 | Flag Reply
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;
}

- Alex December 06, 2017 | Flag Reply
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!

- Alex December 07, 2017 | Flag Reply
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[0];
}

- Evg February 27, 2020 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More