Uniform 0-6 from an Unknown Biased Bit
Learn this problem
LinkedInFULLTIMEPHONE SCREENProblem statement
You receive two deterministic tapes that represent successive calls to random-bit generators.
biasedBitscomes from one unknown but fixed source biasq, where0 < q < 1: 0 has probabilityq, and 1 has probability1-q.uniformBitscomes from a fair bit generator.
First, consume biasedBits in consecutive pairs. Discard equal pairs; map [0,1] to fair bit 0 and [1,0] to fair bit 1. Use fair bits most-significant first in groups of three, rejecting 7, and produce a uniform value in [0,6].
For the follow-up, let the target ratio p = pNumerator / pDenominator. Consume the minimum-width groups from uniformBits, reject integers outside [0,pDenominator-1], and return 0 when the accepted integer is less than pNumerator, otherwise 1.
Return [uniformValue, biasedValue]. Each tape is guaranteed to contain enough bits.
Function
generateRandomOutputs(biasedBits: int[], uniformBits: int[], pNumerator: int, pDenominator: int) → int[]Examples
Example 1
biasedBits = [0,1,1,0,0,1]uniformBits = [0,1]pNumerator = 1pDenominator = 4return = [2,1]The biased pairs yield fair bits 0,1,0, which form 2. Fair bits 0,1 form integer 1. For p=1/4, only integer 0 maps to 0, so the follow-up output is 1.
Example 2
biasedBits = [1,0,1,0,1,0,0,1,1,0,0,1]uniformBits = [1,1,1,0]pNumerator = 2pDenominator = 3return = [2,1]The first three extracted bits form 7 and are rejected; the next three form 2. The fair-bit candidate 3 is rejected for denominator 3, then candidate 2 maps to 1.
Constraints
biasedBits.lengthanduniformBits.lengthare between 0 and 100000.- Every tape element is 0 or 1, and each tape is long enough for its required accepted sample.
1 <= pDenominator <= 1000 <= pNumerator <= pDenominator