"""
https://leetcode.com/problems/insert-delete-getrandom-o1

Related:
  - lt_381

Complexity:
  - Time:
  - Space:
"""

"""
Design a data structure that supports all following operations in average O(1) time.

    insert(val): Inserts an item val to the set if not already present.
    remove(val): Removes an item val from the set if present.
    getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.

Example:

// Init an empty set.
RandomizedSet randomSet = new RandomizedSet();

// Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomSet.insert(1);

// Returns false as 2 does not exist in the set.
randomSet.remove(2);

// Inserts 2 to the set, returns true. Set now contains [1,2].
randomSet.insert(2);

// getRandom should return either 1 or 2 randomly.
randomSet.getRandom();

// Removes 1 from the set, returns true. Set now contains [2].
randomSet.remove(1);

// 2 was already in the set, so return false.
randomSet.insert(2);

// Since 2 is the only number in the set, getRandom always return 2.
randomSet.getRandom();
"""

import random

class RandomizedSet:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.data = []
        self.record = {}
        

    def insert(self, val):
        """
        Inserts a value to the set. Returns true if the set did not already contain the specified element.
        :type val: int
        :rtype: bool
        """
        if val in self.record:
            return False
        
        self.record[val] = len(self.data)
        self.data.append(val)
        return True
        

    def remove(self, val):
        """
        Removes a value from the set. Returns true if the set contained the specified element.
        :type val: int
        :rtype: bool
        """
        if not val in self.record:
            return False
        index = self.record[val]
        self.data[index], self.data[-1] = self.data[-1], self.data[index]
        self.record[self.data[index]] = index
        self.data.pop()
        self.record.pop(val)
        return True

    def getRandom(self):
        """
        Get a random element from the set.
        :rtype: int
        """
        return random.choice(self.data)


# Your RandomizedSet object will be instantiated and called as such:
# obj = RandomizedSet()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()

if __name__ == '__main__':
    test_cases = [
        ([('insert', 1), ('remove', 2), ('insert', 2), ('random', None)], [True, False, True, (1, 2)]),
    ]

    for test_case in test_cases:
        print('case:', test_case)
        obj = RandomizedSet()
        for op_pair, answer in zip(test_case[0], test_case[1]):
            print(op_pair)
            op, val = op_pair
            if op == 'insert':
                output = obj.insert(val)
                assert output == answer 
            elif op == 'remove':
                output = obj.remove(val)
                assert output == answer
            elif op == 'random':
                output = obj.getRandom()
                assert output in answer

3b96a689f0f2e2cd48b208fa5ff3381788c55284
<mask token>


class RandomizedSet:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.data = []
        self.record = {}

    def insert(self, val):
        """
        Inserts a value to the set. Returns true if the set did not already contain the specified element.
        :type val: int
        :rtype: bool
        """
        if val in self.record:
            return False
        self.record[val] = len(self.data)
        self.data.append(val)
        return True

    def remove(self, val):
        """
        Removes a value from the set. Returns true if the set contained the specified element.
        :type val: int
        :rtype: bool
        """
        if not val in self.record:
            return False
        index = self.record[val]
        self.data[index], self.data[-1] = self.data[-1], self.data[index]
        self.record[self.data[index]] = index
        self.data.pop()
        self.record.pop(val)
        return True
    <mask token>


<mask token>

<mask token>


class RandomizedSet:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.data = []
        self.record = {}

    def insert(self, val):
        """
        Inserts a value to the set. Returns true if the set did not already contain the specified element.
        :type val: int
        :rtype: bool
        """
        if val in self.record:
            return False
        self.record[val] = len(self.data)
        self.data.append(val)
        return True

    def remove(self, val):
        """
        Removes a value from the set. Returns true if the set contained the specified element.
        :type val: int
        :rtype: bool
        """
        if not val in self.record:
            return False
        index = self.record[val]
        self.data[index], self.data[-1] = self.data[-1], self.data[index]
        self.record[self.data[index]] = index
        self.data.pop()
        self.record.pop(val)
        return True

    def getRandom(self):
        """
        Get a random element from the set.
        :rtype: int
        """
        return random.choice(self.data)


<mask token>

<mask token>


class RandomizedSet:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.data = []
        self.record = {}

    def insert(self, val):
        """
        Inserts a value to the set. Returns true if the set did not already contain the specified element.
        :type val: int
        :rtype: bool
        """
        if val in self.record:
            return False
        self.record[val] = len(self.data)
        self.data.append(val)
        return True

    def remove(self, val):
        """
        Removes a value from the set. Returns true if the set contained the specified element.
        :type val: int
        :rtype: bool
        """
        if not val in self.record:
            return False
        index = self.record[val]
        self.data[index], self.data[-1] = self.data[-1], self.data[index]
        self.record[self.data[index]] = index
        self.data.pop()
        self.record.pop(val)
        return True

    def getRandom(self):
        """
        Get a random element from the set.
        :rtype: int
        """
        return random.choice(self.data)


if __name__ == '__main__':
    test_cases = [([('insert', 1), ('remove', 2), ('insert', 2), ('random',
        None)], [True, False, True, (1, 2)])]
    for test_case in test_cases:
        print('case:', test_case)
        obj = RandomizedSet()
        for op_pair, answer in zip(test_case[0], test_case[1]):
            print(op_pair)
            op, val = op_pair
            if op == 'insert':
                output = obj.insert(val)
                assert output == answer
            elif op == 'remove':
                output = obj.remove(val)
                assert output == answer
            elif op == 'random':
                output = obj.getRandom()
                assert output in answer

<mask token>
import random


class RandomizedSet:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.data = []
        self.record = {}

    def insert(self, val):
        """
        Inserts a value to the set. Returns true if the set did not already contain the specified element.
        :type val: int
        :rtype: bool
        """
        if val in self.record:
            return False
        self.record[val] = len(self.data)
        self.data.append(val)
        return True

    def remove(self, val):
        """
        Removes a value from the set. Returns true if the set contained the specified element.
        :type val: int
        :rtype: bool
        """
        if not val in self.record:
            return False
        index = self.record[val]
        self.data[index], self.data[-1] = self.data[-1], self.data[index]
        self.record[self.data[index]] = index
        self.data.pop()
        self.record.pop(val)
        return True

    def getRandom(self):
        """
        Get a random element from the set.
        :rtype: int
        """
        return random.choice(self.data)


if __name__ == '__main__':
    test_cases = [([('insert', 1), ('remove', 2), ('insert', 2), ('random',
        None)], [True, False, True, (1, 2)])]
    for test_case in test_cases:
        print('case:', test_case)
        obj = RandomizedSet()
        for op_pair, answer in zip(test_case[0], test_case[1]):
            print(op_pair)
            op, val = op_pair
            if op == 'insert':
                output = obj.insert(val)
                assert output == answer
            elif op == 'remove':
                output = obj.remove(val)
                assert output == answer
            elif op == 'random':
                output = obj.getRandom()
                assert output in answer

"""
https://leetcode.com/problems/insert-delete-getrandom-o1

Related:
  - lt_381

Complexity:
  - Time:
  - Space:
"""

"""
Design a data structure that supports all following operations in average O(1) time.

    insert(val): Inserts an item val to the set if not already present.
    remove(val): Removes an item val from the set if present.
    getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.

Example:

// Init an empty set.
RandomizedSet randomSet = new RandomizedSet();

// Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomSet.insert(1);

// Returns false as 2 does not exist in the set.
randomSet.remove(2);

// Inserts 2 to the set, returns true. Set now contains [1,2].
randomSet.insert(2);

// getRandom should return either 1 or 2 randomly.
randomSet.getRandom();

// Removes 1 from the set, returns true. Set now contains [2].
randomSet.remove(1);

// 2 was already in the set, so return false.
randomSet.insert(2);

// Since 2 is the only number in the set, getRandom always return 2.
randomSet.getRandom();
"""

import random

class RandomizedSet:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.data = []
        self.record = {}
        

    def insert(self, val):
        """
        Inserts a value to the set. Returns true if the set did not already contain the specified element.
        :type val: int
        :rtype: bool
        """
        if val in self.record:
            return False
        
        self.record[val] = len(self.data)
        self.data.append(val)
        return True
        

    def remove(self, val):
        """
        Removes a value from the set. Returns true if the set contained the specified element.
        :type val: int
        :rtype: bool
        """
        if not val in self.record:
            return False
        index = self.record[val]
        self.data[index], self.data[-1] = self.data[-1], self.data[index]
        self.record[self.data[index]] = index
        self.data.pop()
        self.record.pop(val)
        return True

    def getRandom(self):
        """
        Get a random element from the set.
        :rtype: int
        """
        return random.choice(self.data)


# Your RandomizedSet object will be instantiated and called as such:
# obj = RandomizedSet()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()

if __name__ == '__main__':
    test_cases = [
        ([('insert', 1), ('remove', 2), ('insert', 2), ('random', None)], [True, False, True, (1, 2)]),
    ]

    for test_case in test_cases:
        print('case:', test_case)
        obj = RandomizedSet()
        for op_pair, answer in zip(test_case[0], test_case[1]):
            print(op_pair)
            op, val = op_pair
            if op == 'insert':
                output = obj.insert(val)
                assert output == answer 
            elif op == 'remove':
                output = obj.remove(val)
                assert output == answer
            elif op == 'random':
                output = obj.getRandom()
                assert output in answer
