Random Pick with Blacklist

You can implement the Solution class by precomputing the mapping between the indices of the whitelist and the actual numbers during initialization. Then, in the pick method, you can generate a random index and return the corresponding number.

Here’s the code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

from random import randint
from typing import List

class Solution:
    def __init__(self, n: int, blacklist: List[int]):
        self.mapping = {}
        whitelist_size = n - len(blacklist)
        blacklist = set(blacklist)

        # Map the numbers from the end of the range that are not blacklisted to the indices that are blacklisted
        j = n - 1
        for b in blacklist:
            if b >= whitelist_size:
                continue
            while j in blacklist:
                j -= 1
            self.mapping[b] = j
            j -= 1

        self.range = whitelist_size

    def pick(self) -> int:
        idx = randint(0, self.range - 1)
        # Return the mapped number if it's in the mapping, otherwise return the index itself
        return self.mapping.get(idx, idx)

You can use this class as follows:

1
2

solution = Solution(7, [2, 3, 5])
print(solution.pick())  # Output can be 0, 1, 4, or 6

This code creates a mapping between the blacklisted indices that are within the whitelist range and the numbers at the end of the range that are not blacklisted. In the pick method, it generates a random index within the whitelist range and returns the corresponding number from the mapping, or the index itself if it’s not blacklisted.

10 Prerequisite LeetCode Problems

This requires understanding of random number generation, array manipulation and mapping concepts. Here are 10 problems to prepare for this problem:

1. 384. Shuffle an Array: Shuffling an array randomly is a key concept to understand before tackling more complex problems involving random number generation.

2. 398. Random Pick Index: This problem deals with picking a random index from an array, similar to the blacklist problem.

3. 382. Linked List Random Node: This problem involves picking a random node from a linked list which helps understand randomness in a different data structure.

4. 380. Insert Delete GetRandom O(1): This problem requires the implementation of a data structure that supports insert, delete and getRandom operations in O(1) time.

5. 528. Random Pick with Weight: This problem deals with weighted random number generation, adding another layer of complexity to the randomness.

6. 710. Random Pick with Blacklist: This problem is a direct predecessor to the problem in question, it requires generating a random number with a blacklist of excluded numbers.

7. 497. Random Point in Non-overlapping Rectangles: This problem is a more complex version of random number generation, where the random number should represent a point in given rectangles.

8. 713. Subarray Product Less Than K: This problem involves working with subarrays, similar to how the blacklist problem requires managing the array of blacklisted numbers.

9. 704. Binary Search: Binary search could be helpful in optimizing the approach for finding if a number is in the blacklist.

10. 442. Find All Duplicates in an Array: This problem requires finding duplicates in an array. Understanding this can be useful as a way to handle the uniqueness of the blacklist.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

from random import randint

class Solution:
    def __init__(self, N: int, blacklist: List[int]):
        blacklist = set(blacklist)  #to avoid TLE
        self.N = N - len(blacklist) #to be used in pick()
        key = [x for x in blacklist if x < N-len(blacklist)]
        val = [x for x in range(N-len(blacklist), N) if x not in blacklist]
        self.mapping = dict(zip(key, val))

    def pick(self) -> int:
        i = randint(0, self.N-1)
        return self.mapping.get(i, i)

Problem Classification

This falls under the domain of Randomized Algorithms, which is a subfield of Algorithm Theory. This is due to the requirement of generating a random integer within a specific range and with a specific constraint (not being in the blacklist).

‘What’ Components:

1. Random Number Generation: The main task in this problem statement is to generate a random number within a specified range, excluding a list of blacklisted numbers.

2. Data Structures: The use of an array to store the blacklisted numbers is crucial. Understanding how to efficiently use and query this structure is a key part of the problem.

3. Optimization: The problem requires the minimization of calls to the random function, which adds an optimization element.

4. Object-Oriented Programming: The problem statement involves the creation of a class with methods, which falls under the concept of Object-Oriented Programming.

This problem can be classified as an Algorithm Design problem, specifically within the category of Randomized Algorithm Design. It requires understanding how to generate random numbers efficiently and effectively while handling constraints and optimizing the usage of built-in functions. Additionally, the solution must be implemented in an object-oriented manner.

The classification is based on the fact that this problem requires creating a randomized algorithm (with constraints) and focuses on the efficient use of the built-in random function. The requirement to structure the solution in an object-oriented manner further solidifies the problem’s classification.

Language Agnostic Coding Drills

1. Dissecting the Code into Distinct Concepts:

   a) Importing Modules: The first line imports the randint function from Python’s built-in random module. This function generates a random integer within a specified range.

   b) Class Definition: The class Solution is defined with two methods, __init__ and pick. This demonstrates the concept of object-oriented programming (OOP), which allows us to encapsulate related data and functions into objects.

   c) Initialization and Attribute Assignment: In the __init__ method, some initializations are done, and attributes are assigned. This involves list comprehension, set creation, arithmetic operations, dictionary creation, and slicing.

   d) Random Number Generation: The pick method generates a random integer within a specified range.

   e) Dictionary Mapping: This code uses a dictionary to map some values to others. This mapping is then used in the pick method to get a value given a key.

2. Coding Concepts/Drills in Order of Increasing Difficulty:

   a) Importing Modules - This is the basic step in Python, which is required to use built-in functions and libraries.

   b) Class Definition and Method Creation - An intermediate level concept of OOP, which encapsulates data and functions for better organization and usability.

   c) Initialization and Attribute Assignment - This requires understanding of basic data types, arithmetic operations, and advanced data structures like lists and dictionaries. It’s a more advanced concept as it includes list comprehension and set creation.

   d) Random Number Generation - Understanding how to generate a random number falls in the intermediate level. It is necessary for many applications.

   e) Dictionary Mapping - Understanding how to create, update, and access data from a dictionary. It’s an advanced topic because it requires good understanding of data structures and key-value pairing.

3. Problem-solving Approach:

   a) First, you’ll want to create a class that can be initialized with the specified parameters.

   b) During initialization, transform the blacklist into a set for efficient lookups, then calculate the effective length of the allowed list (N minus the length of the blacklist).

   c) Construct a dictionary to map each blacklisted number that is less than the effective length, to a number in the tail end of the interval that is not blacklisted. This will remap the blacklisted numbers to valid ones.

   d) When the pick method is called, generate a random number in the effective range. If this number is a key in the mapping dictionary (i.e., it’s a blacklisted number), return the corresponding value. If it’s not a key (i.e., it’s not blacklisted), return the number itself.

Each of these steps can be learned and practiced individually, and when you understand all of them, you can combine them to create the final solution.

Targeted Drills in Python

1. Coding Drills for Each Identified Concept:

Importing Modules: python from random import randint print(randint(0, 10)) # This will print a random integer between 0 and 10

Class Definition and Method Creation: ```python class TestClass: def init(self, value): self.value = value

        def display_value(self):
            print(self.value)

    obj = TestClass(5)
    obj.display_value()  # This will print 5
    ```

Initialization and Attribute Assignment: python my_list = [1, 2, 3, 4, 5] my_set = set(my_list) my_dict = {i: i**2 for i in my_list} print(my_set) # This will print {1, 2, 3, 4, 5} print(my_dict) # This will print {1: 1, 2: 4, 3: 9, 4: 16, 5: 25}

Random Number Generation: python from random import randint print(randint(0, 10)) # This will print a random integer between 0 and 10

Dictionary Mapping: python my_dict = {'a': 1, 'b': 2, 'c': 3} print(my_dict.get('b', 0)) # This will print 2 print(my_dict.get('d', 0)) # This will print 0

2. Problem-Specific Concepts:

   This problem does not require any additional problem-specific concepts.

3. Integrating These Drills:

   First, you’d start by defining a class called Solution. The class would have an __init__ method that takes in two parameters: N and blacklist. Inside this method, you’d convert the blacklist into a set for efficient lookups, calculate the effective length of the allowed list, and construct a dictionary that maps blacklisted numbers less than the effective length to numbers in the tail end of the interval that are not blacklisted.

   Next, you’d define a pick method for the Solution class that generates a random number in the effective range. If the generated number is a key in the mapping dictionary, it returns the corresponding value. Otherwise, it returns the number itself.

   The individual pieces would integrate as follows:

   1 2 3 4 5 6 7 8 9 10 11 12 13

   from random import randint class Solution: def __init__(self, N: int, blacklist: [int]): blacklist = set(blacklist) self.N = N - len(blacklist) key = [x for x in blacklist if x < self.N] val = [x for x in range(self.N, N) if x not in blacklist] self.mapping = dict(zip(key, val)) def pick(self) -> int: i = randint(0, self.N-1) return self.mapping.get(i, i)

   The process of learning these individual drills, understanding how they can be combined, and finally creating a comprehensive solution is an excellent way to learn and practice coding.