So I’ve been given the next question:
Describe a data structure by the following interface:
- The structure will contain n elements, where each element holds a key and a value (meaning, each element is (key, value)).
- insert ((key, value)): insert an element in O(1) average case and O(log n) worst case.
- delete ((key, value)): delete the element that correspond to the given key in O(1) average case and O(log n) worst case.
- find (key): find the element that correspond to the given key and return it’s value in O(1) average case and O(log n) worst case.
- setAll (m): change the value of each element in the structure to be m in O(1) worst case
So my main thought was to use a hash table to ensure O(1) average case runtime for insert, delete, find. the hash table will be implmented by chaining, but instead of linked list, use an AVL tree, so in the worst case, insert, delete and find will be O(log n).
But I got stuck on setAll. I can’t deal with this problem in O(1) worst case runtime. I know that you can’t really change all the values because it requires traversal on the elements, so I thought maybe I can use global variables and keep track of the calls for setAll but I can’t really see how I implement such thing.
In addition, there is no limit on the space complxity, which is why I used a hash table containing AVL trees. This is also a clue that our lecturer gave us.
>Solution :
A hash table with AVL trees is a good start.
To implement setAll(m), keep an operation counter, and mark each entry with update_op = operation_count during insert.
When setAll(m) is called, set a field last_reset = operation_count and reset_value = m.
Then modify find so it returns reset_value for any entry with update_op < last_reset.