LeetCode: Random Pick with Blacklist Posted on July 17, 2018July 26, 2020 by braindenny 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: #oodesign, #random, #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(); */ Post Views: 7