Simulate Uniform(0,1) from random bits
GoogleData Scientist · Onsite
Last updated
This Coding & Algorithms question for a Data Scientist evaluates understanding of randomized algorithms, bit-level representation of real numbers, and probabilistic error and time-complexity analysis, situated at an algorithmic and mathematical abstraction level that requires both conceptual design and quantitative reasoning.
Assume you have access to a function rand_bit() that returns 0 or 1 with equal probability and independent across calls.
How would you generate a random number approximately uniformly distributed on the interval [0, 1)?
Discuss:
- A simple algorithm.
- How the approximation error depends on the number of bits.
- Time complexity in terms of number of
rand_bit()calls.
Solution walkthrough is for members
Get the full walkthrough with reference code and complexity analysis, plus Kitty Coach at 300 messages a day. Hints, the code runner and community answers stay free.