Insert Delete GetRandom O(1)

Medium

Google

1 view

Topics:

Arrays

Implement the RandomizedSet class:

RandomizedSet(): Initializes the RandomizedSet object.
bool insert(int val): Inserts an item val into the set if not present. Returns true if the item was not present, false otherwise.
bool remove(int val): Removes an item val from the set if present. Returns true if the item was present, false otherwise.
int getRandom(): Returns a random element from the current set of elements (it's guaranteed that at least one element exists when this method is called). Each element must have the same probability of being returned.

You must implement the functions of the class such that each function works in average O(1) time complexity.

Example:

Input
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
Output
[null, true, false, true, 2, true, false, 2]

Explanation
RandomizedSet randomizedSet = new RandomizedSet();
randomizedSet.insert(1); // Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomizedSet.remove(2); // Returns false as 2 does not exist in the set.
randomizedSet.insert(2); // Inserts 2 to the set, returns true. Set now contains [1,2].
randomizedSet.getRandom(); // getRandom() should return either 1 or 2 randomly.
randomizedSet.remove(1); // Removes 1 from the set, returns true. Set now contains [2].
randomizedSet.insert(2); // 2 was already in the set, so return false.
randomizedSet.getRandom(); // Since 2 is the only number in the set, getRandom() will always return 2.

Insert Delete GetRandom O(1)

Medium

Google

1 view

Topics:

Arrays

Implement the RandomizedSet class:

RandomizedSet(): Initializes the RandomizedSet object.
bool insert(int val): Inserts an item val into the set if not present. Returns true if the item was not present, false otherwise.
bool remove(int val): Removes an item val from the set if present. Returns true if the item was present, false otherwise.
int getRandom(): Returns a random element from the current set of elements (it's guaranteed that at least one element exists when this method is called). Each element must have the same probability of being returned.

You must implement the functions of the class such that each function works in average O(1) time complexity.

Example:

Input
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
Output
[null, true, false, true, 2, true, false, 2]

Explanation
RandomizedSet randomizedSet = new RandomizedSet();
randomizedSet.insert(1); // Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomizedSet.remove(2); // Returns false as 2 does not exist in the set.
randomizedSet.insert(2); // Inserts 2 to the set, returns true. Set now contains [1,2].
randomizedSet.getRandom(); // getRandom() should return either 1 or 2 randomly.
randomizedSet.remove(1); // Removes 1 from the set, returns true. Set now contains [2].
randomizedSet.insert(2); // 2 was already in the set, so return false.
randomizedSet.getRandom(); // Since 2 is the only number in the set, getRandom() will always return 2.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of possible values for 'val' in the insert and delete operations?
If I call delete on a value that doesn't exist, should I return false or throw an exception?
How often will each of the operations (insert, delete, getRandom) be called relative to each other? Is there a particular operation that will be called significantly more often than others?
Can I assume the elements inserted will be integers?
Is there a maximum number of elements that the RandomizedSet will hold?

Brute Force Solution

Approach

The main idea is to keep track of all numbers in a straightforward manner. For each operation, we'll just do the most basic thing we can think of to achieve the desired outcome, without worrying about efficiency.

Here's how the algorithm would work step-by-step:

To insert a number, we simply add it to our collection of numbers.
To remove a number, we look through our collection until we find it, and then we take it out.
To get a random number, we pick a number from our collection completely at random. If our collection changes, we simply pick a different number at random.

Code Implementation

import random

class RandomizedSet:

    def __init__(self):
        self.number_list = []

    def insert(self, value):
        if value not in self.number_list:
            self.number_list.append(value)
            return True
        return False

    def remove(self, value):
        if value in self.number_list:
            self.number_list.remove(value)
            return True
        return False

    def getRandom(self):
        # Use python's random library
        # to pick a random index.

        random_index = random.randint(0, len(self.number_list) - 1)

        # Return a random number from the list
        # after selecting a random index

        return self.number_list[random_index]

Big(O) Analysis

Time Complexity

O(n) – The insert operation involves adding an element to a collection, which takes O(1) time, but because in the getRandom function, we have to select randomly from our collection which takes O(n) and in the remove function, we look through our collection until we find it, and then we take it out which takes O(n). Overall, the time complexity is dominated by remove and getRandom which are O(n).

Space Complexity

O(N) – The algorithm uses a collection to store numbers. In the worst case, the collection will contain all N inserted numbers. No other significant auxiliary data structures are used besides the collection itself, resulting in a space complexity proportional to the number of inserted elements. Thus, the auxiliary space used is O(N).

Optimal Solution

Approach

To make these operations super fast, we'll use a clever combination of two data structures. One will let us quickly look up if a number exists, and the other will let us easily pick a random number.

Here's how the algorithm would work step-by-step:

When we add a number, we'll put it in both of our special structures: one that lets us check if it's there, and another that keeps track of all our numbers in a simple order.
When we remove a number, it's a bit trickier. First, we find its spot in the structure that keeps them in order.
Then, we replace the number we want to remove with the *last* number in our structure that keeps them in order. This is the key to making the remove operation fast.
After replacing, we shrink our structure since we effectively removed an element and update the position tracker from the first data structure with this change.
To pick a random number, we simply ask the ordered structure to give us a random element directly. Because it's ordered, getting a random element is quick.
By combining these two structures, we can add, remove, and pick random numbers very efficiently.

Code Implementation

import random

class RandomizedSet:

    def __init__(self):
        self.array_of_numbers = []
        self.position_map = {}

    def insert(self, value):
        if value in self.position_map:
            return False
        
        self.array_of_numbers.append(value)
        self.position_map[value] = len(self.array_of_numbers) - 1
        return True

    def remove(self, value):
        if value not in self.position_map:
            return False
        
        # Get the index of the element to remove.
        index_to_remove = self.position_map[value]

        # Get the last element in the array.
        last_element = self.array_of_numbers[-1]

        # Replace the element to remove with the last element.
        self.array_of_numbers[index_to_remove] = last_element

        # Update the position of the last element.
        self.position_map[last_element] = index_to_remove

        # Remove the last element from the array. Important for O(1) removal
        self.array_of_numbers.pop()

        # Remove the value from the position map.
        del self.position_map[value]

        #Update position_map if the array isn't empty
        if last_element != value:
            self.position_map[last_element] = index_to_remove

        return True

    def getRandom(self):
        #Ensure we can return a random number
        if not self.array_of_numbers:
            return None

        # Generate a random index within the bounds of the array.
        random_index = random.randint(0, len(self.array_of_numbers) - 1)
        return self.array_of_numbers[random_index]

Big(O) Analysis

Time Complexity

O(1) – The insert operation involves adding an element to a hash map and a list, both constant time operations. The remove operation involves finding the index of an element in a hash map (O(1)), swapping elements in a list (O(1)), and removing the last element from the list (O(1)), and updating the index in the hashmap (O(1)). The getRandom operation involves generating a random index and accessing an element in a list by index, which takes O(1) time. Therefore, all operations have a time complexity of O(1).

Space Complexity

O(N) – The solution utilizes two auxiliary data structures: one to check for the existence of numbers (likely a hash map) and another to store the numbers in order (likely a list or dynamic array). The hash map stores each number and its index, and the list stores the numbers themselves. Therefore, the space required grows linearly with the number of elements inserted, N, where N is the number of elements in the data structure. Thus, the auxiliary space complexity is O(N).

Edge Cases

Case	How to Handle
Inserting a value that already exists in the set.	The insert() method should return false without modifying the set.
Deleting a value that does not exist in the set.	The delete() method should return false without modifying the set.
Calling getRandom() on an empty set.	The getRandom() method should handle the edge case of empty set gracefully, likely returning null or throwing exception based on pre-defined behavior.
Maximum number of inserts allowed (memory constraints).	The solution should consider memory constraints and potentially throw an exception if the set reaches its maximum capacity.
Large integer values for inserted elements (potential integer overflow).	Use appropriate data types (e.g., long) to handle large integer values to prevent integer overflow.
Repeated insertions and deletions of the same element.	Ensure the underlying data structures (list and hash map) remain consistent with each insert and delete to guarantee correctness.
Random number generator failing or producing biased results.	Ensure the random number generator is properly initialized and unbiased for uniform element selection.
Deleting the last element in the list.	Deleting the last element should update the index in the hashmap to correctly point to the new location and ensure proper functioning of getRandom().