Data structure for fast insertion and fast random element removal

I'm looking for a data structure that supports the following operations:

add(elem) - Add an element to the data structure.

remove_random() - Remove and return a random element.

The best I got so far is just shuffling a list on every insertion (or on every lookup), and popping from the top. However, this can be quite slow, so I'm looking for a more specialized data structure. Assume we can generate random numbers for free.

You can achieve constant amortized time per operation by keeping a dynamically-sized array $A$ (using the doubling/halving technique). To insert an element append it at the end. To implement remove_random() generate a random index $k$ between $1$ and $n$, swap $A[k]$ with $A[n]$ and delete (and return) $A[n]$.

If you want a non-amortized worst-case bound on the time complexity, then an AVL in which each node $v$ has been augmented to also store the size of the subtree rooted in $v$ supports both those operation in $O(\log n)$ worst-case time per operation.

To implement remove_random() simply generate a random number $k$ between $1$ and $n$ and find the element $e$ of rank $k$ in the tree. Then delete $e$ from the tree and return it.

StackExchange Computer Science Q#146012, answer score: 29