Reputation: 57
So I've been given the next question: Describe a data structure by the following interface:
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.
Upvotes: 0
Views: 734
Reputation: 59263
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
.
Upvotes: 2