LinkedIn·Machine Learning Engineer·Technical Phone Screen·Senior

Senior

Apr 2026

Summary

LinkedIn ML engineer phone screen, basically one meaty probability/randomness problem the whole time. The kind of question that sounds like a puzzle but has real depth once you start pulling at it.

Questions Asked (1)

You have a biased coin function that returns 0 with unknown probability p and 1 with probability 1-p, where p can be anything in (0,1). Using only this function, implement another function that returns a uniform random integer from 0 to 6 inclusive. Also discuss the expected number of calls to the biased function.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

My first instinct was to just call the function a bunch of times and map ranges, which is completely wrong because you can't fix bias that way.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use the von Neumann extractor to generate unbiased bits from pairs of biased coin flips, then combine bits to produce a uniform integer from 0 to 6. Discuss the expected number of calls, which is 1/(p(1-p)) per unbiased bit, and thus 3/(p(1-p)) for three bits, but note that rejection sampling can reduce calls.

Pro tip: Mention that the expected number of calls is minimized when p=0.5, but the algorithm works for any p in (0,1). Also, highlight that the method is optimal in terms of entropy extraction.

1. Understand the problem

Recognize that the biased coin produces independent bits with unknown bias, and we need to generate uniform integers 0-6 (7 outcomes) using only these bits.

2. Generate unbiased bits

Use the von Neumann trick: flip the coin twice; if outcomes are (0,1) output 0, if (1,0) output 1, otherwise discard and repeat. This yields a fair bit.

3. Combine bits to get uniform integer

Generate three unbiased bits to form a number from 0 to 7. If the number is 7, reject and retry; otherwise return the number (0-6).

4. Analyze expected calls

Each unbiased bit requires an expected 1/(p(1-p)) pairs of flips, i.e., 2/(p(1-p)) calls. For three bits, expected calls = 6/(p(1-p)). However, rejection of 7 adds a factor of 8/7, so total expected calls = (48/7)/(p(1-p)).

5. Discuss optimizations and trade-offs

Mention that the expected number of calls can be reduced by using more efficient extraction methods (e.g., generating multiple unbiased bits per pair) or by using a different rejection scheme, but the von Neumann method is simple and optimal in terms of entropy.

Key Points to Mention

Von Neumann extractor for generating unbiased bits from biased coin flips.
Rejection sampling to map 3 bits (0-7) to 0-6 by rejecting 7.
Expected number of calls: 2/(p(1-p)) per unbiased bit, leading to 6/(p(1-p)) for three bits, and with rejection, (48/7)/(p(1-p)).
The method works for any p in (0,1) and is optimal in terms of entropy extraction.
Trade-off between simplicity and efficiency: more complex methods can reduce calls but may be harder to implement.
Mention that the expected number of calls is minimized when p=0.5, but the algorithm is robust to any p.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.