LinkedIn·AI Engineer·Technical Phone Screen·Senior

SeniorPrefer not to say

May 2026

Summary

LinkedIn AI Engineer interview with a probability and randomness problem that sounds approachable until you're actually in it. The core challenge was building a fair uniform distribution over 7 values using only a biased coin you know nothing about.

Questions Asked (1)

You have a function that returns 0 with unknown probability p and 1 with probability 1-p. Using only this function, write code that returns each integer from 0 to 6 with equal probability.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

I knew the Von Neumann trick from somewhere in the back of my brain, pairs of calls where 01 maps to 0 and 10 maps to 1 and you just retry on 00 or 11.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use rejection sampling to generate unbiased random bits from the biased function, then combine bits to form a uniform integer in a range that is a multiple of 7, rejecting out-of-range values. This ensures each integer from 0 to 6 has equal probability.

Pro tip: Mention that rejection sampling is efficient because the expected number of calls is constant, and discuss how to optimize by using as many bits as possible per attempt to minimize waste.

1. Generate unbiased random bits

Use the biased function to produce fair bits by calling it twice and mapping (0,1) to 0 and (1,0) to 1, ignoring (0,0) and (1,1).

2. Combine bits to form a number

Collect enough fair bits to represent a range that is a multiple of 7, such as 3 bits (0-7), and interpret them as an integer.

3. Apply rejection sampling

If the generated integer is 7, reject it and repeat the process; otherwise, return the integer (0-6).

4. Analyze efficiency and correctness

Explain that each fair bit requires an expected 2 calls to the biased function, and the rejection probability is 1/8, so the expected number of calls is constant.

5. Discuss potential optimizations

Mention that using more bits per attempt (e.g., 6 bits for 0-63) can reduce the rejection rate, but the simple 3-bit method is sufficient and easy to implement.

Key Points to Mention

Rejection sampling to handle bias and ensure uniformity
Generating fair bits from a biased coin using the von Neumann extractor
Expected number of calls to the biased function is constant (e.g., 24/7 ≈ 3.43 calls per output)
Correctness proof: each integer 0-6 has probability 1/7
Trade-off between simplicity and efficiency (using more bits reduces rejections)
Edge cases: handling infinite loops in theory but probability of termination is 1

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