How should I practice Uniform Integer from Biased-Coin Flips?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Microsoft onsite interview problems in FastPrep.

Is Uniform Integer from Biased-Coin Flips associated with Microsoft?

FastPrep tags this as a Microsoft onsite interview coding practice problem when the problem catalog has that company and stage context.

Uniform Integer from Biased-Coin Flips

Microsoft● HardNEW GRADONSITE INTERVIEW

Learn

Problem statement

You are given a finite sequence flips produced independently by the same Bernoulli(p) source, where p is unknown and strictly between zero and one. Generate one exactly uniform integer in the inclusive range [a,b].

Consume flips in consecutive pairs. Equal pairs are discarded; [false,true] yields fair bit 0, and [true,false] yields fair bit 1. Use enough fair bits for rejection sampling over the range. The input is guaranteed to contain enough flips to accept a value.

Function

uniformInt(flips: boolean[], a: int, b: int) → int

Examples

Example 1

flips = [false,true,true,false,false,true,true,false]a = 1b = 10return = 6

The unequal pairs yield bits 0,1,0,1, or candidate 5; adding a returns 6.

Example 2

flips = []a = 5b = 5return = 5

A singleton range needs no randomness.

Constraints

1 <= flips.length <= 200000, except a singleton range may use an empty array
-10^9 <= a <= b <= 10^9
b - a + 1 <= 10^9
The supplied flips contain a complete accepted rejection-sampling attempt