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.
Quick Answer: 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 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, ...`.