#710

Random Pick with Blacklist

master · 1865 · lc hard +32 · premium · 34.6% accepted · 896 likes · top 12%

Description

Given integers n and a list of unique blacklisted values blacklist, design a data structure that uniformly samples from all integers in [0, n - 1] that are not blacklisted, using as few calls to the random function as possible.

Implement the Solution class:

- Solution(int n, int[] blacklist) Constructs the object with range n and the forbidden values in blacklist.

- int pick() Returns a uniformly random integer from [0, n - 1] that does not appear 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]

Example 2:

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

Code

class Solution:

    def __init__(self, n: int, blacklist: List[int]):
        

    def pick(self) -> int:
        


# Your Solution object will be instantiated and called as such:
# obj = Solution(n, blacklist)
# param_1 = obj.pick()

class Solution:

    def __init__(self, n: int, blacklist: List[int]):
        

    def pick(self) -> int:
        


# Your Solution object will be instantiated and called as such:
# obj = Solution(n, blacklist)
# param_1 = obj.pick()