Random pick with Blacklist

 

Given an integer n and a list of integers l, write a function that randomly generates a number from 0 to n-1 that isn't in l (uniform).

The simplest approach is to pick a random number in the given range and test if it is blacklisted. Repeat the process until a non blacklisted random number is found. 

This has O(l) time complexity, where l is the length of the blacklisted numbers.

Most random number functions operate within a range of values. Creating a range that is void of blacklisted numbers will improve runtime to constant time, while having O(l) memory complexity.

One approach is to remap all the blacklisted numbers to a reserved range - at one end of the given range. The remapped number would be stored in a hash map for quick lookup. A blacklisted number that is in the reserved range would not require a mapping.

We can now generate numbers using the non reserved range. If there is a collision a remapped value can be quickly looked up and used instead.

Code

The constructor in this code generates the map containing the remapped values. The random number is only generated for the effective range. The map is used to resolve mapped values in case the randomly generated number was remapped.

Things to remember when generating the map containing the remapped values -

• The range is between 0 and n-1
• A blacklisted number in the reserved / blocked-off range should not be remapped
• A remapped number does not point to another blacklisted number

public class Solution {

    int n;
    int effectiveN;

    Random r = new Random();

    Map<Integer,Integer> blackListRemap = new HashMap<>();

    public Solution(int n, int[] blacklist) {
        this.n = n; // 10 , [ 1 , 9 ]

        Set<Integer> s = new HashSet<>();
        for (int i : blacklist)
            if (i < n) // filter out blacklist out of range
                s.add(i);

        this.effectiveN = this.n - s.size(); // effectiveN == 8

        int remap = effectiveN;

        // remap the black listed values to other numbers
        for (int blacklistNumber: blacklist) {

            if (blacklistNumber < effectiveN) {
                while (s.contains(remap))
                    remap++;

                blackListRemap.put(blacklistNumber, remap);
                remap++;
            }
        }
        
        System.out.println(blackListRemap);
    }

    public int getRemapped(int randomNumber) {
        if (blackListRemap.containsKey(randomNumber))
            return blackListRemap.get(randomNumber);
        return randomNumber;
    }

    public int pick() {

        // only finding a random number in the effective range of values
        // after the blacklisted values have been subtracted
        int randomNumber = r.nextInt(effectiveN);

        System.out.println("Generated Random - "+ randomNumber + "\n Effective - " + effectiveN);

        return getRemapped(randomNumber);
    }
}