Virtu Financial Interview Question: 3) Imagine you are out playin... | Glassdoor

Interview Question

Trading Analyst Interview London, England (UK)

3) Imagine you are out playing golf with 2 friends. You

  need to decide randomly, and fairly, the player to go first. You have a fair coin with you, which you can flip. How do you use the coin to decide who goes first, with an emphasis on minimizing the number of flips you need to make?
Answer

Interview Answer

4 Answers

0

You group your friends as if they're one person, so if you lose, you can make another flip for just the both of them.

anonymous on Mar 16, 2012
0

That doesn't seem fair as you can win on the first flip but it would take one of your friends two flips to win. So chances of winning: You: 50%, Friend1: 25%, Friend 2: 25%

The only fair way that I can think of is that you do it like this:

1. You vs Friend 1
2. Winner of #1 vs Friend2 If Winner of #1, wins this then they go first, otherwise
3. Loser of #1 vs Friend2 If Friend2 wins flip #2 and #3 then they go first

If everyone wins 1 flip each then you start again. This will happen 25% of the time.
When you factor this in the above method finds a winner after 4 flips (3+3/4+3/16+.....) whilst giving everyone an equally fair opportunity to win.

Sperick on Mar 22, 2012
0

I should clarify: That method finds a winner after 2 flips 50% of the time, after 3 flips 25% and ties after three flips the other 25% of the time. On average it will take 4 flips to win although this will never happen as, if it is tied after 3 flips, then it will take at least 2 more to determine a winner.

Sperick on Mar 22, 2012
9

Flip the coin twice and record the result of both tosses. We'll let the sequence of flips - HH - represent you winning the coin toss. Let the sequence - TH - represent Friend 1 winning and let the sequence - TT - represent Friend 2 winning. Notice that everybody has an equal chance of winning. If the coin tosses result in the sequence HT, repeat the process and flip the coin twice again.

This will take an average of 8/3 coin tosses. To find this - let x be the expected number of coin tosses this algorithm will take. Then x = 3/4 * 2 + 1/4 * (x + 2). Solving this yields x = 8/3.

Anonymous on Apr 15, 2012

Add Answers or Comments

To comment on this, Sign In or Sign Up.