LinkedIn·Machine Learning Engineer·Technical Phone Screen·Intermediate

Intermediate

May 2026

Summary

LinkedIn ML engineer interview with a classic probability/coding puzzle. Nothing too wild but it made me think harder than I expected.

Questions Asked (1)

You're given a function that flips a biased coin (unknown probability of heads). Write a new function that uses it to produce heads or tails with exactly 50/50 probability.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

I knew the Von Neumann trick from somewhere in the back of my head but couldn't remember the name, so I just re-derived it.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use the von Neumann trick: flip the biased coin twice and map HT to heads and TH to tails, ignoring HH and TT. This yields exactly 50/50 because P(HT) = P(TH) = p(1-p).

Pro tip: Mention that the expected number of flips is 1/(2p(1-p)), which is minimized when p=0.5 and grows as p approaches 0 or 1; this shows awareness of efficiency and trade-offs.

1. Understand the problem

Recognize that the biased coin has unknown probability p of heads, and we need a fair 50/50 outcome using only this coin.

2. Identify symmetry

Notice that sequences HT and TH have equal probability p(1-p), so they can be used to produce fair outcomes.

3. Design the algorithm

Flip the coin twice; if HT, return heads; if TH, return tails; if HH or TT, discard and repeat.

4. Prove correctness

Show that conditional on not discarding, P(HT | HT or TH) = 1/2, ensuring exact fairness.

5. Analyze efficiency

Compute expected number of flips as 1/(2p(1-p)), discuss best and worst cases, and mention potential optimizations.

Key Points to Mention

Von Neumann's algorithm for generating fair coin flips from a biased coin.
Probability calculation: P(HT) = P(TH) = p(1-p).
Conditional probability argument for fairness.
Expected number of flips: 1/(2p(1-p)), which is at least 2 and can be large if p is near 0 or 1.
Handling of discarded outcomes (HH and TT) by repeating the process.
Potential optimizations or alternative approaches for efficiency (e.g., using more flips at once).

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