[algorithm] Trouver un nombre entier pas parmi quatre milliards donnés


Answers

Les algorithmes statistiquement informés résolvent ce problème en utilisant moins de passes que les approches déterministes.

Si de très grands entiers sont autorisés, on peut générer un nombre susceptible d'être unique en O (1). Un nombre entier pseudo-aléatoire de 128 bits comme un GUID ne va entrer en collision avec l'un des quatre milliards d'entiers existants dans l'ensemble que dans un cas sur 64 milliards de milliards de milliards.

Si les entiers sont limités à 32 bits, on peut générer un nombre qui est susceptible d'être unique en un seul passage en utilisant beaucoup moins de 10 Mo. La probabilité qu'un nombre entier 32 bits pseudo-aléatoire entre en collision avec l'un des 4 milliards d'entiers existants est d'environ 93% (4e9 / 2 ^ 32). Les probabilités que 1000 entiers pseudo-aléatoires entrent en collision sont inférieures à un sur 12 000 milliards de milliards de milliards (probabilité d'une collision ^ 1000). Donc, si un programme maintient une structure de données contenant 1000 candidats pseudo-aléatoires et itère à travers les entiers connus, en éliminant les correspondances des candidats, il est presque certain de trouver au moins un entier qui n'est pas dans le fichier.

Question

C'est une question d'entrevue:

Étant donné un fichier d'entrée avec quatre milliards d'entiers, fournissez un algorithme pour générer un entier qui n'est pas contenu dans le fichier. Supposons que vous avez 1 Go de mémoire. Suivez ce que vous feriez si vous n'aviez que 10 Mo de mémoire.

Mon analyse:

La taille du fichier est de 4 × 10 9 × 4 octets = 16 GB.

Nous pouvons faire un tri externe, ainsi nous arrivons à connaître la gamme des entiers. Ma question est quelle est la meilleure façon de détecter l'entier manquant dans les grands ensembles entiers triés?

Ma compréhension (après avoir lu toutes les réponses):

En supposant que nous parlons d'entiers 32 bits. Il y a 2 ^ 32 = 4 * 10 9 entiers distincts.

Cas 1: nous avons 1 Go = 1 * 10 9 * 8 bits = 8 milliards de bits de mémoire. Solution: si nous utilisons un bit représentant un entier distinct, cela suffit. nous n'avons pas besoin de trier. La mise en oeuvre:

int radix = 8;
byte[] bitfield = new byte[0xffffffff/radix];
void F() throws FileNotFoundException{
    Scanner in = new Scanner(new FileReader("a.txt"));
    while(in.hasNextInt()){
        int n = in.nextInt();
        bitfield[n/radix] |= (1 << (n%radix));
    }

    for(int i = 0; i< bitfield.lenght; i++){
        for(int j =0; j<radix; j++){
            if( (bitfield[i] & (1<<j)) == 0) System.out.print(i*radix+j);
        }
    }
}

Cas 2: 10 Mo de mémoire = 10 * 10 6 * 8 bits = 80 millions de bits

Solution: For all possible 16-bit prefixes, there are 2^16 number of
integers = 65536, we need 2^16 * 4 * 8 = 2 million bits. We need build
65536 buckets. For each bucket, we need 4 bytes holding all possibilities because
 the worst case is all the 4 billion integers belong to the same bucket.

step1: Build the counter of each bucket through the first pass through the file.
step2: Scan the buckets, find the first one who has less than 65536 hit.
step3: Build new buckets whose high 16-bit prefixes are we found in step2
through second pass of the file
step4: Scan the buckets built in step3, find the first bucket which doesnt
have a hit.

The code is very similar to above one.

Conclusion: Nous diminuons la mémoire en augmentant la passe de fichier.

Une clarification pour ceux qui arrivent en retard: La question, telle que posée, ne dit pas qu'il y a exactement un entier qui n'est pas contenu dans le fichier - du moins ce n'est pas comme la plupart des gens l'interprètent. Beaucoup de commentaires dans le fil de commentaire sont à propos de cette variation de la tâche, cependant. Malheureusement, le commentaire qui l'a introduit dans le fil de commentaires a été plus tard supprimé par son auteur, alors maintenant il semble que les réponses orphelines ont tout simplement mal compris. C'est très confus. Pardon.




As long as we're doing creative answers, here is another one.

Use the external sort program to sort the input file numerically. This will work for any amount of memory you may have (it will use file storage if needed). Read through the sorted file and output the first number that is missing.




Puisque le problème ne spécifie pas que nous devons trouver le plus petit nombre possible qui ne soit pas dans le fichier, nous pourrions simplement générer un nombre plus long que le fichier d'entrée lui-même. :)




Si ce sont des entiers de 32 bits (probablement du choix de ~ 4 milliards de nombres proches de 2 ^ 32), votre liste de 4 milliards de nombres occupera au maximum 93% des entiers possibles (4 * 10 ^ 9 / (2 ^ 32)). Donc, si vous créez un tableau de bits de 2 ^ 32 bits avec chaque bit initialisé à zéro (ce qui prendra 2 ^ 29 octets ~ 500 Mo de RAM, rappelez-vous un octet = 2 ^ 3 bits = 8 bits), lisez votre liste entière et pour chaque int définir l'élément de tableau de bits correspondant de 0 à 1; puis lisez votre tableau de bits et renvoyez le premier bit qui est toujours 0.

Dans le cas où vous avez moins de RAM (~ 10 Mo), cette solution doit être légèrement modifiée. 10 Mo ~ 83886080 bits est encore suffisant pour faire un tableau de bits pour tous les nombres compris entre 0 et 83886079. Vous pouvez donc lire votre liste d'ints; et n'enregistre que les # compris entre 0 et 83886079 dans votre tableau de bits. Si les numéros sont distribués au hasard avec une probabilité écrasante (il diffère de 100% par environ 10^-2592069 ), vous trouverez un int). En fait, si vous choisissez seulement les numéros 1 à 2048 (avec seulement 256 octets de RAM) vous trouverez toujours un nombre manquant un pourcentage écrasant (99.99999999999999999999999999999999999999999999999999999999999995%) du temps.

Mais disons plutôt que d'avoir environ 4 milliards de numéros; vous aviez quelque chose comme 2 ^ 32 - 1 numéros et moins de 10 Mo de RAM; donc toute petite plage d'ints a seulement une petite possibilité de ne pas contenir le nombre.

Si vous aviez la garantie que chaque int dans la liste était unique, vous pouvez additionner les nombres et soustraire la somme avec un # manquant à la somme complète (1/2) (2 ^ 32) (2 ^ 32 - 1) = 9223372034707292160 à trouver l'int manquant. Cependant, si un int s'est produit deux fois, cette méthode échouera.

Cependant, vous pouvez toujours diviser et conquérir. Une méthode naïve consisterait à lire le tableau et à compter le nombre de nombres compris dans la première moitié (0 à 2 ^ 31-1) et dans la seconde moitié (2 ^ 31, 2 ^ 32). Puis choisissez la gamme avec moins de nombres et répétez la division de cette gamme de moitié. (Dites s'il y avait deux nombres de moins dans (2 ^ 31, 2 ^ 32) alors votre prochaine recherche compterait les nombres dans la gamme (2 ^ 31, 3 * 2 ^ 30-1), (3 * 2 ^ 30, 2 ^ 32) Continuez à répéter jusqu'à ce que vous trouviez une plage avec des nombres nuls et que vous ayez votre réponse.Vous devriez prendre O (lg N) ~ 32 lectures à travers le tableau.

Cette méthode était inefficace. Nous n'utilisons que deux entiers dans chaque étape (ou environ 8 octets de RAM avec un entier de 4 octets (32 bits)). Une meilleure méthode serait de diviser en sqrt (2 ^ 32) = 2 ^ 16 = 65536 bins, chacun avec 65536 numéros dans une corbeille. Chaque bin nécessite 4 octets pour stocker son compte, vous avez donc besoin de 2 ^ 18 octets = 256 Ko. Donc bin 0 est (0 à 65535 = 2 ^ 16-1), bin 1 est (2 ^ 16 = 65536 à 2 * 2 ^ 16-1 = 131071), bin 2 est (2 * 2 ^ 16 = 131072 à 3 * 2 ^ 16-1 = 196607). En python, vous auriez quelque chose comme:

import numpy as np
nums_in_bin = np.zeros(65536, dtype=np.uint32)
for N in four_billion_int_array:
    nums_in_bin[N // 65536] += 1
for bin_num, bin_count in enumerate(nums_in_bin):
    if bin_count < 65536:
        break # we have found an incomplete bin with missing ints (bin_num)

Lisez la liste des entiers ~ 4 milliards; et comptez combien d'ints tombent dans chacun des 2 ^ 16 bins et trouvez un incomplete_bin qui n'a pas tous les 65536 nombres. Ensuite, vous lisez à nouveau la liste des 4 milliards d'entiers; mais cette fois-ci, remarquez seulement quand les entiers sont dans cette gamme; retournant un peu quand vous les trouvez.

del nums_in_bin # allow gc to free old 256kB array
from bitarray import bitarray
my_bit_array = bitarray(65536) # 32 kB
my_bit_array.setall(0)
for N in four_billion_int_array:
    if N // 65536 == bin_num:
        my_bit_array[N % 65536] = 1
for i, bit in enumerate(my_bit_array):
    if not bit:
        print bin_num*65536 + i
        break



If you don't assume the 32-bit constraint, just return a randomly generated 64-bit number (or 128-bit if you're a pessimist). The chance of collision is 1 in 2^64/(4*10^9) = 4611686018.4 (roughly 1 in 4 billion). You'd be right most of the time!

(Joking... kind of.)




Cela peut être résolu dans très peu d'espace en utilisant une variante de recherche binaire.

  1. Commencez avec la plage autorisée de nombres, 0 à 4294967295 .

  2. Calculez le point milieu.

  3. Parcourez le fichier en boucle, en comptant combien de nombres étaient égaux, inférieurs ou supérieurs à la valeur du point central.

  4. Si aucun chiffre n'était égal, vous avez terminé. Le numéro de milieu est la réponse.

  5. Sinon, choisissez la plage ayant le moins de numéros et répétez l'étape 2 avec cette nouvelle plage.

Cela nécessitera jusqu'à 32 balayages linéaires à travers le fichier, mais il utilisera seulement quelques octets de mémoire pour stocker la gamme et les comptes.

C'est essentiellement la même chose que la solution de Henning , sauf qu'elle utilise deux bacs au lieu de 16k.




I will answer the 1 GB version:

There is not enough information in the question, so I will state some assumptions first:

The integer is 32 bits with range -2,147,483,648 to 2,147,483,647.

Pseudo-code:

var bitArray = new bit[4294967296];  // 0.5 GB, initialized to all 0s.

foreach (var number in file) {
    bitArray[number + 2147483648] = 1;   // Shift all numbers so they start at 0.
}

for (var i = 0; i < 4294967296; i++) {
    if (bitArray[i] == 0) {
        return i - 2147483648;
    }
}



For the 10 MB memory constraint:

  1. Convert the number to its binary representation.
  2. Create a binary tree where left = 0 and right = 1.
  3. Insert each number in the tree using its binary representation.
  4. If a number has already been inserted, the leafs will already have been created.

When finished, just take a path that has not been created before to create the requested number.

4 billion number = 2^32, meaning 10 MB might not be sufficient.

MODIFIER

An optimization is possible, if two ends leafs have been created and have a common parent, then they can be removed and the parent flagged as not a solution. This cuts branches and reduces the need for memory.

EDIT II

There is no need to build the tree completely too. You only need to build deep branches if numbers are similar. If we cut branches too, then this solution might work in fact.




I think this is a solved problem (see above), but there's an interesting side case to keep in mind because it might get asked:

If there are exactly 4,294,967,295 (2^32 - 1) 32-bit integers with no repeats, and therefore only one is missing, there is a simple solution.

Start a running total at zero, and for each integer in the file, add that integer with 32-bit overflow (effectively, runningTotal = (runningTotal + nextInteger) % 4294967296). Once complete, add 4294967296/2 to the running total, again with 32-bit overflow. Subtract this from 4294967296, and the result is the missing integer.

The "only one missing integer" problem is solvable with only one run, and only 64 bits of RAM dedicated to the data (32 for the running total, 32 to read in the next integer).

Corollary: The more general specification is extremely simple to match if we aren't concerned with how many bits the integer result must have. We just generate a big enough integer that it cannot be contained in the file we're given. Again, this takes up absolutely minimal RAM. See the pseudocode.

# Grab the file size
fseek(fp, 0L, SEEK_END);
sz = ftell(fp);
# Print a '2' for every bit of the file.
for (c=0; c<sz; c++) {
  for (b=0; b<4; b++) {
    print "2";
  }
}



Check the size of the input file, then output any number which is too large to be represented by a file that size. This may seem like a cheap trick, but it's a creative solution to an interview problem, it neatly sidesteps the memory issue, and it's technically O(n).

void maxNum(ulong filesize)
{
    ulong bitcount = filesize * 8; //number of bits in file

    for (ulong i = 0; i < bitcount; i++)
    {
        Console.Write(9);
    }
}

Should print 10 bitcount - 1 , which will always be greater than 2 bitcount . Technically, the number you have to beat is 2 bitcount - (4 * 10 9 - 1) , since you know there are (4 billion - 1) other integers in the file, and even with perfect compression they'll take up at least one bit each.




S'il n'y a pas de limite de taille, le moyen le plus rapide est de prendre la longueur du fichier et de générer la longueur du fichier + 1 nombre de chiffres aléatoires (ou simplement "11111 ..." s). Avantage: vous n'avez même pas besoin de lire le fichier, et vous pouvez minimiser l'utilisation de la mémoire presque à zéro. Inconvénient: Vous allez imprimer des milliards de chiffres.

Cependant, si le seul facteur était la minimisation de l'utilisation de la mémoire, et rien d'autre n'est important, ce serait la solution optimale. Il pourrait même vous obtenir un prix «pire abus des règles».




  • The simplest approach is to find the minimum number in the file, and return 1 less than that. This uses O(1) storage, and O(n) time for a file of n numbers. However, it will fail if number range is limited, which could make min-1 not-a-number.

  • The simple and straightforward method of using a bitmap has already been mentioned. That method uses O(n) time and storage.

  • A 2-pass method with 2^16 counting-buckets has also been mentioned. It reads 2*n integers, so uses O(n) time and O(1) storage, but it cannot handle datasets with more than 2^16 numbers. However, it's easily extended to (eg) 2^60 64-bit integers by running 4 passes instead of 2, and easily adapted to using tiny memory by using only as many bins as fit in memory and increasing the number of passes correspondingly, in which case run time is no longer O(n) but instead is O(n*log n).

  • The method of XOR'ing all the numbers together, mentioned so far by rfrankel and at length by ircmaxell answers the question asked in #35185 , as ltn100 pointed out. It uses O(1) storage and O(n) run time. If for the moment we assume 32-bit integers, XOR has a 7% probability of producing a distinct number. Rationale: given ~ 4G distinct numbers XOR'd together, and ca. 300M not in file, the number of set bits in each bit position has equal chance of being odd or even. Thus, 2^32 numbers have equal likelihood of arising as the XOR result, of which 93% are already in file. Note that if the numbers in file aren't all distinct, the XOR method's probability of success rises.




Si vous avez un nombre entier manquant dans la plage [0, 2 ^ x - 1] alors juste xor les ensemble. Par exemple:

>>> 0 ^ 1 ^ 3
2
>>> 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ 6 ^ 7
5

(Je sais que cela ne répond pas exactement à la question, mais c'est une bonne réponse à une question très similaire.)




You can use bit flags to mark whether an integer is present or not.

After traversing the entire file, scan each bit to determine if the number exists or not.

Assuming each integer is 32 bit, they will conveniently fit in 1 GB of RAM if bit flagging is done.




Ils cherchent peut-être à voir si vous avez entendu parler d'un filtre Bloom probabiliste qui peut déterminer très efficacement si une valeur ne fait pas partie d'un grand ensemble (mais peut seulement déterminer avec une probabilité élevée qu'il est membre de l'ensemble).




Links



Tags

algorithm