[refibrillator]

Love anecdotes like this! But admittedly I feel a bit lost, so please forgive my ignorance when I ask: why does choosing a subset of k integers at random require deduplication? My naive intuition is that sampling without replacement can be done in linear time (hash table to track chosen elements?). I’m probably not understanding the problem formulation here.

[willvarfar]

your random number function might return the same number multiple times? So to choose k random but unique numbers you may have to call the random number function more than k times?

Of course my intuition would be that you can do a random shuffle and then take the first k, which is O(N). So I might be misunderstanding.

[chopin]

Is there a O(n) shuffling algorithm? In place, I don't think so.

[tialaramex]

Um, the "Knuth Shuffle" aka "Fisher-Yates" ?

https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

[minitech]

You can do that for O(N), but the problem can be solved in O(k).