Implement a Dynamic Multiset/Bag

To implement a dynamic multiset or bag that supports duplicates efficiently, I would use a Hash Map, specifically a Dictionary in Swift given Apple's ecosystem. In this design, the keys represent the unique elements stored in the bag, and the values are integers representing the frequency of each element. For the 'add' operation, we check if the element exists in the map. If it does, we increment its value; otherwise, we insert it with a count of one. This ensures O(1) average time complexity. For 'contains', we simply check if the key exists and its associated count is greater than zero, also achieving O(1) performance. The 'remove' operation requires slightly more nuance. If the requirement is to remove only one instance, we decrement the count. If the count drops to zero, we remove the key from the map to keep memory usage optimal. If the requirement is to remove all instances, we delete the key immediately. This approach prevents the data structure from bloating with zero-count entries. Regarding complexity, both time and space are optimized. Time complexity for all three operations is O(1) on average. Space complexity is O(K), where K is the number of unique elements, which is strictly better than storing every duplicate in a list. This design aligns well with Apple's emphasis on performance and clean, efficient code that scales well under heavy load, such as in real-time event processing systems.