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.

Answer 2

I may be missing something, but most of the other answers appear to me as overly complicated. Just sort the original array and then start counting from zero: if the current count is in the array skip it, otherwise you have your next number. This algorithm is O(n), where n is the number of newly generated numbers: both sorting the array and skipping existing numbers are constants. Here's an example:

#include <algorithm>
#include <iostream>
unsigned array[] = { 98, 1, 24, 66, 20, 70, 6, 33, 5, 41 };

unsigned count = 0;
unsigned index = 0;

int main() {
  std::sort(array, array + 10);
  while ( count < 100 ) {
    if ( count > array[index] )
      ++index;
    else {
      if ( count < array[index] )
        std::cout << count << std::endl;
      ++count;
    }
  }
}

Answer 3

Here's an O(n) algorithm:

int64 generateNewValue(list_of_cards)
{
    return find_max(list_of_cards)+1;
}

Note: As @amit points out below, this will fail if INT64_MAX is already in the list.

As far as I'm aware, this is the only way you're going to get O(n). If you want to deal with that (fairly important) edge case, then you're going to have to do some kind of proper sort or search, which will take you to O(n log n).

Answer 4

@arne is almost there. What you need is a self-balancing interval tree, which can be built in O(n lg n) time.

Then take the top node, which will store some interval [i, j]. By the properties of an interval tree, both i-1 and j+1 are valid candidates for a new key, unless i = UINT64_MIN or j = UINT64_MAX. If both are true, then you've stored 2^64 elements and you can't possibly generate a new element. Store the new element, which takes O(lg n) worst-case time.

I.e.: init takes O(n lg n), generate takes O(lg n). Both are worst-case figures. The greatest thing about this approach is that the top node will keep "growing" (storing larger intervals) and merging with its successor or predecessor, so the tree will actually shrink in terms of memory use and eventually the time per operation decays to O(1). You also won't waste any numbers, so you can keep generating until you've got 2^64 of them.

Answer 5

This algorithm has O(N lg N) initialisation, O(1) query and O(N) memory usage. I assume you have some integer type which I will refer to as int64 and that it can represent the integers [0, int64_max].

1. Sort the numbers
2. Create a linked list containing intervals [u, v]
3. Insert [1, first number - 1]
4. For each of the remaining numbers, insert [prev number + 1, current number - 1]
5. Insert [last number + 1, int64_max]

You now have a list representing the numbers which are not used. You can simply iterate over them to generate new numbers.

Answer 6

I think the way to go is to use some kind of hashing. So you store your cards in some buckets based on lets say on MOD operation. Until you create some sort of indexing you are stucked with looping over the whole array.

IF you have a look on HashSet implementation in java you might get a clue.

Edit: I assume you wanted them to be random numbers, if you don't mind sequence MAX+1 below is good solution :)

Answer 7

You could build a binary tree of the already existing elements and traverse it until you find a node whose depth is not 64 and which has less than two child nodes. You can then construct a "missing" child node and have a new element. The should be fairly quick, in the order of about O(n) if I'm not mistaken.

Answer 8

bool seen[1001] = { false };
for each element of the original array
    if the element is in the range 0..1000
        seen[element] = true
find the index for the first false value in seen

Answer 9

Initialization: Don't sort the list. Create a new array 1000 long containing 0..999. Iterate the list and, if any number is in the range 0..999, invalidate it in the new array by replacing the value in the new array with the value of the first item in the list.

Insertion: Use an incrementing index to the new array. If the value in the new array at this index is not the value of the first element in the list, add it to the list, else check the value from the next position in the new array. When the new array is used up, refill it using 1000..1999 and invalidating existing values as above. Yes, this is looping over the list, but it doesn't have to be done for each insertion.

Near O(1) until the list gets so large that occasionally iterating it for invalidation of the 'new' new array becomes significant. Maybe you could mitigate this by using a new array that grows, maybee always the size of the list?

Rgds, Martin

Answer 10

Put them all into a hash table of size > 1000, and find the empty cell (this is the parking problem). Generate a key for that. This will of course work better for bigger table size. The table needs only 1-bit entries.

EDIT: this is the pigeonhole principle. This needs "modulo tablesize" (or some other "semi-invertible" function) for a hash function.

unsigned hashtab[1001] = {0,};
unsigned long long long long numbers[1000] = { ... };

void init (void)
{
unsigned idx;

for (idx=0; idx < 1000; idx++) {
    hashtab [ numbers[idx] % 1001 ] += 1; }

}

unsigned long long long long generate(void)
{
unsigned idx;

for (idx = 0; idx < 1001; idx++) {
    if ( !hashtab [ idx] ) break;  }

return idx + rand() * 1001;
}

Answer 11

Based on the solution here: question on array and number

Since there are 1000 numbers, if we consider their remainders with 1001, at least one remainder will be missing. We can pick that as our missing number.

So we maintain an array of counts: C[1001], which will maintain the number of integers with remainder r (upon dividing by 1001) in C[r].

We also maintain a set of numbers for which C[j] is 0 (say using a linked list).

When we move the window over, we decrement the count of the first element (say remainder i), i.e. decrement C[i]. If C[i] becomes zero we add i to the set of numbers. We update the C array with the new number we add.

If we need one number, we just pick a random element from the set of j for which C[j] is 0.

This is O(1) for new numbers and O(n) initially.

This is similar to other solutions but not quite.

Answer 12

How about something simple like this:

1) Partition the array into numbers equal and below 1000 and above

2) If all the numbers fit within the lower partition then choose 1001 (or any number greater than 1000) and we're done.

3) Otherwise we know that there must exist a number between 1 and 1000 that doesn't exist within the lower partition.

4) Create a 1000 element array of bools, or a 1000-element long bitfield, or whatnot and initialize the array to all 0's

5) For each integer in the lower partition, use its value as an index into the array/bitfield and set the corresponding bool to true (ie: do a radix sort)

6) Go over the array/bitfield and pick any unset value's index as the solution

This works in O(n) time, or since we've bounded everything by 1000, technically it's O(1), but O(n) time and space in general. There are three passes over the data, which isn't necessarily the most elegant approach, but the complexity remains O(n).

Answer 13

you can create a new array with the numbers that are not in the original array, then just pick one from this new array.

¿O(1)?