710. Random Pick with Blacklist Hard

1/**
2 * [710] Random Pick with Blacklist
3 *
4 * 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.
5 * Optimize your algorithm such that it minimizes the number of calls to the built-in random function of your language.
6 * Implement the Solution class:
7 * 
8 * 	Solution(int n, int[] blacklist) Initializes the object with the integer n and the blacklisted integers blacklist.
9 * 	int pick() Returns a random integer in the range [0, n - 1] and not in blacklist.
10 * 
11 *  
12 * Example 1:
13 * 
14 * Input
15 * ["Solution", "pick", "pick", "pick", "pick", "pick", "pick", "pick"]
16 * [[7, [2, 3, 5]], [], [], [], [], [], [], []]
17 * Output
18 * [null, 0, 4, 1, 6, 1, 0, 4]
19 * Explanation
20 * Solution solution = new Solution(7, [2, 3, 5]);
21 * solution.pick(); // return 0, any integer from [0,1,4,6] should be ok. Note that for every call of pick,
22 *                  // 0, 1, 4, and 6 must be equally likely to be returned (i.e., with probability 1/4).
23 * solution.pick(); // return 4
24 * solution.pick(); // return 1
25 * solution.pick(); // return 6
26 * solution.pick(); // return 1
27 * solution.pick(); // return 0
28 * solution.pick(); // return 4
29 * 
30 *  
31 * Constraints:
32 * 
33 * 	1 <= n <= 10^9
34 * 	0 <= blacklist.length <= min(10^5, n - 1)
35 * 	0 <= blacklist[i] < n
36 * 	All the values of blacklist are unique.
37 * 	At most 2 * 10^4 calls will be made to pick.
38 * 
39 */
40pub struct Solution {}
41
42// problem: https://leetcode.com/problems/random-pick-with-blacklist/
43// discuss: https://leetcode.com/problems/random-pick-with-blacklist/discuss/?currentPage=1&orderBy=most_votes&query=
44
45// submission codes start here
46
47struct Solution {
48        vec![]
49    }
50
51
52/** 
53 * `&self` means the method takes an immutable reference.
54 * If you need a mutable reference, change it to `&mut self` instead.
55 */
56impl Solution {
57
58    fn new(n: i32, blacklist: Vec<i32>) -> Self {
59        
60    }
61    
62    fn pick(&self) -> i32 {
63        
64    }
65}
66
67/**
68 * Your Solution object will be instantiated and called as such:
69 * let obj = Solution::new(n, blacklist);
70 * let ret_1: i32 = obj.pick();
71 */
72
73// submission codes end
74
75#[cfg(test)]
76mod tests {
77    use super::*;
78
79    #[test]
80    fn test_710() {
81    }
82}
83