One of the questions that I was asked on a recent onsite interview with was a probability question. It went as follows:

Given an unfair coin which flips as heads with probability $0<p<1$ as a source of randomness, come up with an algorithm that flips a fair coin, with probability of flipping a head exactly $0.5$ .

The trick here is to consider a pair of coin flips, with the set of possible results being $\{HH,HT,TH,TT\}$ . Then both $HT$ and $TH$ have probability of exactly $p(1-p)$ which means we can use these two events to simulate a fair coin flip.

And of course, as you would suspect, this is a relatively well-known problem. The process of flipping coins with probability $p$ for heads is mathematically referred to as a Bernoulli process, with the key part being that the unfairness is consistent, that is $p$ does not change between the flips. Using an unfair Bernoulli process to generate a fair one is an example of randomness extraction. You can read up on both of these topics on Wikipedia. The particular extractor discussed above, which is one solution to the problem, is called the von Neumann extractor. It's implemented here in Python using two generators. See the post on iterators and generators for more implementation details.

import random


def bernoulli_process(p):
    if p > 1.0 or p < 0.0:
        raise ValueError("p should be between 0.0 and 1.0.")
    while True:
        yield random.random() > p

def von_neumann_extractor(process):
    while True:
        x, y = process.next(), process.next()
        if x != y:
            yield x

For a full discussion of this problem, and the best possible solution, see the article by Michael Mitzenmacher.