Derive uniform RNGs from limited or biased sources
Quick Overview
This question evaluates understanding of random number generation, probability theory, and algorithmic reduction techniques for producing unbiased samples from constrained or biased primitives, along with proof of correctness and expected-cost analysis.
Derive uniform RNGs from limited or biased sources
Company: Snowflake
Role: Data Scientist
Category: Statistics & Math
Difficulty: hard
Interview Round: Technical Screen
You have access to rand5(), which returns an integer in {1,2,3,4,5} uniformly at random.
A) Implement rand7() that returns {1..7} uniformly using only calls to rand5(). Your solution must be correct (unbiased), terminating, and near-optimal in expected number of rand5() calls. Prove uniformity and compute the exact expected number of rand5() calls your construction uses.
B) Generalize: given randM() (uniform over {1..M}), implement randN() (uniform over {1..N}) for arbitrary positive integers M and N. Describe an algorithm that is correct for all M,N, and derive an upper bound on the expected number of randM() calls in terms of M and N. Discuss how you would adapt when N≫M and when M≫N.
C) Biased source: given toss(p) which returns 1 with unknown probability p∈(0,1) and 0 otherwise, construct fair_coin() that returns 0/1 with equal probability, prove correctness, and derive the expected number of tosses as a function of p. Then extend your approach to sample uniformly from {1..K} using only toss(p). Analyze termination and expected complexity.
Overview: This question evaluates understanding of random number generation, probability theory, and algorithmic reduction techniques for producing unbiased samples from constrained or biased primitives, along with proof of correctness and expected-cost analysis.
Derive uniform RNGs from limited or biased sources
Snowflake
hardData ScientistTechnical ScreenStatistics & Math
15
0
Sampling Construction and Analysis: From rand5() to rand7(), General randM()→randN(), and Fairness from a Biased Source
You have access to a uniform primitive randM() that returns an integer in {1, 2, ..., M} and, in Part C, a biased primitive toss(p) that returns 1 with an unknown fixed probability p in (0, 1) and 0 otherwise. Assume independent calls to each supplied primitive. Use only the supplied primitive as the source of randomness in its corresponding part.
Part 1 — A) rand7() from rand5()
Task: Implement
rand7()
that returns a value uniformly from
{1, ..., 7}
using only calls to
rand5()
.
Requirements: unbiased (exact), almost surely terminating, and near-optimal in expected
rand5()
calls. Quantify the comparison with a justified lower bound rather than assuming global optimality.
Deliverables: (i) a correct construction; (ii) a proof of uniformity; (iii) the exact expected number of
rand5()
calls. Analyze one result starting without retained randomness from earlier invocations.
What This Part Should Cover Guidance
Probability
1/7
for each output and exclusive use of the allowed primitive.
A valid termination argument and the exact expected call count.
A stated comparison model and a justified efficiency bound.
Part 2 — B) General randN() from randM()
Task: For arbitrary positive integers
M
and
N
, determine feasibility and construct
randN()
from
randM()
whenever possible.
Requirements: exact correctness and almost-sure termination for feasible pairs. If
N = 1
, return the only possible value. If
M = 1
and
N > 1
, explain why the requested uniform randomness is impossible without another entropy source; report infeasibility instead of promising a sampler.
Deliverables: (i) an algorithm covering the feasible cases and explicit handling of the exception; (ii) an upper bound on expected
randM()
calls in terms of
M
and
N
; (iii) adaptations when
N
is much larger than
M
and when
M
is much larger than
N
.
Specialization: rand10() using rand7()
The supplied rand7() API returns an independent uniform integer from 1 through 7. Implement the parameterless method Solution.rand10() so that every result in 1..10 has probability 1/10. Call no random API other than the supplied rand7(); a language's built-in random API is not allowed.
The test environment calls rand10() a total of n times, with 1 <= n <= 100000. The repeat count n is not an argument to the method. Each invocation returns one integer, not an array. Three calls might return 3, 8, 10; other sequences and repeated values are also valid. Random example outputs are not fixed expected answers.
Derive the expected number of rand7() calls and discuss reducing that number. State whether an efficiency comparison permits retained random state across invocations, and distinguish a proved improvement from a proved optimum. No finite worst-case call limit is specified.
What This Part Should Cover Guidance
The feasibility boundary and exact uniformity for every feasible parameter pair.
Termination and expected primitive-call bounds, including the two size regimes.
The exact parameterless
Solution.rand10()
interface, permitted entropy source, and repeated-call behavior.
Assumptions behind any call-count or optimality claim.
Part 3 — C) Fairness from a Biased Source
Given toss(p) with an unknown fixed p in (0, 1) and independent calls:
Construct
fair_coin()
returning
0
and
1
with probability
1/2
each. Prove correctness and derive the expected number of tosses as a function of
p
.
Extend it to sample uniformly from
{1, ..., K}
for a positive integer
K
, using only
toss(p)
. Analyze termination and expected complexity, including
K = 1
.
What This Part Should Cover Guidance
Exact fairness without knowing
p
, under the stated independence assumption.
Expected toss counts and their behavior as
p
approaches either endpoint.
Uniform range sampling and the single-outcome case.
What a Strong Answer Covers Guidance
All three constructions and the concrete
rand7
-to-
rand10
interface.
Separate arguments for output distribution, almost-sure termination, and expected cost.
Feasibility, numeric representation, and the distinction between per-invocation and amortized efficiency.