Create a new element other than 1000 elements of the array

Question

I was asked these questions in an interview. Consider a punch card scenario where each punch card has a 64-bit drawing. I was offered each card as an int , since each int is a set of bits.

In addition, it should be borne in mind that I have an array that already contains 1000 of these cards. I have to generate a new item every time, which is different from the previous 1000 cards. Integers (aka cards) in the array are not necessarily sorted.

Moreover, how would it be possible, the question was for C ++, where does 64 bit int come from and how can I generate this new map from an array, where the element being created differs from all the elements already present in the array?

Answer 1

There are 2 ⁶⁴ 64-bit integers, a number that is so much more than 1000, the simplest solution would be to simply create a random 64-bit number, and then make sure that it is not in the table of already generated numbers. (The likelihood that this is infinitely small, but you can also be sure.)

Since most random number generators do not generate 64-bit values, you leave either writing your own or (much easier) combining the values, for example, generating 8 random bytes and entering memcpy into uint64_t .

As for verifying that the number doesn't exist yet, std::find just fine for one or two new numbers; if you need to do a lot of searching, sorting the table and using binary search is worth it. Or some kind of hash table.

Answer 2

Something may be missing for me, but most of the other answers seem to me too complicated. Just sort the source array and start counting from scratch: if the current counter is in the array, skip it, otherwise you will have the next number. This algorithm is O (n), where n is the number of newly generated numbers: both array sorting and omissions of existing numbers are constants. Here is 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 is the O (n) algorithm:

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

Note. As @amit points below, this will not work if INT64_MAX already in the list.

As far as I know, this is the only way to get O (n). If you want to deal with this (rather important) edge case, then you will have to do some sort of proper sorting or search that will lead you to O (n log n).

Answer 4

@arne is almost there. You need a self-balancing interval tree that can be built in O (n lg n) time.

Then take the top node, which will keep some interval [i, j]. According to the properties of the interval tree, both i-1 and j + 1 are valid candidates for the new key if i = UINT64_MIN or j = UINT64_MAX . If both of them are true, then you saved 2 ^ 64 elements, and you cannot create a new element. Save the new element that takes O (lg n) in the worst case.

Ie: init takes O (n lg n), generates O (lg n). Both are the worst numbers. The most important thing in this approach is that the top node will continue to “grow” (store large intervals) and merge with its successor or predecessor, so the tree will actually be reduced in terms of memory usage, and ultimately the operation time splits into O (1). You also won't waste any numbers, so you can continue to generate until you have 2 ^ 64 of them.

Answer 5

This algorithm has O(N lg N) initialization, O(1) request and O(N) memory usage. I assume that you have an integer type that I will call int64 and that it can represent the integers [0, int64_max] .

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

You now have a list representing numbers that are not in use. You can simply iterate over them to generate new numbers.

Answer 6

I think the way is to use some kind of hashing. Thus, you store your cards in some buckets, based on what allows you to talk about the operation of MOD. Until you create some kind of indexing, you will loop around the entire array.

If you have a look at the implementation of HashSet in java, you can get a hint.

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

Answer 7

You can build a binary tree of already existing elements and go through it until you find a node whose depth is not equal to 64 and has less than two child nodes. Then you can create a “missing” child element node and create a new element. It should be pretty fast, in order of 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: Do not sort the list. Create a new array of length 1000 containing 0..999. Iterate the list and, if any number is in the range 0..999, invalidate it in the new array, replacing the value in the new array with the value of the first element in the list.

Insert: Use an incremental index for the new array. If the value in the new array in this index is not the value of the first element in the list, add it to the list, otherwise check the value from the next position in the new array. When the new array is used, refuel it with 1000..1999 and discard the existing values ​​as described above. Yes, this is a list loop, but it does not need to be done for each insert.

Next to O (1) until the list becomes so large that from time to time its iteration for the invalidity of the new array becomes significant. Perhaps you could reduce this using a new array that grows, perhaps always the size of the list?

Rgds, Martin

Answer 10

Put them in a hash table of size> 1000 and find an empty cell (this is a parking problem). Create a key for this. This, of course, will work better for a larger table. Only 1-bit records are needed for a table.

EDITOR: This is the principle of the pigment hole. A hash function requires "modulo tablesize" (or some other "semi-invertible" 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 about array and number

Since there are 1000 numbers, if we look at their balances from 1001, there will be at least one remainder. We can choose this as our missing number.

So, we save an array of counters: C [1001], which will support the number of integers with the remainder r (when divided by 1001) in C [r].

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

When we move the window, we decrease the counter of the first element (for example, the remainder i), i.e. decrement C [i]. If C [i] vanishes, we add i to the set of numbers. We are updating the array C with the new number being added.

If we need a single number, we simply select a random element from the set 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:

1) Divide the array into numbers equal to and below 1000 and above

2) If all numbers correspond to the bottom section, select 1001 (or any number greater than 1000), and we are done.

3) Otherwise, we know that there must be a number from 1 to 1000, which does not exist in the lower section.

4) Create an array of elements with a size of 1000 bools elements or a 1000 element long bit field or something else and initialize the array for all

5) For each integer in the lower section, use its value as an index in the array / bitfield field and set the corresponding bool to true (i.e., sort by the radix method)

6) Scroll through the array / bitfield and select any index of the unspecified value as the solution

This works in O (n) time, or since we limited everything to 1000, technically it is O (1), but O (n) time and space in general. There are three passes over the data, which is not necessarily the most elegant approach, but the complexity remains O (n).

Answer 13

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

¿O (1)?