Generate uniform 0–6 from biased coin

Q: Generate uniform 0–6 from biased coin

This question evaluates understanding of randomized algorithms, probability theory, and techniques for extracting uniform randomness from a biased source.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

You are given a function:

int getRandom01Biased() returns 0 with probability p and 1 with probability 1-p , where p is unknown and may be any value in (0,1) .

Design and implement:

int getRandom06Uniform() that returns an integer in [0,6] with exactly uniform probability 1/7 .

Constraints/notes:

You may call getRandom01Biased() multiple times.
The algorithm must be correct for any p in (0,1) .
Discuss expected number of calls (at least at a high level).

Generate uniform 0–6 from biased coin

Quick Overview

Comments (0)