Random Pick with Blacklist

Given a blacklist B containing unique integers from [0, N), write a function to return a uniform random integer from [0, N) which is NOT in B.

Optimize it such that it minimizes the call to system’s Math.random().

Note:

  1. 1 <= N <= 1000000000
  2. 0 <= B.length < min(100000, N)
  3. [0, N) does NOT include N. See interval notation.
Example 1:

Input: 
["Solution","pick","pick","pick"]
[[1,[]],[],[],[]]
Output: [null,0,0,0]
Example 2:

Input: 
["Solution","pick","pick","pick"]
[[2,[]],[],[],[]]
Output: [null,1,1,1]
Example 3:

Input: 
["Solution","pick","pick","pick"]
[[3,[1]],[],[],[]]
Output: [null,0,0,2]
Example 4:

Input: 
["Solution","pick","pick","pick"]
[[4,[2]],[],[],[]]
Output: [null,1,3,1]
Explanation of Input Syntax:

The input is two lists: the subroutines called and their arguments. Solution's constructor has two arguments, N and the blacklist B. pick has no arguments. Arguments are always wrapped with a list, even if there aren't any.

Solution:

Suppose N=10, blacklist=[3, 5, 8, 9], re-map 3 and 5 to 7 and 6.
class Solution {
    Map<Integer, Integer> map = new HashMap();
    int m;
    Random r;

    public Solution(int N, int[] blacklist) {
        map = new HashMap();
        r = new Random();
        m = N - blacklist.length;
        for (int val : blacklist) {
            map.put(val, -1);
        }
        N --;
        for (int val : blacklist) {
            if (val < m) {
                while (map.containsKey(N)) {
                    N --;       
                }
                map.put(val, N);
                N --;
            }
        }
        // System.out.println(map);
    }
    
    public int pick() {
        int next = r.nextInt(m);
        if (map.containsKey(next)) {
            return map.get(next);
        }
        return next;
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(N, blacklist);
 * int param_1 = obj.pick();
 */