Set with constant random element functionality - PrismoSkills
Problem: Design an advanced data structure which has all the functionalities of a set and
additionally it is also able to return a random number from the set in constant time.
Solution: Create a class containing a Map<Object, Integer> and an ArrayList<Object>
Set will provide the default functionality of a set but will additionally store the index of the object in the array.
The ArrayList will store references to the objects in the map.
Insert operations: If the value was not present in the map before, add it to the end of the ArrayList.
Then insert the object in the map with key=object and value=ArrayList.size-1 (this gives the index of thhe object in the array).
Delete operations: Lookup index of object in the ArrayList from the map.
Delete from map and then nullify the index in the ArrayList where the object was present.
To prevent developing holes in the ArrayList, move the last element of the ArrayList to the deleted index and update the index in the map.
Read full article from Set with constant random element functionality - PrismoSkills
Problem: Design an advanced data structure which has all the functionalities of a set and
additionally it is also able to return a random number from the set in constant time.
Solution: Create a class containing a Map<Object, Integer> and an ArrayList<Object>
Set will provide the default functionality of a set but will additionally store the index of the object in the array.
The ArrayList will store references to the objects in the map.
Insert operations: If the value was not present in the map before, add it to the end of the ArrayList.
Then insert the object in the map with key=object and value=ArrayList.size-1 (this gives the index of thhe object in the array).
Delete operations: Lookup index of object in the ArrayList from the map.
Delete from map and then nullify the index in the ArrayList where the object was present.
To prevent developing holes in the ArrayList, move the last element of the ArrayList to the deleted index and update the index in the map.
Read full article from Set with constant random element functionality - PrismoSkills
