How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Google.

What role is this question designed for?

This question is commonly asked for Data Scientist candidates at Google during technical interviews.

Simulate Uniform(0,1) from random bits

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

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

Input: ([1, 0, 1],)

Expected Output: 0.625

Explanation: This is `1/2 + 0/4 + 1/8 = 0.625`.

Input: ([0, 1, 1, 0],)

Expected Output: 0.375

Explanation: This is `0/2 + 1/4 + 1/8 + 0/16 = 0.375`.

Input: ([1, 1, 1, 1],)

Expected Output: 0.9375

Explanation: This is `1/2 + 1/4 + 1/8 + 1/16 = 15/16 = 0.9375`.

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, ...`.

Quick Overview