Generate uniform 0–6 from biased coin
Company: LinkedIn
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
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).
Quick Answer: This question evaluates understanding of randomized algorithms, probability theory, and techniques for extracting uniform randomness from a biased source.