So, I ran across a problem for building a set with a getRandomElement() function. Easy enough at first glance. But the more I think about this, the less I think it’s possible to do this in O(1) time complexity. There was no given requirement for constant time, but all of a sets major functionality is in constant time, so I feel like it’s implied that this should also be accomplished in constant time.
The goal of a set is for the hashing function to reduce collisions. The problem now becomes that if you simply generate random integers and try to select the index using this random integer, you will most likely run into an “empty” slot in your set....in which case you must generate a new random number and try again. Essentially the better your hashing function, the worst your getRandomElement will perform using this approach.
So then I thought...okay, why not store the indices after every insertion? Then, generate a random number and select an index from this collection of indices. I thought this was a good idea, but then comes the problem of removing elements. We would also have to remove the corresponding index from our index list, as well as removing the element itself from our Set. How can we find the correct index to remove any faster than linear time???
Anyway, getting a random element from a set FEELS like it can be done in better than linear time. Btw, I’m handling collisions by chaining. I don’t want to waste time trying to do what’s mathematically impossible, but I’m also not a mathematician and I don’t want to give up on something that actually is possible.