Simulate Uniform(0,1) from random bits
Company: Google
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
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.
Overview: 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.
Read the full Google Data Scientist interview experience this question came from
Assume there is a function `rand_bit()` that returns `0` or `1` with equal probability, independently on each call. A standard way to approximate a random number uniformly distributed on `[0, 1)` is to use the generated bits as the binary digits after the decimal point.
If the first `n` calls return bits `b1, b2, ..., bn`, define
`X = b1/2 + b2/4 + b3/8 + ... + bn/2^n`
In this coding version, the bit sequence is given to you directly as a list `bits`, and you must return the corresponding value `X`.
This matches the simple algorithm for the original randomized problem: call `rand_bit()` exactly `n` times and interpret the results as a binary fraction. Using `n` bits produces one of `2^n` equally likely values in `[0,1)`. The approximation has resolution `1/2^n`, and the truncation error compared with the full infinite binary expansion is always less than `1/2^n`.
Constraints
- `0 <= len(bits) <= 30`
- Each `bits[i]` is either `0` or `1`
- The simple randomized algorithm uses exactly `n` calls to `rand_bit()` for `n` output bits
Examples
Input: ([],)
Expected Output: 0.0
Explanation: With no bits, the binary fraction has no nonzero terms, so the value is 0.0.
Input: ([1],)
Expected Output: 0.5
Explanation: The fraction is `1/2 = 0.5`.
Hints
- Think of the list as the binary digits after the point: `[1, 0, 1]` means `0.101` in base 2.
- You can build an integer from the bits and divide by `2^n`, or accumulate the value with weights `1/2, 1/4, 1/8, ...`.