Rejection Sampling is a randomized algorithm technique used to generate uniform random values from a restricted set by repeatedly sampling and discarding invalid outcomes. Instead of designing a complex direct distribution, the algorithm samples from a broader range and rejects values that don’t meet the required condition. This approach is widely used in probability simulations, randomized algorithms, and certain coding interview problems.
In coding interviews, rejection sampling typically appears in problems involving random number generation under constraints. For example, generating a uniform random number in a specific range using another random generator, or ensuring each outcome has equal probability. Understanding this technique requires a solid grasp of probability, expected runtime, and randomness.
Rejection sampling problems often combine concepts from multiple DSA areas. You'll frequently see it alongside topics like Probability and Statistics, Randomized algorithms, and mathematical reasoning from Math. Some advanced interview questions also compare rejection sampling with techniques like Reservoir Sampling for handling random selection in streaming data.
Common techniques used in rejection sampling problems include:
You should consider rejection sampling when a direct mapping to the desired distribution is difficult but sampling from a broader uniform range is easy. In interviews, these problems test both probabilistic thinking and algorithm design. Practicing rejection sampling problems helps you build intuition for randomness, probability distributions, and efficient simulation strategies—skills that appear in advanced algorithm questions and system simulations.
Provides the mathematical foundation for probability ranges, modular arithmetic, and mapping sampled values to valid outputs.
Rejection sampling is a core randomized technique used in algorithms that rely on probabilistic behavior rather than deterministic logic.
Many rejection sampling problems simulate processes with randomness, making simulation skills useful for implementing and testing solutions.
Helps you reason about uniform distributions, expected runtime, and why rejecting samples still produces unbiased results.
| Status | Title | Solution | Practice | Difficulty | Companies | Topics |
|---|---|---|---|---|---|---|
| 470. Implement Rand10() Using Rand7() | Solution | Solve | Medium | Amazon+2 | ||
| 478. Generate Random Point in a Circle | Solution | Solve | Medium | Leap Motion |
Frequently appear alongside Rejection Sampling.
Common questions about Rejection Sampling.
Rejection sampling is a technique for generating random values from a target distribution by sampling from a larger distribution and rejecting invalid results. The process repeats until a valid value appears. If designed correctly, each valid output remains uniformly distributed.
Rejection sampling appears less frequently than topics like arrays or dynamic programming, but it does show up in randomized algorithm questions at companies like Google and Meta. Interviewers use it to test probability reasoning and algorithm design.
Most candidates only need to solve 2–5 well-designed rejection sampling problems to understand the pattern. Since the technique is specialized, mastering a few representative problems usually covers the interview scenarios.
The expected time complexity depends on the acceptance probability. If the probability of accepting a sample is p, the expected number of iterations is 1/p. In well-designed interview problems, this value is typically small and constant.
Common interview problems involve generating a uniform random number using another random generator, such as implementing rand10() using rand7(). These problems test understanding of probability, expected runtime, and unbiased sampling.
Rejection sampling repeatedly discards invalid random samples until a valid one appears, while reservoir sampling selects k random elements from a stream of unknown size. Both use randomness, but they solve different types of problems.
