Comment trier 400 mil. entiers, où chacun est répété au plus 2 fois?

Étant donné 400 millions d'entiers 32 bits, où chaque entier individuel est répété au maximum deux fois, comment pouvez-vous les trier?Comment trier 400 mil. entiers, où chacun est répété au plus 2 fois?

Ceci dans une interview questions. J'ai proposé d'utiliser une table de comptage avec 2^32 entrées - chaque valeur possible a une entrée, et chaque entrée prend 2 bits. Il suffit de parcourir les entiers et de définir les bits dans l'entrée correspondante selon les besoins.

L'intervieweur a ensuite demandé ce qui se passerait si l'opération set/clear-bit est vraiment coûteuse, par exemple, prend 1ms. Je n'ai pas eu une bonne réponse à cela. J'ai envisagé d'utiliser 11 au lieu de 10 pour représenter 2 - de sorte qu'en augmentant l'occurrence de 1 à 2, il suffit de définir un autre bit au lieu de devoir définir un bit/effacer un bit. Cela ne semble pas être la réponse que recherche l'intervieweur.

Avez-vous une solution plus efficace?

Source

2017-08-12 yangsuli

ce n'est pas vraiment une programmation, plus d'une question de science informatique. Peut-être plus logique de demander cela sur programmers.stackexchange.com qu'ici. –

Comment _hash_ aide-t-il à itérer l'intervalle entre {0, 1, 3000000000, 300000000001, ...}? Et comment savez-vous que votre table de hachage 400M est (relativement) libre de collision? Je considérerais cela comme un nom qui tombe. –

@AkiSuihkonen Mon erreur. Je voulais dire une table de comptage avec 2^32 entrées, essentiellement chaque valeur possible a une entrée – yangsuli

créer deux ensembles de bits ayant 400 mn les bits

mis chaque bit de la première, si vous trouvez le bit est défini et le nombre est AVBL à nouveau, mettez-le dans le second

enfin lire le premier, si son ensemble, vérifiez la seconde et imprimer dans l'ordre

exemple

Bitset1: 10001100 Bitset2: 00001000

valeur finale: 1,5,5,6

Source

2017-08-12 13:23:07 Ramanan

Cela a été écarté comme inefficace par l'enquêteur ... –

Je pense que vous avez besoin de 2^32 bits au lieu de 400m bits ... – yangsuli

devrait vous donner tri par base O (WN) où w = 9 (longueur maximale d'un numéro), en battant l'habituel O (NlogN) où log (400,000) = 19

https://en.wikipedia.org/wiki/Radix_sort

Source

2017-08-15 07:59:43 CodingPill

(Devrait travailler.Est-ce que cela fait une différence que les numéros un ni * unique * ni * répété plus que 2 fois *?) 'log (400.000) = 19' - le nombre concret est indifférent en ce qui concerne l'analyse asymptotique et ses résultats, manquant un ordre de grandeur ou pas. – greybeard

Cela peut avoir quelque chose à voir avec le fait que pour une comparaison, vous n'avez généralement pas besoin de vérifier plus de quelques bits lorsque la population est uniformément répartie. – CodingPill

Comment trier 400 mil. entiers, où chacun est répété au plus 2 fois?

Répondre

Questions connexes