← LinkedIn Interview InsightsMachine Learning Engineer

LinkedIn·Machine Learning Engineer·Technical Phone Screen·Senior

Senior
May 2026

Summary

LinkedIn ML engineer interview with a probability/randomness coding problem that sounds deceptively simple until you start thinking about the math. The question had real depth to it and the follow-up on efficiency caught me a bit flat-footed.

Questions Asked (1)

Q1

You have a biased coin function that returns 0 with probability p and 1 with probability (1-p), where p is unknown. Implement a function that returns a uniformly random integer from 0 to 6 inclusive. Walk through your approach, analyze the expected number of calls to the biased function, and explain how you'd minimize it.

Algorithms & Data StructuresTechnical Trade-offs
Author's notes

The core insight is von Neumann's trick: call the biased function twice, and if you get (0,1) or (1,0) you have an unbiased bit since both have probability p*(1-p).

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by explaining how to use the biased coin to generate unbiased random bits via the von Neumann extractor, then combine bits to generate uniform integers from 0 to 6 using rejection sampling. Analyze the expected number of coin flips and discuss optimizations like recycling rejected randomness or using arithmetic coding to reduce waste.

Pro tip: Emphasize that while the von Neumann extractor is simple, more efficient methods like generating a random real number in [0,1) and multiplying by 7 can reduce the expected number of flips, showing depth in probabilistic algorithm design.

1. Generate unbiased bits

Explain the von Neumann extractor: flip the biased coin twice; if outcomes differ, output the first bit (0 for 01, 1 for 10); if same, discard and repeat. This yields fair bits with expected 4 flips per bit (since p(1-p) ≤ 1/4).

2. Combine bits for uniform integer

Use rejection sampling: generate 3 unbiased bits to form a number 0-7; if the number is 0-6, return it; if 7, reject and retry. Expected number of unbiased bits per success is 8/7 ≈ 1.143.

3. Compute expected coin flips

Multiply expected flips per unbiased bit (4) by expected bits per success (8/7) to get 32/7 ≈ 4.57 flips per integer. Note this is an upper bound; actual expected flips depend on p, but worst-case is when p=0.5.

4. Discuss optimizations

Mention recycling rejected randomness: when 7 is generated, use it to produce additional bits or combine with future bits to reduce waste. Alternatively, use arithmetic coding or generate a random fraction in [0,1) by flipping until first 1, then multiply by 7 and take floor, which can be more efficient for some p.

5. Analyze trade-offs and minimize calls

Compare methods: von Neumann + rejection is simple but may waste flips; recycling or arithmetic coding reduces expected flips but adds complexity. For minimizing calls, consider generating a random integer directly using a tree-based approach that adapts to p, or use the fact that the entropy of the coin is H(p) = -p log p - (1-p) log(1-p) to bound efficiency.

Key Points to Mention

  • Von Neumann extractor for unbiased bits from biased coin
  • Rejection sampling to map bits to uniform integer 0-6
  • Expected number of coin flips: 4 flips per unbiased bit, 8/7 bits per integer, total 32/7 ≈ 4.57 flips (worst-case p=0.5)
  • Optimization: recycling rejected randomness (e.g., when 7 is generated)
  • Alternative: arithmetic coding or generating random fraction in [0,1) to reduce waste
  • Trade-off between simplicity and efficiency; entropy bound H(p) limits minimum expected flips

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