Rejection Sampling is a randomized technique used to generate samples from a desired probability distribution by repeatedly drawing candidates from a simpler distribution and accepting or rejecting them based on a condition. In coding interviews, this concept often appears in problems that require generating uniform randomness from biased sources or filtering random outputs to match strict constraints.
Instead of directly computing a complex distribution, rejection sampling relies on repeated trials until a valid sample appears. This makes it a practical approach in algorithm design when direct sampling is difficult or inefficient. Many interview questions test whether you can use randomness effectively while ensuring the final result remains unbiased.
Rejection sampling problems are closely connected with concepts from Probability and Statistics and Randomized algorithms. Candidates are often asked to transform one random generator into another or simulate fair outcomes from biased inputs. Some problems also involve implementing logic that mimics real-world processes using Simulation.
Common patterns you may encounter include:
Mastering rejection sampling helps you handle probability-based interview questions and strengthens your understanding of randomized algorithm design.
Helps analyze acceptance probabilities and expected runtime of repeated sampling.
Rejection sampling is a core technique used in randomized algorithms to generate fair outcomes.
Many rejection sampling solutions rely on simulating processes and filtering invalid outcomes.
Provides the mathematical foundation for understanding distributions, probabilities, and unbiased sampling.
| Status | Title | Video | Leetcode | Solve | Difficulty | Companies | Topics |
|---|---|---|---|---|---|---|---|
| 470. Implement Rand10() Using Rand7() | Solve | Medium | Amazon+2 | ||||
| 478. Generate Random Point in a Circle | Solve | Medium | Leap Motion |
Frequently appear alongside Rejection Sampling.
Common questions about Rejection Sampling.
Rejection sampling is a technique where random samples are generated from a simple distribution and rejected if they do not meet specific conditions. The process repeats until a valid sample is accepted, ensuring the final distribution is correct.
The expected time complexity depends on the acceptance probability. If a sample is accepted with probability p, the expected number of trials is roughly 1/p.
Practicing a few well-designed problems is usually enough to understand the pattern. Focus on questions that convert biased randomness into uniform outputs and analyze their probability reasoning.
Interviewers use rejection sampling problems to test understanding of randomness and probability. These questions evaluate whether you can produce unbiased results using limited or imperfect random generators.
Rejection sampling filters randomly generated candidates until a valid one appears, while reservoir sampling selects items uniformly from a stream of unknown size. They solve different types of randomized problems.