Skip to content

Prepare For Coder Interview – Denny

  • Basic
  • Medium
  • Hard
  • Architect
  • Life

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. 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();
 */
linkedin
github
slack

Post Views: 7
Posted in HardTagged #twopointer, oodesign, random

Post navigation

LeetCode: Implement Rand10() Using Rand7()
LeetCode: Search in a Binary Search Tree

Leave a Reply Cancel reply

Your email address will not be published.

Tags

#array #backtracking #bfs #binarytree #bitmanipulation #blog #classic #codetemplate #combination #dfs #dynamicprogramming #game #graph #greedy #heap #inspiring #interval #linkedlist #manydetails #math #palindrome #recursive #slidingwindow #stack #string #subarray #trie #twopointer #twosum binarysearch editdistance hashmap intervaldp knapsack monotone oodesign presum rectangle redo review rotatelist series sql treetraversal unionfind

Recent Posts

  • a
  • a
  • a
  • a
  • a

Recent Comments

    Archives

    Categories

    • Amusing
    • Basic
    • Easy
    • Hard
    • Life
    • Medium
    • Resource
    • Review
    • Series
    • Uncategorized
    Proudly powered by WordPress | Theme: petals by Aurorum.