Quick Overview

This question evaluates understanding of randomized algorithms, probability theory, and techniques for extracting uniform randomness from a biased source.

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.

You are given access to a biased coin through a function `getRandom01Biased()` that returns `0` with probability `p` and `1` with probability `1-p`, where `p` is unknown and can be any value in `(0,1)`. Design an algorithm `getRandom06Uniform()` that returns each integer in `[0, 6]` with exactly equal probability `1/7`, no matter what `p` is. For this coding version, the random coin is modeled deterministically by a list `stream` of 0s and 1s. Read the list from left to right as consecutive outputs of `getRandom01Biased()`. Your task is to simulate the correct exact algorithm: 1. Build an unbiased random bit using pairs of biased outputs: - `01 -> 0` - `10 -> 1` - `00` and `11` are discarded 2. Use three unbiased bits to form a number in `[0, 7]`. 3. If the number is `7`, reject it and repeat. 4. Return the first accepted value in `[0, 6]`. This algorithm is correct for every `p` in `(0,1)`. In the real probabilistic setting, each unbiased bit needs `1 / (p(1-p))` biased calls in expectation, and the full `[0,6]` generator needs `24 / (7p(1-p))` biased calls on average.

Constraints

  • 1 <= len(stream) <= 100000
  • Each element of `stream` is either 0 or 1
  • The provided stream is guaranteed to contain enough values to generate one final answer
  • Your logic must not depend on the value of `p`

Examples

Input: [0,1,0,1,1,0]

Expected Output: 1

Explanation: Pairs are `01 -> 0`, `01 -> 0`, `10 -> 1`, so the unbiased bits are `001`, which is 1.

Input: [1,0,1,0,0,1]

Expected Output: 6

Explanation: Pairs are `10 -> 1`, `10 -> 1`, `01 -> 0`, so the unbiased bits are `110`, which is 6.

Hints

  1. A pair of outcomes `01` and `10` have the same probability, even when the coin is biased.
  2. Once you can generate fair bits, think about creating a value in `[0,7]` and using rejection sampling.

Loading coding console...