### Another Math/Stat related Interview Question

http://discuss.joelonsoftware.com/default.asp?joel.3.476021.48
The answer seems like 1:1, but I am not sure because later rrounds of throws are conditional on earlier rounds.

Incidentally I think it's a fair question if the programming job require S/P skills, even though it's quite useless for interviews since ... the probability of false positive is quite high :)

Perhaps it's ok for phone screen interviews...

Rick Zeng/Tseng
April 5th, 2007 8:49pm

Given an infinite number of people, you get an asymptotal curve that approaches 1:1 but never reaches it.

[Repost of how I answered there. --MB]

Thinking is for assholes. Simulate:

$ cat h2t.py

#!/usr/bin/python

import random

N = 100000

def heads_or_tails():

if random.randrange(2):

return 'heads'

return 'tails'

class tosser:

def __init__(self):

self.tosses = []

def flip(self):

ht = heads_or_tails()

self.tosses.append(ht)

if ht == 'tails':

return False

return True

def main():

people = []

for i in xrange(N):

person = tosser()

while person.flip():

pass

people.append(person)

heads = 0

tails = 0

for person in people:

for toss in person.tosses:

if toss == 'heads':

heads += 1

else:

tails += 1

print 'heads:tails = %d:%d' % (heads,tails)

main()

Tests:

$ ./h2t.py

heads:tails = 99939:100000

$ ./h2t.py

heads:tails = 100033:100000

$ ./h2t.py

heads:tails = 100110:100000

The answer is 1:1

Michael B
April 5th, 2007 9:33pm

Wow, what a precise summary, my (presumed) Russian friend!

Of course, I want the answer to be a function of n. :)

Also I really like Peter's approach. Sigh, I should have paid more attention in my only S&P class in university.

Rick Zeng/Tseng
April 6th, 2007 4:23am

You only need to construct a chart of the first 7 or so coin tosses to see what's happening.

What's happening is the "if you travel half the distance to a line each minute, you'll come close to crossing it but will never actually cross it."

Given 100 people, you know there are 100 tails - once someone gets a tail they stop. So then it's a matter of counting heads.

First round you get 50 heads.

Second round you get half of 50 heads, or 25 for a total of 75.

Third round you get half of 25 for a total of ~88 and so on, halving until you get as close to 1:1 as possible before running out of people. You end up with a graph that looks like this:

1: **********

2: ***************

3: ******************

4: *******************

5: ********************

6: ********************

Interestingly, that graph could be for either heads or tails as each round half the people get heads and half the people get tails, so from that point of view, the folks who say it's 1:1 are also correct.

Gosh, nobody accused Rick of "repost dildo". I wonder why that is?

SaveTheHubble
April 6th, 2007 10:09am

Good point. Repost Dildo.

Ward
April 6th, 2007 1:46pm

D'oh!

SaveTheHubble
April 6th, 2007 2:44pm