Saturday, July 30, 2011

Programming Interview Tip : What is the probability that when you open a random page in a phone book the contact you are looking for is in there?

Lets say the phone book pages are numbered from  1 - 1000. And assume that the contact is definitely there in the book.

So when you randomly flip open a book there are 1 of 500 choices that it is one one of the two pages that appear before you.

So the probability is 1/500.

Next Question : How many attempts will it take for me to be certain that the contact is there? 
Well you can NEVER be 100% sure .... for obvious reasons :)

Next Question : So how many attempts will it take for me to be 50% sure that the contact is found in one of the two pages that show up?
The 50% is called percent confidence in statistics lingo.
This is best solved by the difference from 1 for the probability of the contact NOT being on the page.
For each attempt to fail we need to multiply 499/500 . So for n attempts to fail it is (499/500)^n. So the probability of it being successful in n attempts is {1-(499/500)^n}
So you need to solve the equation :
{1-(499/500)^n} = .5
which is obviously :
(499/500)^n = .5
And taking log to the base 499/500 on both sides (using python) :
>>> math.log(.5,499/500.0)

n = 347 attempts

double verify :
>>> math.pow(499/500.0,346.22690104949118)