Google Interview Question: 15 Minuten vom zweiten Gesprä... | Glassdoor

Interview Question

Produktmanager Interview Zürich (Switzerland)

15 Minuten vom zweiten Gespräch beschäftigten sich mit

  einer Münz-Denksportaufgabe: Sie haben eine Münze und 3 Türen. Wie wählt man eine der drei Türen aus, indem man die Münze wirft? Wie hoch ist die Wahrscheinlichkeit nach dem ausgewählten Algorithmus, jede der drei Türen zu wählen? Kann man ihn so wählen, dass die Wahrscheinlichkeit für alle drei Türen gleich ist? Der Gesprächspartner wollte anscheinend keine Lösung hören, die anders war als seine Antwort (oder die im Buch? :)). Vorgeschlagener Algorithmus: K=Kopf Z=Zahl Werfen Sie die Münze zweimal: KK oder ZZ -> nehmen Sie Tür Nr. 3 sonst benutzen Sie das Ergebnis des allerersten Wurfs: wenn (K1) -> nehmen Sie Tür Nr. 1 wenn (Z1) -> nehmen Sie Tür Nr. 2 Ich gebe zu, dass ich diese Frage und die Länge der Zeit, die wir darauf verwendet haben, nicht besonders toll fand. Meiner Meinung nach hätten wir die wirklich kurze Zeit darauf verwenden können, Probleme aus dem echten Leben zu besprechen, die für die Stelle relevant waren, also habe ich versucht, meinen Algorithmus als die "schnelle und einfache" Lösung zu verkaufen und gehofft, dass es dann weitergeht, aber anscheinend war es für meinen Gesprächspartner prinzipiell wichtig, die gleiche Lösung zu finden, die er hatte.
Answer

Interview Answer

7 Answers

1

toss the coin 2times for each door think that H to open the door and T to not open the door

yaswanth babu on Jul 31, 2012
0

I think it not always equal, everything we take a choice there is a new probability shown up, so I always chose my best way to pick that choice if there is an error or disagree from My Boss, I take the risk.

Yunan Yusmanto on Aug 3, 2012
0

Toss the coin 2 times! H = 0, T=1 or vice versa.
Result:
00 = 1st door
01= 2nd door
11 = 3nd door

Manolis Samarakis on Aug 6, 2012
15

I think all the previous answer are somehow incomplete (and the one given by the author of this post is wrong, for this reason he kept asking you the question trying to help).

Toss the coin 2 time. Here the possible outcomes:

HH => try again
HT => Door 1
TH => Door 2
TT => Door 3

This way the probability to choose a door is evenly distributed. And you cover all the possible outcomes.

Ciao!

Claudio on Aug 8, 2012
3

Since you are tossing a coin, the number of outcomes will never be divisible by 3. Thus, no matter how many times you toss the coin, you can never divide the number of outcomes into 3 equal probability groups. This also means that if you MUST choose a door, then one of them will be chosen more often than the others, or NOT choosing must be a possibility. In the latter case, you have to come up with an alternative, like flip two times (4 possible outcomes to match the 4 choices...3 doors + 1'flip again' option). The problem with flipping again option is that you 'leave the door open' to the possibility that you might never choose a door. What if you keep getting the HH option and never open a door?? Thus, a better alternative is needed: Choose two of the doors first (doesn't matter which ones) then flip between them. Winner gets to compete against the third door with the second coin toss. In both cases any door has a 50% chance of being chosen, and the probability does not change for the second try. So, each door has an equal probability of being chosen, AND a door WILL be chosen.

Anonymous on Jul 20, 2014
0

The idea of the question is, most probably, to detect if a candidate understand the idea of binary numbers. A candidate should be aware, most probably, of how to express the notion of digit 3, provided with just 2 available states, that is 1 and 0. In short, one has to write down 3 in base 2

Nazar on Jan 29, 2015
1

There seems to be no absolute solution for this problem. None of the answers so far create a real 1/3 chance for each door. In order to get a real 1/3 possibility for each door, we need to flip the coin in a way that will yield a number of possibilities that divides by 3, so we can divide the possibilities into 3 groups and assign a door to each. When we throw a coin once we get 2^1 = 2 possibilities (H or T), 2 times = 2^2=4 possibilities (HH, TT, HT, TH). For n flips we get 2^n possibilities. No matter what n is, 2^n possibilities will never divide by 3.

So as I see it, there are 2 ways to answer this:
1. Get real close to a 1 out of 3 possibility: flip the coin a lot of times, say 10, which yields 1024 possibilities. Then allocate them to each door - the first 341 possibilities to door 1, the second 341 to door 2 and the rest 342 to the third door. This is not a perfect 1/3 chance but close and the more we flip, the closer we will approach 1/3.
2. Flip 2 times (HH, TT, TH, HT) and always discard HH (in which case we will flip again). That does give a perfect 1/3. But what happens if HH always shows up? Theoretically it can happen no matter how much we flip. Again, flipping a large number of times, reduces this but can not guarantee an answer.

I was asked this and allowed to throw an infinite amount of times. In this case we can get a perfect 1/3 for the first answer and a guarantee that we will reach a conclusion in the second answer (since anything that has a chance to happen in infinity will happen).

Anonymous on Jul 14, 2015

Add Answers or Comments

To comment on this, Sign In or Sign Up.