sample problems: mutable bag
Design a Data Structure for....
& implement (or provide a sketch of how it works) the following functions:
Represent a mutable bag of elements. A bag is like a set with duplicates.
Create empty bag - O(1)
add element to bag - O(n) where n is number of distinct elements in bag
return total # of elements - O(n)
return # of distinct elements - O(n)
delete an element - O(n)
determine how many occurences of a particular element are in the bag - O(n)
After you have something that works with those time bounds,
see if you can improve (by changing slightly the data structure)
the time bounds for return total # of elements & return
# of distinct elements to O(1)
Can you think of other useful operations on the bag?