On vous donne un fichier qui contient tous les nombres possibles sur une architecture 32 bits. Il manque 4 numéros dans ce fichier. Trouvez les 4 numéros manquants

Il s'agit d'une question d'entrevue que j'ai rencontrée plusieurs fois, et je ne sais vraiment pas comment la résoudre étant donné que quatre numéros sont manquants. Je connais les algorithmes pour trouver un ou deux nombres manquants, mais je ne vois pas de moyen de généraliser l'un d'eux à quatre.

Que ce soit pour un entretien ou un travail réel, votre première priorité doit être une solution de travail qui a du sens pour vous . Cela habituellement signifie que vous devez offrir la première solution , vous pouvez penser à qui est simple et facile pour vous d'expliquer.

Pour moi, cela signifie trier les chiffres et rechercher les lacunes. Mais je travaille sur des systèmes d'entreprise et des applications Web. Je ne joue pas avec les morceaux et je ne veux pas que mon équipe le fasse!

Si vous interviewez pour un travail de bas niveau, plus proche du métal, le "tri" sera probablement rencontré avec des regards vides. Ils veulent que vous réfléchissiez à l'aise sur les bits et ainsi de suite. Votre première réponse devrait être: «Oh, j'utiliserais un bitmap». (Ou tableau de bits ou ensemble de bits.)

Et puis, de toute façon - même si vous donnez une «mauvaise» solution, si votre intervieweur (ou patron!) Insiste , vous pouvez suggérer des améliorations ou des alternatives, en vous concentrant sur le domaine de préoccupation spécifique du manager.

• RAM sévèrement limitée? Moins de 512 Mo?
  Triez-le sur place. Vous pouvez utiliser une quantité de RAM principalement arbitraire pour optimiser et / ou mettre en mémoire tampon les blocs triés.
• Temps limité?
  Utilisez cette RAM! Le tri est déjà O(n*log(n)). (Ou O (n) pour un tri par nombre entier!)
• Maintenabilité?
  Quoi de plus simple que de trier?!
• Ne démontre pas la connaissance des indicateurs / champs de bits? ( BitSet/ BitMap/ BitArray)
  Bon d'accord ... allez-y et utilisez a BitArraypour signaler les "nombres trouvés". Et puis scannez pour 0.
• Une complexité "en temps réel" prévisible ?
  Utilisez la solution bitmap. C'est une seule passe sur le fichier et une autre passe sur leBitArray/BitSet(pour trouver le0). VoilàO(n), je pense!

Ou peu importe.

Répondez aux préoccupations que vous avez réellement. Résolvez d'abord le problème, en utilisant des solutions naïves si nécessaire. Ne perdez pas le temps de tout le monde à répondre à des préoccupations qui n'existent pas encore.

Puisqu'il s'agit d'un fichier, je suppose que vous êtes autorisé à effectuer plusieurs passes. Créez d'abord un tableau de 256 compteurs, parcourez le fichier et pour chaque numéro incrémentez le compteur indexé comme premier octet du numéro. Lorsque vous avez terminé, la plupart des compteurs doivent être à 2 ^ 24, mais 1 à 4 compteurs doivent avoir des valeurs inférieures. Chacun de ces indices représente un premier octet d'un des nombres manquants (s'il y en a moins de 4, c'est parce que plusieurs nombres manquants partagent le même premier octet).

Pour chacun de ces indices, créez un autre tableau de 256 compteurs et effectuez une deuxième passe sur le fichier. Cette fois, si le premier octet est l'une des valeurs précédentes, incrémentez un compteur dans son tableau en fonction du deuxième octet. Lorsque vous avez terminé, recherchez à nouveau les compteurs inférieurs à 2 ^ 16, et vous aurez le deuxième octet des nombres manquants, chacun correspondant à son premier octet.

Recommencez pour le troisième octet (notez que vous avez besoin d'un maximum de 4 tableaux dans chaque passage, même si chaque octet peut être suivi par jusqu'à 4 octets différents) et pour le quatrième octet, et vous avez trouvé tous les nombres manquants.

Complexité temporelle - Complexité O(n * log n)
spatiale - constante !

Modifier:

En fait, je considérais le n=2^32comme le paramètre, mais le nombre de nombres manquants k=4est aussi un paramètre. En supposant que k<<ncela signifie que la complexité de l'espace est O(k).

Mise à jour:

Juste pour le plaisir (et parce que j'essaie actuellement d'apprendre Rust), je l'ai implémenté dans Rust: https://gist.github.com/idanarye/90a925ebb2ea57de18f03f570f70ea1f . J'ai choisi d'avoir une représentation textuelle, car tout le monde va l'exécuter avec ~ 2 ^ 32 chiffres ...

S'il s'agissait de Java, vous pourriez utiliser un BitSet. Eh bien, deux d'entre eux, car ils ne peuvent pas tout à fait contenir tous les nombres 32 bits. Code squelettique, peut-être buggé:

BitSet bitsetForPositives = new Bitset(2^31);  // obviously not 2^31 but you get the idea
BitSet bitsetForNegatives = new Bitset(2^31);

for (int value: valuesTheyPassInSomehow) {
  if ((value & 0x80000000) == 0)
     bitsetForPositives.set(value );
  else
     bitsetForNegatives.set(value & ~0x80000000);
}

Utilisez ensuite BitSet.nextClearBit()pour trouver qui manque.

Note ajoutée bien plus tard:

Notez qu'avec cet algorithme, il est assez facile d'exécuter la partie chronophage en parallèle . Supposons que le fichier d'origine ait été divisé en quatre parties à peu près égales. Allouez 4 paires de BitSets (2 Go, toujours gérables).

1. Avoir quatre threads, en parallèle, chacun traite un fichier dans sa propre paire de BitSets.
2. Une fois terminé, revenez à un seul thread, ou aux Bitsets (temps trivial), puis appelez nextClearBit quatre fois (également temps assez trivial).

Je m'attendrais à ce que les E / S soient toujours l'étape de limitation de débit, mais si par magie tous les nombres étaient en mémoire, vous pourriez vraiment accélérer les choses.

Cette question peut être résolue en utilisant un tableau de bits (vrai / faux). Cela devrait être la structure la plus efficace pour conserver les réponses de tous les nombres en utilisant l'index du tableau pour savoir si ce nombre particulier a été trouvé.

C #

var bArray = new BitArray(Int32.MaxValue);

//Assume the file has 1 number per line
using (StreamReader sr = File.OpenText(fileName))
{
        string s = String.Empty;
        while ((s = sr.ReadLine()) != null)
        {
            var n = int32.Parse(s);
            bArray[n] = true;
        }
}

Ensuite, parcourez simplement le tableau et pour les valeurs qui sont toujours fausses, elles ne sont pas dans le fichier.

Vous pouvez diviser le fichier en morceaux plus petits, mais j'ai pu allouer un tableau complet de taille maximale int32 (2147483647) sur mon ordinateur portable de 16,0 Go exécutant Windows 7 (64 bits).

Même si je n'exécutais pas 64 bits, je pouvais allouer des tableaux de bits plus petits. Je pré-traiterais le fichier en créant un ensemble de fichiers plus petits, chacun avec une plage de [0-64000] [64001-128000], etc. des nombres qui conviendraient aux ressources environnementales disponibles. Parcourez le gros fichier et écrivez chaque numéro dans son fichier de jeu correspondant. Ensuite, traitez chaque fichier plus petit. Cela prendrait un peu plus de temps en raison de l'étape de prétraitement, mais cela contournerait les limitations de ressources s'il y avait des ressources limitées.

Comme il s'agit d'une question d'entrevue, je montrerais à l'intervieweur une certaine compréhension des contraintes. Que signifie alors "tous les nombres possibles"? Est-ce vraiment 0 ... 2 <(32-1) comme tout le monde le devine? Les architectures 32 bits habituelles peuvent fonctionner avec bien plus que des nombres 32 bits. C'est juste une question de représentation, évidemment.

Doit-il être résolu sur un système 32 bits, ou est-ce plutôt une partie de la restriction sur les nombres? Par exemple, un système 32 bits typique ne pourra pas charger le fichier dans la RAM à la fois. Je mentionnerais également qu'un système 32 bits ne sera souvent pas en mesure d'avoir un fichier contenant tous les nombres en raison de la limitation de la taille du fichier. Eh bien, à moins qu'il n'ait un codage intelligent, comme "Tous les nombres sauf ces quatre", auquel cas le problème est résolu trivialement.

Mais si vous voulez vraiment comprendre la question comme "étant donné un fichier avec tous les nombres de 0 ... 2 ^ (32-1) sauf quelques-uns, donnez-moi ceux qui manquent" (et c'est un gros si !), Alors il existe de nombreuses façons de le résoudre.

Anecdotique mais non réalisable: pour chaque numéro possible, scannez le fichier et voyez s'il s'y trouve.

Avec 512 Mo de RAM et fichier à passage unique: marquez chaque numéro (= bit défini à cet index) lu dans le fichier, puis passez une fois la RAM et voyez ceux qui manquent.

Une approche facile à retenir et à articuler dans une interview serait d'utiliser le fait que si vous regardez tous les nombres en N bits, chaque bit sera défini dans exactement la moitié de ces valeurs et non dans l'autre moitié .

Si vous parcourez toutes les valeurs du fichier et conservez 32 décomptes à la fin, vous vous retrouverez avec 32 valeurs exactement (2 ^ 32/2) ou légèrement inférieures à cette valeur. La différence entre ce maximum (2 ^ 32/2) et le total vous donne le total des bits définis dans chaque position des valeurs manquantes.

Une fois que vous avez cela, vous pouvez déterminer tous les ensembles possibles de 4 valeurs qui pourraient donner ces totaux. Cela étant, vous pouvez ensuite parcourir les valeurs du fichier en vérifiant à nouveau les valeurs qui font partie de ces combinaisons. Lorsque vous en trouvez une, les combinaisons contenant cette valeur sont éliminées en tant que possibilités. Une fois qu'il ne vous reste qu'une seule combinaison possible, vous avez la réponse.

Par exemple, en utilisant un quartet, vous avez les valeurs suivantes:

1010
0110
1111
0111
1101
1001
0100
0101
0001
1011
1100
1110

Le nombre total de bits définis dans chaque position est:

7867

En soustrayant ceux de 8 (4 ^ 2/2), nous obtenons:

1021

Ce qui signifie qu'il existe les ensembles possibles suivants de 4 valeurs:

1000
0000
0011
0010

1010
0001
0010
0000

(pardonne-moi si j'en ai manqué, je fais juste ça de vue)

Et puis en regardant à nouveau les numéros originaux, nous trouvons 1010 tout de suite, ce qui signifie que le premier ensemble était la réponse.

En supposant que le fichier est trié par nombre croissant:

Assurez-vous qu'il contient bien des nombres (2³²-4).
Maintenant, si le fichier était complet (ou si les 4 nombres manquants étaient les 4 derniers), la lecture de n'importe quel mot du fichier à la position N retournerait la valeur correspondante N.

Utilisez une recherche de dichotomie sur les positions [0..2³²-4-1) pour rechercher le premier nombre non attendu X1.
Une fois trouvé le premier nombre manquant, refaites une recherche de dichtotomie sur les positions [X1 .. (2³²-4-1)] pour trouver le deuxième manquant, X2: Cette fois, la lecture d'un mot à la position N devrait retourner la valeur correspondante N-1 s'il n'y avait plus de numéros manquants (puisque vous avez passé un numéro manquant).
Répétez de même pour les deux nombres restants. À la troisième itération, la lecture du mot à la position N doit renvoyer N-2, et à la quatrième, il doit renvoyer N-3.

Avertissement: je n'ai pas testé cela. Mais je pense que cela devrait fonctionner. :)

Maintenant dans la vraie vie, je suis d'accord avec d'autres réponses: les premières questions porteraient sur l'environnement. Avons-nous de la RAM disponible (combien), le fichier se trouve-t-il sur un périphérique de stockage à accès direct, s'agit-il d'une opération ponctuelle (aucune optimisation requise) ou critique (chaque nombre de cycles), avons-nous un utilitaire de tri externe disponible , etc.
Trouvez ensuite un compromis acceptable pour le contexte. Cela montre au moins que vous commencez à analyser le problème avant de rechercher un algorithme.

Comme pour toutes les questions standard, la solution consiste à les rechercher sur Google avant l'entretien.

Cette question et ses variantes ont une réponse «correcte» très précise impliquant XORing tous les nombres. Son censé vous montrer comprendre les index dans les bases de données ou quelque chose. Donc, zéro point pour tout «pourrait fonctionner, mais pas ce qu'il dit sur le papier», répond im afriad.

Du côté positif, il y a un ensemble fini de ces questions, une révision de quelques heures vous fera ressembler à un génie. N'oubliez pas de prétendre que vous travaillez dans votre tête.

Modifier. Ahh il semble que pour 4 il y a une approche différente de XOR

http://books.google.com/books?id=415loiMd_c0C&lpg=PP1&dq=muthukrishnan%20data%20stream%20algorithms&hl=el&pg=PA1#v=onepage&q=muthukrishnan%20data%20stream%20algorithms&f=false

Modifier. Downvoters: Ceci est une solution O (n) de manuel publiée au problème exact indiqué dans le PO.