Random Pick with Blacklist

Similar Problems:

- LeetCode: Random Flip Matrix
- LeetCode: Implement Rand10() Using Rand7()
- CheatSheet: Leetcode For Code Interview
- CheatSheet: Common Code Problems & Follow-ups
- Tag: #random, #oodesign, #twopointer

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 <= N <= 1000000000
- 0 <= B.length < min(100000, N)
- [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.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

- Solution:

// https://code.dennyzhang.com/random-pick-with-blacklist // Basic Ideas: two pointer + hashmap // // Get a mapping for items in blacklist // Complexity: Time O(b*log(b)) Space O(b) // b = Len(B) import "sort" type Solution struct { m map[int]int cnt int } func Constructor(N int, blacklist []int) Solution { m := map[int]int{} cnt := N-len(blacklist) blacklistm := map[int]bool{} for _, b := range blacklist { blacklistm[b] = true } sort.Ints(blacklist) index := N-1 left, right := 0, len(blacklist)-1 for left<=right { if blacklist[right] == index { right-- index-- continue } m[blacklist[left]] = index index-- left++ } return Solution{m:m, cnt:cnt} } func (this *Solution) Pick() int { res := rand.Intn(this.cnt) if v, ok := this.m[res]; ok { res = v } return res } /** * Your Solution object will be instantiated and called as such: * obj := Constructor(N, blacklist); * param_1 := obj.Pick(); */