Generate a new element different from 1000 elements of an array

Question

I was asked this questions in an interview. Consider the scenario of punched cards, where each punched card has 64 bit pattern. I was suggested each card as an int since each int is a collection of bits.

Also, to be considered that I have an array which already contains 1000 such cards. I have to generate a new element everytime which is different from the previous 1000 cards. The integers(aka cards) in the array are not necessarily sorted.

Even more, how would that be possible the question was for C++, where does the 64 bit int comes from and how can I generate this new card from the array where the element to be generated is different from all the elements already present in the array?

Answer 1

There are 2⁶⁴ 64 bit integers, a number that is so much larger than 1000 that the simplest solution would be to just generate a random 64 bit number, and then verify that it isn't in the table of already generated numbers. (The probability that it is is infinitesimal, but you might as well be sure.)

Since most random number generators do not generate 64 bit values, you are left with either writing your own, or (much simpler), combining the values, say by generating 8 random bytes, and memcpying them into a uint64_t.

As for verifying that the number isn't already present, std::find is just fine for one or two new numbers; if you have to do a lot of lookups, sorting the table and using a binary search would be worthwhile. Or some sort of a hash table.