Random Pick with Blacklist

hard random hash map design

Problem

Pick uniformly at random from [0, n) excluding blacklist[].

Inputn=4 blacklist=[2]

Output0,1,3 uniformly

Remap indices to skip the bad ones.

input

import random
class Solution:
    def __init__(self, n, blacklist):
        self.bound = n - len(blacklist); m = {}
        bset = set(blacklist); last = n - 1
        for b in blacklist:
            if b < self.bound:
                while last in bset: last -= 1
                m[b] = last; last -= 1
        self.map = m
    def pick(self):
        x = random.randrange(self.bound); return self.map.get(x, x)

class Solution {
  constructor(n, blacklist) {
    this.bound = n - blacklist.length;
    const set = new Set(blacklist);
    this.map = new Map(); let last = n - 1;
    for (const b of blacklist) {
      if (b < this.bound) {
        while (set.has(last)) last--;
        this.map.set(b, last); last--;
      }
    }
  }
  pick() { const x = Math.floor(Math.random() * this.bound); return this.map.get(x) ?? x; }
}

class Solution {
    int bound; Map map = new HashMap<>(); Random r = new Random();
    public Solution(int n, int[] blacklist) {
        bound = n - blacklist.length;
        Set set = new HashSet<>(); for (int b : blacklist) set.add(b);
        int last = n - 1;
        for (int b : blacklist) {
            if (b < bound) {
                while (set.contains(last)) last--;
                map.put(b, last); last--;
            }
        }
    }
    public int pick() { int x = r.nextInt(bound); return map.getOrDefault(x, x); }
}

class Solution {
    int bound; unordered_map m;
public:
    Solution(int n, vector& blacklist) {
        bound = n - blacklist.size();
        unordered_set s(blacklist.begin(), blacklist.end());
        int last = n - 1;
        for (int b : blacklist) {
            if (b < bound) {
                while (s.count(last)) last--;
                m[b] = last; last--;
            }
        }
    }
    int pick() { int x = rand() % bound; auto it = m.find(x); return it == m.end() ? x : it->second; }
};

Explanation

We want a uniform pick from [0, n) while skipping the blacklisted numbers. Rejection sampling (pick, retry if bad) could be slow, so instead we squeeze all the valid numbers into a clean front range and remap the blacklisted holes that land in it.

Let bound = n - len(blacklist). There are exactly bound good values, so we will only ever pick from [0, bound). The problem is some blacklisted numbers might sit inside that low range — those are the ones we must redirect to a good number living at or above bound.

In the constructor we sweep a pointer last down from n-1, skipping any number that is itself blacklisted. For each blacklisted b < bound, we set map[b] = last (a guaranteed-good high value) and move last down. Then pick() just draws x from [0, bound) and returns map.get(x, x) — the remap if x was a hole, otherwise x as-is.

Example: n = 4, blacklist = [2]. Here bound = 3, and 2 is below bound, so it maps to the highest good value 3: map = {2: 3}. A pick of 0 or 1 returns itself; a pick of 2 returns 3 — so the result is uniform over {0, 1, 3}.

Building the map is O(B) for the blacklist size, and each pick() is one random draw plus one lookup, O(1).

Time: O(B) init, O(1) pick Space: O(B)