Design a class Solution that picks a uniformly random integer from 0 to n - 1 that is not in a blacklist.
new Solution(n, blacklist, rng): blacklist holds distinct integers in [0, n), and at least one number is allowed. rng returns numbers in [0, 1)pick() returns an allowed number, each allowed number equally likelyn can be as large as 10 ** 9 while the blacklist is small, so setup must cost O(blacklist size) and never loop over 0 .. n - 1- Make at most one draw from
rng per pick. Redrawing until the draw is allowed is not enough