Given n and a list of blacklisted integers in [0, n), pick() returns a uniformly random integer in [0, n) that isn't blacklisted. n can be up to a billion, and the blacklist up to 100,000 values. Minimize calls to the random number generator.
Before you code
There are k = n − len(blacklist) allowed values. If you draw uniformly from 0 to k − 1, which draws land on blacklisted values, and where could they be sent instead?
Hints
- Draw r uniformly from [0, k).
- Some values below k are blacklisted, and exactly as many values at or above k are allowed. Pair them up.
- Store the pairing in a hash map from each blacklisted value below k to an allowed value at or above k. pick returns map.get(r, r): one random call and one expected O(1) lookup.
Production & complexity notes
When solving Random pick with blacklist on LeetCode (hard), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Expected cost of hashing to reinforce the underlying pattern.
What it practices
Using expected O(1) hash lookups to make sampling exact, from Expected cost of hashing.