The Random Pick with Blacklist problem asks you to design a class that picks a random integer from [0, n-1] excluding a blacklist, with equal probability for all non-blacklisted numbers. The key challenge: do this in O(1) per pick call. This hard randomized coding problem maps blacklisted numbers in the "good range" to non-blacklisted numbers in the "bad range." The array, math, hash table, sorting, binary search, and randomized interview pattern is the core.
Uber, Amazon, and Google ask this because the O(1) pick solution requires a clever virtual mapping: split [0, n-1] into a "good zone" [0, n-b-1] and a "bad zone" [n-b, n-1]. Numbers in the good zone that are blacklisted get remapped to non-blacklisted numbers in the bad zone.
Virtual remapping. whitelist_size = n - len(blacklist). Identify blacklisted numbers in [0, whitelist_size-1] and non-blacklisted numbers in [whitelist_size, n-1]. Build a map: blacklisted_in_good_zone → clean_in_bad_zone. For pick(): generate random r in [0, whitelist_size-1]. If r is in the map, return map[r]. Else return r directly.
n=7, blacklist=[2,3,5]. whitelist_size=4. Good zone=[0..3], bad zone=[4..6]. Blacklisted in good zone: {2,3}. Clean in bad zone: {4,6} (5 is blacklisted). Map: {2→4, 3→6}. Pick r=2: return map[2]=4. Pick r=0: return 0. Pick r=1: return 1. Pick r=3: return map[3]=6. All uniform.
Random Pick with Blacklist demonstrates virtual space reduction: conceptually "remove" blacklisted numbers by remapping only those in the "good zone" to clean numbers in the "bad zone." Only O(blacklist size) space is needed, and pick is O(1). Practice similar virtual remapping problems: "map shuffled indices," "virtual contiguous range." This technique appears in distributed systems and database design.
