This page explains Java solution to problem `Random Pick with Blacklist`

using `HashMap`

data structure.

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().

Input:

["Solution","pick","pick","pick"]

[[1,[]],[],[],[]]Output: [null,0,0,0]

Input:

["Solution","pick","pick","pick"]

[[2,[]],[],[],[]]Output: [null,1,1,1]

Input:

["Solution","pick","pick","pick"]

[[4,[2]],[],[],[]]Output: [null,1,3,1]

```
package com.vc.hard;
import java.util.*;
class RandomPickWithBlacklist {
/**
Idea is to shift the whitelisted number up and
take the random index from 0 to whitelisted.length
For e.g. N = 6
blacklist = {2, 3, 4}
1, 2, 3, 4, 5, 6
w b b b w w
Only 3 whitelisted,
so swap 2 with 5 & swap 3 with 6
Which make the arr
1, 5, 6, 4, 2, 3
w w w b b b
And then take random number from 0 - whitelisted.length
*/
private Random random = new Random();
private HashMap<Integer, Integer> blacklistedMapping = new HashMap<>();
private int blen = 0;
private int wlen = 0;
public RandomPickWithBlacklist(int N, int[] blacklist) {
this.blen = blacklist.length;
this.wlen = N - blen;
HashSet<Integer> set = new HashSet<>();
for(int i = wlen; i <= N; i++) set.add(i);
for(int blacklisted: blacklist) set.remove(blacklisted);
//Map blacklisted Indexes to One of the Whitelisted Indexes
Iterator<Integer> itr = set.iterator();
for(int i = 0; i < blen; i++) {
if(blacklist[i] < wlen) {
blacklistedMapping.put(blacklist[i], itr.next());
}
}
}
public int pick() {
int rIndex = random.nextInt(wlen);
return blacklistedMapping.getOrDefault(rIndex, rIndex);
}
}
/**
* Your RandomPickWithBlacklist object will be instantiated and called as such:
* RandomPickWithBlacklist obj = new RandomPickWithBlacklist(N, blacklist);
* int param_1 = obj.pick();
*/
```

O(1)

O(1)