Design a bag that allows duplicates and supports insert, remove-one-copy and 'give me a random member', all in average O(1). A value present three times must be three times as likely to come back as a value present once.
new RandomizedCollection(pick) - pick(n) returns an index in 0..n-1; when omitted, use a uniform random choiceinsert(value) - add one copy. Return true if the value was not in the collection before, otherwise falseremove(value) - remove one copy. Return true if there was a copy to remove, otherwise falsegetRandom() - one stored copy, chosen with pick