Design O(1) Randomized Multiset

Implement a randomized multiset data structure that allows duplicate values and supports the following operations in average constant time: - `insert(val)`: Insert one occurrence of `val`. - `remove(val)`: Remove one occurrence of `val` if it exists. - `getRandom()`: Return a random element currently in the collection, where each stored occurrence has equal probability of being returned. You should describe the data structure design and expected time complexity for each operation. Follow-up: suppose each inserted occurrence also has a time-to-live value, so an item expires automatically after its TTL elapses. How would you extend the design so that `insert`, `remove`, and `getRandom` remain as efficient as possible while expired items are excluded correctly? Also explain what test cases you would use to validate the implementation.