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

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at LinkedIn during technical interviews.

Generate uniform 0–6 from biased coin | LinkedIn Coding Question

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.

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

Expected Output: 3

Explanation: First three unbiased bits are `111`, which is 7, so they are rejected. The next three unbiased bits are `011`, which is 3.

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

Expected Output: 2

Explanation: Discard `00`, discard `11`, then `01 -> 0`; discard `11`, then `10 -> 1`; discard `00`, discard `00`, then `01 -> 0`. The unbiased bits are `010`, which is 2.

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

Expected Output: 5

Explanation: Discard `11`, then `10 -> 1`; discard `00`, then `01 -> 0`; then `10 -> 1`. The unbiased bits are `101`, which is 5.

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

Expected Output: 0

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

Hints

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

Quick Overview

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