Your question is O(1) Randomized Set. Start with the requirements on the right.
Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.
Turo may need an in-memory set of active vehicle or trip identifiers where inserts, removals, and random sampling are all fast. Implement a RandomizedSet supporting each operation in average O(1) time.
The set must reject duplicate inserts, report whether deletions succeed, and return a uniformly random element from the current set. The data structure should not use a separate random-selection list that requires scanning or shifting elements during deletion.
Implement these methods:
insert(value) returns True if value was added, otherwise False.remove(value) returns True if value was present and removed, otherwise False.getRandom() returns one uniformly random value currently in the set. This method is called only when the set is non-empty.value is an integer. For automated testing, implement run_randomized_set(operations), which executes operation arrays such as ["insert", 10], ["remove", 10], and ["getRandom"], returning the results in order.
def run_randomized_set(operations):