Katkat
Back

Generate uniform 0–6 from biased coin

LinkedInMachine Learning Engineer · Onsite
MediumMachine Learning EngineerOnsiteCoding & Algorithms

Last updated

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

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).