Random Pick with Blacklist

Hard

Asked by:

22 views

Topics:

Arrays

You are given an integer n and an array of unique integers blacklist. Design an algorithm to pick a random integer in the range [0, n - 1] that is not in blacklist. Any integer that is in the mentioned range and not in blacklist should be equally likely to be returned.

Optimize your algorithm such that it minimizes the number of calls to the built-in random function of your language.

Implement the Solution class:

Solution(int n, int[] blacklist) Initializes the object with the integer n and the blacklisted integers blacklist.
int pick() Returns a random integer in the range [0, n - 1] and not in blacklist.

Example 1:

Input
["Solution", "pick", "pick", "pick", "pick", "pick", "pick", "pick"]
[[7, [2, 3, 5]], [], [], [], [], [], [], []]
Output
[null, 0, 4, 1, 6, 1, 0, 4]

Explanation
Solution solution = new Solution(7, [2, 3, 5]);
solution.pick(); // return 0, any integer from [0,1,4,6] should be ok. Note that for every call of pick,
                 // 0, 1, 4, and 6 must be equally likely to be returned (i.e., with probability 1/4).
solution.pick(); // return 4
solution.pick(); // return 1
solution.pick(); // return 6
solution.pick(); // return 1
solution.pick(); // return 0
solution.pick(); // return 4

Constraints:

1 <= n <= 10⁹
0 <= blacklist.length <= min(10⁵, n - 1)
0 <= blacklist[i] < n
All the values of blacklist are unique.
At most 2 * 10⁴ calls will be made to pick.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for `n` and the numbers in the blacklist `blacklist`?
Can the `blacklist` array be empty?
Is the input `n` always greater than the number of elements in the `blacklist`?
If all numbers in the range [0, n-1] are blacklisted, what value should `pick()` return?
How is the `pick()` method going to be called - is it a one-time call or will it be called multiple times, and if so, what is the approximate number of calls to `pick()`?

Brute Force Solution

Approach

We need to pick a random number from a range, but certain numbers are forbidden. The brute force method is like randomly guessing numbers until we find one that's allowed. We keep trying until we succeed, ignoring the forbidden ones.

Here's how the algorithm would work step-by-step:

First, consider all the numbers within the specified range as potentially valid.
Generate a random number within the full range of possible numbers.
Check if the randomly generated number is on the blacklist (the list of forbidden numbers).
If the randomly generated number IS on the blacklist, then it's not a valid choice, so we simply discard it and repeat the process from step two: Generate a new random number.
If the randomly generated number is NOT on the blacklist, then it's a valid choice, and we can return it as the answer.

Code Implementation

import random

def pick_with_blacklist_brute_force(upper_bound, blacklist):
    while True:
        # Generate a random integer within the specified range.
        random_number = random.randint(0, upper_bound)

        # Check if the generated number is in the blacklist.
        if random_number in blacklist:

            # Discard the number and try again.
            continue

        # If the number is not blacklisted, return it.
        return random_number

Big(O) Analysis

Time Complexity

O(b) – The provided algorithm repeatedly generates random numbers and checks if they are in the blacklist. In the worst-case scenario, the algorithm might need to generate and check a large number of random numbers before finding one that is not blacklisted. The time complexity is directly proportional to the number of blacklist entries (b) because in the worst case, we might have to iterate through the entire blacklist to determine if the randomly generated number is present. Thus, the time complexity is O(b), where b is the size of the blacklist.

Space Complexity

O(1) – The provided algorithm, as described, does not utilize any auxiliary data structures. It only generates random numbers and checks them against the blacklist, discarding invalid choices. Therefore, the space complexity is constant as it does not depend on the size of the blacklist or the range of numbers. No extra lists, maps, or recursive calls are involved.

Optimal Solution

Approach

The goal is to pick a random number from a range, but some numbers are off-limits. Instead of repeatedly guessing and checking, we'll remap the valid numbers to a smaller, more manageable range, and then pick randomly from that smaller range.

Here's how the algorithm would work step-by-step:

First, figure out how many numbers are actually allowed.
Create a way to remember the numbers we're not allowed to pick.
If an allowed number is one of the blocked ones, map that allowed number to a valid number from the end.
Pick a random number from 0 up to the total number of allowed numbers.
If our randomly chosen number isn't one of the remapped ones, just return it directly. Otherwise return the remapped number.

Code Implementation

import random

class Solution:

    def __init__(self, upper_bound: int, blacklist: list[int]):
        self.valid_number_count = upper_bound - len(blacklist)
        self.number_map = {}
        self.upper_bound = upper_bound
        self.blacklist = blacklist
        
        # Add blacklist numbers to set for quick lookup.
        self.blacklist_set = set(blacklist)

        # Map larger blacklisted numbers to valid range.
        for blacklisted_number in blacklist:
            if blacklisted_number < self.valid_number_count:
                while upper_bound - 1 in self.blacklist_set:
                    upper_bound -= 1
                self.number_map[blacklisted_number] = upper_bound - 1
                upper_bound -= 1

    def pick(self) -> int:
        # Generate random number within valid range.
        random_index = random.randint(0, self.valid_number_count - 1)

        # If the random number has been remapped, return its mapping.
        if random_index in self.number_map:
            return self.number_map[random_index]

        # Otherwise return the number directly.
        return random_index

Big(O) Analysis

Time Complexity

O(b) – The first step of figuring out how many numbers are allowed takes O(1) time, since it is just a subtraction. Creating a way to remember the numbers we're not allowed to pick (the blacklist) requires iterating through the blacklist, where b is the number of blacklisted integers. Mapping the allowed numbers to valid numbers involves iterating through the blacklist again in the worst-case scenario where all blacklisted numbers are in the lower range. Picking a random number and returning it or its remapped value takes O(1) time. Thus, the dominant operation is iterating through the blacklist, resulting in O(b) complexity.

Space Complexity

O(B) – The primary auxiliary space usage comes from storing the blacklist numbers in a data structure for quick lookups, which is represented in the plain English explanation as "a way to remember the numbers we're not allowed to pick". This data structure, typically implemented as a hash map or a set, stores information for each blacklisted number. Thus, the space required scales linearly with the number of blacklisted numbers, denoted as B. The remapping from blocked to valid numbers is also stored, potentially within this same data structure. Therefore, the space complexity is O(B), where B is the number of blacklisted numbers.

Edge Cases

Case	How to Handle
n is equal to blacklist size	Return an empty list because all possible numbers are blacklisted.
Blacklist is empty	The uniform random number generation is used to generate the number from 0 to n-1 without any checks.
Blacklist contains duplicate numbers	The algorithm overwrites values in the map, effectively only considering the last occurrence of each duplicate in the blacklist.
Blacklist contains numbers outside the range [0, n)	Filter out these numbers, as they don't affect the valid pick range and could cause out of bounds errors.
n is a large number (e.g., close to Integer.MAX_VALUE)	Ensure that the data structures (e.g., HashMap) used to store the mapping can handle a large number of entries without exceeding memory limits or causing performance issues; use long if necessary.
All numbers from 0 to n-1 except one are blacklisted.	The algorithm should still correctly return the single non-blacklisted number.
The random number generator produces the same sequence of numbers repeatedly.	This is a property of the random number generator itself and should be addressed with a good random number generator seed; the algorithm itself should function correctly, just perhaps not randomly.
Integer overflow when calculating n - blacklist.length	Use long data type for calculations involving n and blacklist length to prevent overflow.

n is equal to blacklist size

How to Handle:

Return an empty list because all possible numbers are blacklisted.

Blacklist is empty

How to Handle:

The uniform random number generation is used to generate the number from 0 to n-1 without any checks.

Blacklist contains duplicate numbers

How to Handle:

The algorithm overwrites values in the map, effectively only considering the last occurrence of each duplicate in the blacklist.

Blacklist contains numbers outside the range [0, n)

How to Handle:

Filter out these numbers, as they don't affect the valid pick range and could cause out of bounds errors.

n is a large number (e.g., close to Integer.MAX_VALUE)

How to Handle:

Ensure that the data structures (e.g., HashMap) used to store the mapping can handle a large number of entries without exceeding memory limits or causing performance issues; use long if necessary.

All numbers from 0 to n-1 except one are blacklisted.

How to Handle:

The algorithm should still correctly return the single non-blacklisted number.

The random number generator produces the same sequence of numbers repeatedly.

How to Handle:

This is a property of the random number generator itself and should be addressed with a good random number generator seed; the algorithm itself should function correctly, just perhaps not randomly.

Integer overflow when calculating n - blacklist.length

How to Handle:

Use long data type for calculations involving n and blacklist length to prevent overflow.