Leetcode: Random Pick with Blacklist

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

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();
 */