Rejection Sampling is a randomized algorithm technique used to generate samples from a target distribution by repeatedly generating candidate values and rejecting those that do not meet certain criteria. In coding interviews and algorithmic problem solving, this technique appears when you must generate uniformly random results while filtering out invalid states. Instead of computing complicated probabilities directly, you sample repeatedly until a valid result appears.
In many interview questions, Rejection Sampling is used to build one random distribution from another. For example, you may be given a function that produces random values in one range and asked to simulate randomness in a different range. The key idea is simple: generate a candidate value, check if it falls within the acceptable region, and reject it if it does not. Although it may involve repeated attempts, the expected runtime remains efficient when the acceptance probability is reasonably high.
This technique often appears in problems involving Randomized algorithms, probability modeling, and simulation tasks. Understanding the math behind acceptance probabilities can also require concepts from Probability and Statistics and basic Math. Some related techniques include Reservoir Sampling for sampling from streams and Simulation when modeling random processes.
Common patterns in Rejection Sampling problems include:
You should consider using Rejection Sampling when the direct generation of the desired distribution is difficult but generating candidates is easy. By mastering this technique, you will be able to solve a variety of interview questions that combine randomness, probability reasoning, and algorithmic design.
Mathematical reasoning helps compute valid ranges, probability bounds, and expected number of iterations in rejection sampling.
Rejection sampling is a core randomized technique where algorithm correctness depends on probabilistic behavior and uniform sampling.
Many rejection sampling problems are implemented as simulations that repeatedly generate and validate random candidates.
Another important sampling technique; learning it alongside rejection sampling helps understand different strategies for random selection problems.
Provides the foundation for understanding distributions, expected value, and acceptance probability used in rejection sampling algorithms.
Try broadening your search or exploring a different topic. There are thousands of problems waiting for you.
Frequently appear alongside Rejection Sampling.
Common questions about Rejection Sampling.
Rejection sampling appears occasionally in FAANG and top tech interviews, usually in questions involving random number generation or probability simulations. While not as common as arrays or dynamic programming, it demonstrates strong understanding of randomized algorithms.
Common patterns include generating uniform random numbers in a new range, rejecting out-of-bound samples, mapping multi-dimensional random spaces to valid outputs, and minimizing rejection probability. Many problems also combine math with randomized algorithm design.
Start by understanding the mathematical idea of accepting or rejecting samples to maintain a uniform distribution. Then practice classic problems such as converting rand7() to rand10(). Visualizing the valid sampling region often helps clarify why the method works.
Rejection sampling usually has O(1) expected time complexity because the expected number of trials is bounded by the acceptance probability. However, the worst case can be unbounded if the rejection rate is extremely high, which is why efficient mapping strategies are important.
The best problems involve generating one random distribution from another, such as implementing rand10() using rand7(). These questions test probability reasoning, algorithm design, and understanding of uniform distributions. Practicing 2–5 well-known rejection sampling problems is usually enough to master the core technique.
Most candidates can grasp the pattern after solving about 3–6 problems. The key is understanding why rejected samples maintain uniform probability rather than memorizing solutions. Focus on problems that transform one random generator into another.
