Design O(1) insert/delete and frequency-weighted random

Problem

Design a data structure that supports the following operations in average $O(1)$ time:

1. add(x) -> bool
   • Inserts value x into the collection.
   • Returns true if x was not already present in the collection before this call; otherwise returns false .
   • Duplicates are allowed .
2. delete(x) -> bool
   • Removes one occurrence of value x from the collection (if present).
   • Returns true if an occurrence was removed; otherwise returns false .
3. random() -> int
   • Returns a random element from the collection such that the probability of returning a value is proportional to its frequency .
   • Equivalently, if the multiset currently contains N total elements counting duplicates, random() should pick uniformly among the N occurrences .

Example

If the collection contains [5, 5, 7], then:

• P(random() = 5) = 2/3
• P(random() = 7) = 1/3

Notes / Constraints

• You may assume values fit in 32-bit signed integers.
• Aim for average $O(1)$ time per operation and $O(N)$ space overall.