710. Random Pick with Blacklist

Question

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.

Thinking:

  • Method 1: TLE / MLE 
      class Solution {
      private Set<Integer> black;
      private int[] valid;
      private Random random;
      private int N;
      private int size;
      public Solution(int N, int[] blacklist) {
          this.black = new HashSet<>();
          for(int b : blacklist) this.black.add(b);
          this.valid = new int[N - blacklist.length];
          int count = 0;
          for(int i = 0; i < N; i++){
              if(this.black.contains(i)) continue;
              this.valid[count++] = i;
          }
          this.size = this.valid.length;
          this.random = new Random();
          this.N = N;
      }
        
      public int pick() {
          return this.valid[Math.abs(random.nextInt()) % size];
      }
  }
    
  /**
   * Your Solution object will be instantiated and called as such:
   * Solution obj = new Solution(N, blacklist);
   * int param_1 = obj.pick();
   */
  • Method 2: reorder HashMap
    1. We first create a hashtable for saving all blacklist.
    2. we insert all the valid numbers to previous blacklist positions.

    3. Use random to get a random value, if that value is in the map, we return the value, otherwise, we just return the value directly. ```Java class Solution { private Map<Integer, Integer> map; private Random random; private int M; public Solution(int N, int[] blacklist) { this.random = new Random(); this.map = new HashMap<>(); for(int b : blacklist){ map.put(b, -1); } this.M = N - blacklist.length; N–; for(int b : blacklist){ if(b < M){ while(map.containsKey(N)) N–; map.put(b, N–); } } }

      public int pick() { int next = random.nextInt(M); return map.containsKey(next) ? map.get(next): next; } }

    /**

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