algoadvance

Clarifying Questions

1. Operations Supported: The problem asks us to support insert, delete, and getRandom operations with average O(1) time complexity. Are there any constraints on the number of operations?
2. Element Uniqueness: Should the data structure handle duplicate elements or assume all elements are unique?
3. Output Requirements: During the getRandom operation, should we ensure a uniform random distribution of the elements?

Based on the problem name and customary constraints, we assume:

1. We need to support insert(val), delete(val), and getRandom().
2. Elements are unique.
3. getRandom() should return a random element from the set of current elements, with each element having an equal probability of being returned.

Strategy

To achieve average O(1) time complexity for all operations, we can use:

• A list to store elements.
• A dictionary to store the indices of elements in the list.

Insert Operation:

• Append the element to the list and record its index in the dictionary.

Delete Operation:

• Find the element in the dictionary, get its index from the list, and swap it with the last element in the list.
• Update the dictionary with the new position of the swapped element.
• Remove the element from both the list and dictionary.

GetRandom Operation:

• Use Python’s random.choice to get a random element from the list.

Code

import random

class RandomizedSet:
    def __init__(self):
        self.elements_list = []
        self.elements_dict = {}

    def insert(self, val: int) -> bool:
        if val in self.elements_dict:
            return False
        self.elements_dict[val] = len(self.elements_list)
        self.elements_list.append(val)
        return True

    def delete(self, val: int) -> bool:
        if val not in self.elements_dict:
            return False
        # Index of the element to delete
        idx_to_remove = self.elements_dict[val]
        # Move the last element to the spot of the element to remove
        last_element = self.elements_list[-1]
        self.elements_list[idx_to_remove] = last_element
        self.elements_dict[last_element] = idx_to_remove
        # Remove the last element
        self.elements_list.pop()
        del self.elements_dict[val]
        return True

    def getRandom(self) -> int:
        return random.choice(self.elements_list)

# Example Usage
# randomizedSet = RandomizedSet()
# print(randomizedSet.insert(1))    # True
# print(randomizedSet.insert(2))    # True
# print(randomizedSet.getRandom())  # Could be 1 or 2
# print(randomizedSet.delete(1))    # True
# print(randomizedSet.getRandom())  # Should be 2

Time Complexity

• insert(val): Average O(1), since dictionary operations (insert) and list append are O(1).
• delete(val): Average O(1), since dictionary operations (lookup and delete) and list operations (swap and pop) are O(1).
• getRandom(): O(1), as random.choice on a list is O(1).

This approach ensures all operations meet the required time complexity on average.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?