Ecrire un programme pour trouver 100 plus grands nombres sur un tableau de 1 milliard de nombres

J’ai récemment assisté à une interview où on m’a demandé “d’écrire un programme pour trouver les 100 plus gros nombres parmi un ensemble de 1 milliard de numéros”.

Je n’ai pu que donner une solution de force brute qui consistait à sortinger le tableau en complexité temporelle O (nlogn) et à prendre les 100 derniers chiffres.

Arrays.sort(array); 

L’interviewer cherchait une meilleure complexité temporelle, j’ai essayé quelques autres solutions mais n’ai pas réussi à lui répondre. Existe-t-il une meilleure solution de complexité temporelle?

Vous pouvez conserver une queue prioritaire des 100 plus gros nombres, parcourir les milliards de numéros, chaque fois que vous rencontrez un nombre supérieur au plus petit nombre de la file (en tête de file), supprimez la tête de la file et ajoutez le nouveau numéro à la queue.

EDIT: comme Dev l’a noté, avec une queue prioritaire implémentée avec un tas, la complexité de l’insertion dans la queue est O(logN)

Dans le pire des cas, vous obtenez des billion log 2 (100) ce qui est mieux que des billion log 2 (billion)

En général, si vous avez besoin des plus grands nombres K d’un ensemble de N nombres, la complexité est O(NlogK) plutôt que O(NlogN) , cela peut être très significatif lorsque K est très petit comparé à N.

EDIT2:

Le temps attendu de cet algorithme est assez intéressant, car à chaque itération une insertion peut ou non avoir lieu. La probabilité que le numéro soit inséré dans la queue correspond à la probabilité qu’une variable aléatoire soit supérieure à au moins iK variables aléatoires provenant de la même dissortingbution (les premiers k numéros sont automatiquement ajoutés à la queue). Nous pouvons utiliser les statistiques de commande (voir lien ) pour calculer cette probabilité. Par exemple, supposons que les nombres ont été choisis au hasard de manière uniforme parmi {0, 1} , la valeur attendue du (iK) e nombre (sur i nombres) est (ik)/i et la probabilité qu’une variable aléatoire soit plus grande que cela la valeur est 1-[(ik)/i] = k/i .

Ainsi, le nombre d’insertions attendu est:

entrer la description de l'image ici

Et le temps d’exécution prévu peut être exprimé comme:

entrer la description de l'image ici

( k temps pour générer la queue avec les premiers k éléments, puis nk comparaisons, et le nombre prévu d’insertions comme décrit ci-dessus, chacun prend une moyenne log(k)/2 fois)

Notez que lorsque N est très grand comparé à K , cette expression est beaucoup plus proche de n que de NlogK . Ceci est quelque peu intuitif, car dans le cas de la question, même après 10000 itérations (ce qui est très petit comparé à un milliard), les chances qu’un numéro soit inséré dans la queue sont très faibles.

Si cela est demandé dans une interview, je pense que l’intervieweur veut probablement voir votre processus de résolution de problèmes, pas seulement votre connaissance des algorithmes.

La description est assez générale alors peut-être que vous pouvez lui demander la scope ou la signification de ces chiffres pour clarifier le problème. Faire cela peut impressionner un intervieweur. Si, par exemple, ces chiffres correspondent à l’âge des personnes dans un pays (par exemple en Chine), le problème est beaucoup plus facile. En supposant raisonnablement que personne n’est âgé de plus de 200 ans, vous pouvez utiliser un tableau int de taille 200 (peut-être 201) pour compter le nombre de personnes du même âge en une seule itération. Ici, l’indice signifie l’âge. Après cela, c’est un morceau de gâteau de trouver 100 plus grand nombre. Au fait, cet algo s’appelle le sorting par comptage .

Quoi qu’il en soit, rendre la question plus précise et plus claire est bon pour une entrevue.

Vous pouvez parcourir les nombres qui prennent O (n)

Chaque fois que vous trouvez une valeur supérieure au minimum actuel, ajoutez la nouvelle valeur à une queue circulaire de taille 100.

Le min de cette queue circulaire est votre nouvelle valeur de comparaison. Continuez à append à cette queue. S’il est plein, extrayez le minimum de la queue.

Je me suis rendu compte que ceci est marqué avec «algorithme», mais jettera d’autres options, car il devrait probablement également être étiqueté «interview».

Quelle est la source des 1 milliard de numéros? Si c’est une firebase database, alors ‘select value from table order by valeur desc limit 100’ ferait bien le travail – il pourrait y avoir des différences de dialecte.

Est-ce un cas isolé ou quelque chose qui sera répété? Si répété, à quelle fréquence? Si c’est un one-off et que les données sont dans un fichier, alors ‘cat srcfile | sortinger (options au besoin) | head -100 ‘vous permettra d’accomplir rapidement un travail productif que vous êtes payé pour faire face à cette corvée sortingviale.

Si cela se répète, vous conseillerez de choisir une approche décente pour obtenir la réponse initiale et de stocker / mettre en cache les résultats afin de pouvoir continuellement signaler les 100 premiers.

Enfin, il y a cette considération. Êtes-vous à la recherche d’un emploi de débutant et d’une entrevue avec un gestionnaire de geek ou un futur collègue? Si c’est le cas, alors vous pouvez lancer toutes sortes d’approches décrivant les avantages et inconvénients techniques relatifs. Si vous recherchez un emploi plus managérial, alors abordez-le comme le ferait un gestionnaire, soucieux des coûts de développement et de maintenance de la solution, et dites «merci beaucoup» et partez si l’enquêteur veut se concentrer sur le sortingvia de CS. . Il est peu probable que vous et vous ayez un grand potentiel d’avancement.

Bonne chance pour la prochaine interview.

Vous pouvez utiliser l’ algorithme de sélection rapide pour trouver le numéro à l’index (par ordre) [milliards-101], puis parcourir les numéros et trouver les nombres qui se trouvent dans ce numéro.

 array={...the billion numbers...} result[100]; pivot=QuickSelect(array,billion-101);//O(N) for(i=0;i=pivot) result.add(array[i]); 

Cet algorithme Time est: 2 XO (N) = O (N) (performance moyenne des observations)

La deuxième option, comme Thomas Jungblut, est la suivante:

Utiliser Heap en construisant le tas MAX prendra O (N), alors les 100 premiers nombres maximum seront en haut du tas, il vous suffit de les sortir du tas (100 XO (Log (N)).

Cet algorithme Time est: O (N) + 100 XO (Log (N)) = O (N)

Ma réaction immédiate à cela serait d’utiliser un tas, mais il est possible d’utiliser QuickSelect sans conserver toutes les valeurs d’entrée à la fois.

Créez un tableau de taille 200 et remplissez-le avec les 200 premières valeurs d’entrée. Exécutez QuickSelect et supprimez les 100 plus faibles, vous laissant 100 places libres. Lisez les 100 valeurs d’entrée suivantes et exécutez à nouveau QuickSelect. Continuez jusqu’à ce que vous ayez parcouru l’intégralité de l’entrée en lots de 100.

À la fin, vous avez les 100 meilleures valeurs. Pour N valeurs, vous avez exécuté QuickSelect environ N / 100 fois. Chaque Quickselect coûte environ 200 fois une certaine constante, le coût total est donc 2N fois plus constant. Cela semble linéaire dans la taille de l’entrée, quelle que soit la taille du paramètre que je câble à 100 dans cette explication.

Bien que l’autre solution de sélection rapide ait été abaissée, il n’en rest pas moins que quickselect trouvera la solution plus rapidement qu’avec une queue de taille 100. Quickselect a un temps de fonctionnement attendu de 2n + o (n), en termes de comparaisons. Une mise en œuvre très simple serait

 array = input array of length n r = Quickselect(array,n-100) result = array of length 100 for(i = 1 to n) if(array[i]>r) add array[i] to result 

Cela prendra 3n + o (n) comparaisons en moyenne. De plus, cela peut être rendu plus efficace en utilisant le fait que quickselect laissera les 100 plus gros éléments du tableau dans les 100 emplacements les plus à droite. Donc, en fait, le temps de fonctionnement peut être amélioré à 2n + o (n).

Il y a le problème que cela est la durée d’exécution attendue, et pas le pire des cas, mais en utilisant une stratégie de sélection de pivot décent (par exemple choisir 21 éléments au hasard et choisir la médiane de ces 21 comme pivot), alors le nombre de comparaisons peut être garanti avec une forte probabilité d’être au plus (2 + c) n pour une constante arbitrairement petite c.

En fait, en utilisant une stratégie d’échantillonnage optimisée (par exemple, échantillonner des éléments sqrt (n) au hasard et choisir le 99e centile), le temps d’exécution peut être réduit à (1 + c) n + o (n) (en supposant que K, le nombre d’éléments à sélectionner est o (n)).

D’un autre côté, l’utilisation d’une queue de taille 100 nécessitera des comparaisons O (log (100) n), et la base de journalisation 2 de 100 est approximativement égale à 6,6.

Si nous pensons à ce problème dans le sens plus abstrait de choisir les plus grands éléments K dans un tableau de taille N, où K = o (N) mais K et N vont tous deux à l’infini, alors la durée de la version quickselect sera O (N) et la version de la queue seront O (N log K), donc dans ce sens, quickselect est également asymptotiquement supérieur.

Dans les commentaires, il a été mentionné que la solution de queue s’exécutera à l’heure prévue N ​​+ K log N sur une entrée aléatoire. Bien entendu, l’hypothèse de la saisie aléatoire n’est jamais valide à moins que la question ne l’indique explicitement. La solution de queue pourrait être amenée à traverser le tableau dans un ordre aléatoire, mais cela entraînerait le coût supplémentaire de N appels à un générateur de nombres aléatoires et permuterait le tableau d’entrée entier ou allouer un nouveau tableau de longueur N indices aléatoires.

Si le problème ne vous permet pas de déplacer les éléments du tableau d’origine et que le coût de l’allocation de mémoire est élevé, la duplication du tableau n’est pas une option, c’est une autre affaire. Mais ssortingctement en termes de temps d’exécution, c’est la meilleure solution.

prenez les 100 premiers chiffres du milliard et sortingez-les. Maintenant, il suffit de parcourir le milliard, si le numéro de source est supérieur au plus petit de 100, insérer dans l’ordre de sorting. Ce que vous obtenez avec quelque chose de plus proche de O (n) que de la taille de l’ensemble.

Deux options:

(1) tas (priorityQueue)

Maintenez un min-tas de taille 100. Parcourez le tableau. Une fois que l’élément est plus petit que le premier élément dans le tas, remplacez-le.

 InSERT ELEMENT INTO HEAP: O(log100) compare the first element: O(1) There are n elements in the array, so the total would be O(nlog100), which is O(n) 

(2) Modèle avec réduction de la carte.

Ceci est très similaire à l’exemple de compte de mots dans hadoop. Travail sur carte: comptez la fréquence ou les heures de chaque élément. Réduire: récupère le premier élément K

En général, je donnerais deux réponses au recruteur. Donnez-leur ce qu’ils veulent. Bien sûr, la réduction de la cartographie serait un travail difficile car vous devez connaître tous les parameters exacts. Pas de mal à le pratiquer. Bonne chance.

Une solution très simple consisterait à parcourir 100 fois le tableau. Qui est O(n) .

Chaque fois que vous extrayez le plus grand nombre (et changez sa valeur à la valeur minimale, de sorte que vous ne le voyiez pas dans la prochaine itération, ou gardez une trace des index des réponses précédentes (en gardant une trace des index du tableau original) multiple du même numéro)). Après 100 itérations, vous avez les 100 plus grands nombres.

Inspiré par la réponse de @ron teller, voici un programme C barebone pour faire ce que vous voulez.

 #include  #include  #define TOTAL_NUMBERS 1000000000 #define N_TOP_NUMBERS 100 int compare_function(const void *first, const void *second) { int a = *((int *) first); int b = *((int *) second); if (a > b){ return 1; } if (a < b){ return -1; } return 0; } int main(int argc, char ** argv) { if(argc != 2){ printf("please supply a path to a binary file containing 1000000000" "integers of this machine's wordlength and endianness\n"); exit(1); } FILE * f = fopen(argv[1], "r"); if(!f){ exit(1); } int top100[N_TOP_NUMBERS] = {0}; int sorts = 0; for (int i = 0; i < TOTAL_NUMBERS; i++){ int number; int ok; ok = fread(&number, sizeof(int), 1, f); if(!ok){ printf("not enough numbers!\n"); break; } if(number > top100[0]){ sorts++; top100[0] = number; qsort(top100, N_TOP_NUMBERS, sizeof(int), compare_function); } } printf("%d sorts made\n" "the top 100 integers in %s are:\n", sorts, argv[1] ); for (int i = 0; i < N_TOP_NUMBERS; i++){ printf("%d\n", top100[i]); } fclose(f); exit(0); } 

Sur ma machine (Core i3 avec un SSD rapide), il faut 25 secondes et 1724 sortes. J'ai généré un fichier binary avec dd if=/dev/urandom/ count=1000000000 bs=1 pour cette exécution.

De toute évidence, il y a des problèmes de performance avec la lecture de seulement 4 octets à la fois - à partir du disque, mais c'est par exemple dans l'intérêt de l'utilisateur. Sur le plan positif, très peu de mémoire est nécessaire.

La solution la plus simple consiste à parsingr le grand tableau à un milliard de numéros et à conserver les 100 plus grandes valeurs trouvées jusqu’à présent dans un petit tampon de tableau sans aucun sorting et à mémoriser la plus petite valeur de ce tampon. J’ai d’abord pensé que cette méthode avait été proposée par fordprefect mais dans un commentaire, il a dit qu’il supposait que la structure de données à 100 numéros était implémentée en tant que tas. Chaque fois qu’un nouveau nombre est trouvé, plus grand que le minimum dans le tampon est remplacé par la nouvelle valeur trouvée et le tampon est à nouveau recherché pour le minimum actuel. Si les nombres en milliards de nombres sont dissortingbués aléatoirement la plupart du temps, la valeur du grand tableau est comparée au minimum du petit tableau et rejetée. Seulement pour une très petite fraction du nombre, la valeur doit être insérée dans le petit tableau. Donc, la différence de manipulation de la structure de données contenant les petits nombres peut être négligée. Pour un petit nombre d’éléments, il est difficile de déterminer si l’utilisation d’une queue prioritaire est en réalité plus rapide que l’utilisation de mon approche naïve.

Je veux estimer le nombre d’insertions dans la petite mémoire tampon de 100 éléments lorsque le tableau d’éléments 10 ^ 9 est analysé. Le programme parsing les 1000 premiers éléments de ce grand tableau et doit insérer au maximum 1000 éléments dans le tampon. Le tampon contient 100 éléments parmi les 1000 éléments analysés, soit 0,1 de l’élément analysé. Nous supposons donc que la probabilité qu’une valeur du grand tableau soit supérieure au minimum actuel du tampon est d’environ 0,1. Un tel élément doit être inséré dans le tampon. Maintenant, le programme parsing les 10 ^ 4 éléments suivants du grand tableau. Parce que le minimum de la mémoire tampon augmente à chaque fois qu’un nouvel élément est inséré. Nous avons estimé que le rapport des éléments plus grands que notre minimum actuel est d’environ 0,1 et qu’il y a donc 0,1 * 10 ^ 4 = 1000 éléments à insérer. En fait, le nombre attendu d’éléments insérés dans le tampon sera plus petit. Après l’parsing de cette fraction de 10 ^ 4 éléments, la fraction des nombres dans le tampon sera d’environ 0,01 des éléments analysés jusqu’à présent. Ainsi, lors du balayage des 10 5 5 prochains chiffres, nous supposons que pas plus de 0,01 * 10 ^ 5 = 1000 seront insérés dans le tampon. En continuant cette argumentation, nous avons inséré environ 7000 valeurs après avoir balayé 1000 + 10 ^ 4 + 10 ^ 5 + … + 10 ^ 9 ~ 10 ^ 9 éléments du grand tableau. Donc, lors de la numérisation d’un tableau avec 10 ^ 9 éléments de taille aléatoire, nous ne prévoyons pas plus de 10 ^ 4 (= 7000 arrondis) insertions dans le tampon. Après chaque insertion dans le tampon, le nouveau minimum doit être trouvé. Si le tampon est un tableau simple, nous avons besoin de 100 comparaisons pour trouver le nouveau minimum. Si le tampon est une autre structure de données (comme un tas), nous avons besoin d’au moins 1 comparaison pour trouver le minimum. Pour comparer les éléments du grand tableau, nous avons besoin de 10 ^ 9 comparaisons. Donc, dans l’ensemble, nous avons besoin d’environ 10 ^ 9 + 100 * 10 ^ 4 = 1.001 * 10 ^ 9 comparaisons lorsque vous utilisez un tableau comme tampon et au moins 1.000 * 10 ^ 9 comparaisons lorsque vous utilisez un autre type de structure de données (comme un tas) . Donc, l’utilisation d’un tas n’apporte qu’un gain de 0,1% si les performances sont déterminées par le nombre de comparaisons. Mais quelle est la différence de temps d’exécution entre l’insertion d’un élément dans un tas de 100 éléments et le remplacement d’un élément dans un tableau de 100 éléments et la recherche de son nouveau minimum?

  • Au niveau théorique: combien de comparaisons sont nécessaires pour l’insertion dans un tas. Je sais que c’est O (log (n)) mais quelle est la taille du facteur constant? je

  • Au niveau de la machine: quel est l’impact de la mise en cache et de la prédiction de twig sur le temps d’exécution d’un segment de segment et d’une recherche linéaire dans un tableau.

  • Au niveau de l’implémentation: Quels coûts supplémentaires sont cachés dans une structure de données de tas fournie par une bibliothèque ou un compilateur?

Je pense qu’il faut répondre à certaines des questions avant d’essayer d’estimer la différence réelle entre les performances d’un segment de 100 éléments ou d’un tableau de 100 éléments. Il serait donc judicieux de faire une expérience et de mesurer la performance réelle.

  Although in this question we should search for top 100 numbers, I will generalize things and write x. Still, I will treat x as constant value. 

Algorithme Biggest x éléments de n:

Je vais appeler la valeur de retour LIST . C’est un ensemble de x éléments (à mon avis, cela devrait être une liste liée)

  • Les premiers x éléments sont pris dans le pool “comme ils viennent” et sortingés dans la liste (ceci est fait dans le temps constant car x est traité comme une constante – O (x log (x)) temps)
  • Pour chaque élément suivant, nous vérifions s’il est plus grand que le plus petit élément de la LISTE et, si tel est le cas, sortons le plus petit et insérons l’élément actuel dans la LISTE. Étant donné que cette liste est ordonnée, chaque élément devrait trouver sa place dans le temps logarithmique (recherche binary) et comme il est ordonné, l’insertion de liste ne pose aucun problème. Chaque étape est également effectuée à temps constant (heure O (log (x))).

Alors, quel est le pire scénario?

x log (x) + (nx) (log (x) +1) = nlog (x) + n – x

Donc, c’est O (n) temps pour le pire des cas. Le +1 est la vérification si le nombre est supérieur au plus petit du LISTE. Le temps prévu pour un cas moyen dépendra de la dissortingbution mathématique de ces n éléments.

Améliorations possibles

Cet algorithme peut être légèrement amélioré dans le pire des cas, mais à mon humble avis (je ne peux pas prouver cette affirmation), cela dégradera le comportement moyen. Le comportement asymptotique sera le même.

L’amélioration de cet algorithme sera que nous ne vérifierons pas si l’élément est plus grand que le plus petit. Pour chaque élément, nous essayerons de l’insérer et si celui-ci est plus petit que le plus petit, nous le négligerons. Bien que cela puisse paraître absurde si nous ne considérons que le pire scénario, nous aurons

x log(x) + (nx)log(x) = nlog(x)

operations.

For this use case I don’t see any further improvements. Yet you must ask yourself – what if I have to do this more than log(n) times and for different x-es? Obviously we would sort that array in O(n log(n)) and take our x element whenever we need them.

This question would be answered with N log(100) complexity (instead of N log N) with just one line of C++ code.

  std::vector myvector = ...; // Define your 1 billion numbers. // Assumed integer just for concreteness std::partial_sort (myvector.begin(), myvector.begin()+100, myvector.end()); 

The final answer would be a vector where the first 100 elements are guaranteed to be the 100 biggest numbers of you array while the remaining elements are unordered

C++ STL (standard library) is quite handy for this kind of problems.

Note: I am not saying that this is the optimal solution, but it would have saved your interview.

The simple solution would be using a priority queue, adding the first 100 numbers to the queue and keeping track of the smallest number in the queue, then iterating through the other billion numbers, and each time we find one that is larger than the largest number in the priority queue, we remove the smallest number, add the new number, and again keep track of the smallest number in the queue.

If the numbers were in random order, this would work beautiful because as we iterate through a billion random numbers, it would be very rare that the next number is among the 100 largest so far. But the numbers might not be random. If the array was already sorted in ascending order then we would always insert an element to the priority queue.

So we pick say 100,000 random numbers from the array first. To avoid random access which might be slow, we add say 400 random groups of 250 consecutive numbers. With that random selection, we can be quite sure that very few of the remaining numbers are in the top hundred, so the execution time will be very close to that of a simple loop comparing a billion numbers to some maximum value.

Finding the top 100 out of a billion numbers is best done using min-heap of 100 elements.

First prime the min-heap with the first 100 numbers encountered. min-heap will store the smallest of the first 100 numbers at the root (top).

Now as you go along the rest of the numbers only compare them with the root (smallest of the 100).

If the new number encountered is larger than root of min-heap replace the root with that number otherwise ignore it.

As part of the insertion of the new number in min-heap the smallest number in the heap will come to the top (root).

Once we have gone through all the numbers we will have the largest 100 numbers in the min-heap.

I have written up a simple solution in Python in case anyone is interestd. It uses the bisect module and a temporary return list which it keeps sorted. This is similar to a priority queue implementation.

 import bisect def kLargest(A, k): '''returns list of k largest integers in A''' ret = [] for i, a in enumerate(A): # For first k elements, simply construct sorted temp list # It is treated similarly to a priority queue if i < k: bisect.insort(ret, a) # properly inserts a into sorted list ret # Iterate over rest of array # Replace and update return array when more optimal element is found else: if a > ret[0]: del ret[0] # pop min element off queue bisect.insort(ret, a) # properly inserts a into sorted list ret return ret 

Usage with 100,000,000 elements and worst-case input which is a sorted list:

 >>> from so import kLargest >>> kLargest(range(100000000), 100) [99999900, 99999901, 99999902, 99999903, 99999904, 99999905, 99999906, 99999907, 99999908, 99999909, 99999910, 99999911, 99999912, 99999913, 99999914, 99999915, 99999916, 99999917, 99999918, 99999919, 99999920, 99999921, 99999922, 99999923, 99999924, 99999925, 99999926, 99999927, 99999928, 99999929, 99999930, 99999931, 99999932, 99999933, 99999934, 99999935, 99999936, 99999937, 99999938, 99999939, 99999940, 99999941, 99999942, 99999943, 99999944, 99999945, 99999946, 99999947, 99999948, 99999949, 99999950, 99999951, 99999952, 99999953, 99999954, 99999955, 99999956, 99999957, 99999958, 99999959, 99999960, 99999961, 99999962, 99999963, 99999964, 99999965, 99999966, 99999967, 99999968, 99999969, 99999970, 99999971, 99999972, 99999973, 99999974, 99999975, 99999976, 99999977, 99999978, 99999979, 99999980, 99999981, 99999982, 99999983, 99999984, 99999985, 99999986, 99999987, 99999988, 99999989, 99999990, 99999991, 99999992, 99999993, 99999994, 99999995, 99999996, 99999997, 99999998, 99999999] 

It took about 40 seconds to calculate this for 100,000,000 elements so I’m scared to do it for 1 billion. To be fair though, I was feeding it the worst-case input (ironically an array that is already sorted).

I see a lot of O(N) discussions, so I propose something different just for the thought exercise.

Is there any known information about the nature of these numbers? If it’s random in nature, then go no further and look at the other answers. You won’t get any better results than they do.

Toutefois! See if whatever list-populating mechanism populated that list in a particular order. Are they in a well-defined pattern where you can know with certainty that the largest magnitude of numbers will be found in a certain region of the list or on a certain interval? There may be a pattern to it. If that is so, for example if they are guaranteed to be in some sort of normal dissortingbution with the characteristic hump in the middle, always have repeating upward trends among defined subsets, have a prolonged spike at some time T in the middle of the data set like perhaps an incidence of insider trading or equipment failure, or maybe just have a “spike” every Nth number as in analysis of forces after a catastrophe, you can reduce the number of records you have to check significantly.

There’s some food for thought anyway. Maybe this will help you give future interviewers a thoughtful answer. I know I would be impressed if someone asked me such a question in response to a problem like this – it would tell me that they are thinking of optimization. Just recognize that there may not always be a possibility to optimize.

 Time ~ O(100 * N) Space ~ O(100 + N) 
  1. Create an empty list of 100 empty slot

  2. For every number in input-list:

    • If the number is smaller than the first one, skip

    • Otherwise replace it with this number

    • Then, push the number through adjacent swap; until it’s smaller than the next one

  3. Return the list


Note: if the log(input-list.size) + c < 100 , then the optimal way is to sort the input-list, then split first 100 items.

THe complexity is O(N)

First create an array of 100 ints initialiaze the first element of this array as the first element of the N values, keep track of the index of the current element with a another variable, call it CurrentBig

Iterate though the N values

 if N[i] > M[CurrentBig] { M[CurrentBig]=N[i]; ( overwrite the current value with the newly found larger number) CurrentBig++; ( go to the next position in the M array) CurrentBig %= 100; ( modulo arithmetic saves you from using lists/hashes etc.) M[CurrentBig]=N[i]; ( pick up the current value again to use it for the next Iteration of the N array) } 

when done , print the M array from CurrentBig 100 times modulo 100 🙂 For the student: make sure that the last line of the code does not trump valid data right before the code exits

Another O(n) algorithm –

The algorithm finds the largest 100 by elimination

consider all the million numbers in their binary representation. Start from the most significant bit. Finding if the MSB is 1 can be a done by a boolean operation multiplication with an appropriate number. If there are more than 100 1’s in these million eliminate the other numbers with zeros. Now of the remaining numbers proceed with the next most significant bit. keep a count of the number of remaining numbers after elimination and proceed as long as this number is greater than 100.

The major boolean operation can be an parallely done on GPUs

I would find out who had the time to put a billion numbers into an array and fire him. Must work for government. At least if you had a linked list you could insert a number into the middle without moving half a billion to make room. Even better a Btree allows for a binary search. Each comparison eliminates half of your total. A hash algorithm would allow you to populate the data structure like a checkerboard but not so good for sparse data. As it is your best bet is to have a solution array of 100 integers and keep track of the lowest number in your solution array so you can replace it when you come across a higher number in the original array. You would have to look at every element in the original array assuming it is not sorted to begin with.

You can do it in O(n) time. Just iterate through the list and keep track of the 100 biggest numbers you’ve seen at any given point and the minimum value in that group. When you find a new number bigger the smallest of your ten, then replace it and update your new min value of the 100 (may take a constant time of 100 to determine this each time you do it, but this does not affect the overall analysis).

  1. Use nth-element to get the 100’th element O(n)
  2. Iterate the second time but only once and output every element that is greater than this specific element.

Please note esp. the second step might be easy to compute in parallel! And it will also be efficiently when you need a million biggest elements.

It’s a question from Google or some else industry giants.Maybe the following code is the right answer expected by your interviewer. The time cost and space cost depend on the maximum number in the input array.For 32-Bit int array input, The maximum space cost is 4 * 125M Bytes, Time cost is 5 * Billion.

 public class TopNumber { public static void main(Ssortingng[] args) { final int input[] = {2389,8922,3382,6982,5231,8934 ,4322,7922,6892,5224,4829,3829 ,6892,6872,4682,6723,8923,3492}; //One int(4 bytes) hold 32 = 2^5 value, //About 4 * 125M Bytes //int sort[] = new int[1 << (32 - 5)]; //Allocate small array for local test int sort[] = new int[1000]; //Set all bit to 0 for(int index = 0; index < sort.length; index++){ sort[index] = 0; } for(int number : input){ sort[number >>> 5] |= (1 << (number % 32)); } int topNum = 0; outer: for(int index = sort.length - 1; index >= 0; index--){ if(0 != sort[index]){ for(int bit = 31; bit >= 0; bit--){ if(0 != (sort[index] & (1 << bit))){ System.out.println((index << 5) + bit); topNum++; if(topNum >= 3){ break outer; } } } } } } } 

i did my own code,not sure if its what the “interviewer” it’s looking

 private static final int MAX=100; PriorityQueue queue = new PriorityQueue<>(MAX); queue.add(array[0]); for (int i=1;i=MAX) { queue.poll(); } queue.add(array[i]); } } 

Possible improvements.

If the file contains 1 billions number, reading it could be really long…

To improve this working you can :

  • Split the file into n parts, Create n threads, make n threads look each for the 100 biggest numbers in their part of the file (using the priority queue), and finally get the 100 biggest numbers of all threads output.
  • Use a cluster to do a such task, with a solution like hadoop. Here you can split the file even more and have the output quicker for a 1 billion (or a 10^12) numbers file.

This code is for finding N largest numbers in an Unsorted array .

 #include  using namespace std; #define Array_Size 5 // No Of Largest Numbers To Find #define BILLION 10000000000 void findLargest(int max[], int array[]); int checkDup(int temp, int max[]); int main() { int array[BILLION] // contains data int i=0, temp; int max[Array_Size]; findLargest(max,array); cout<< "The "<< Array_Size<< " largest numbers in the array are: \n"; for(i=0; i< Array_Size; i++) cout<< max[i] << endl; return 0; } void findLargest(int max[], int array[]) { int i,temp,res; for(int k=0; k< Array_Size; k++) { i=0; while(i < BILLION) { for(int j=0; j< Array_Size ; j++) { temp = array[i]; res= checkDup(temp,max); if(res == 0 && max[j] < temp) max[j] = temp; } i++; } } } int checkDup(int temp, int max[]) { for(int i=0; i 

This might not be the efficient one but gets the job done.

J'espère que cela t'aides

I know this might get buried, but here is my idea for a variation on a radix MSD .

pseudo-code:

 //billion is the array of 1 billion numbers int[] billion = getMyBillionNumbers(); //this assumes these are 32-bit integers and we are using hex digits int[][] mynums = int[8][16]; for number in billion putInTop100Array(number) function putInTop100Array(number){ //basically if we got past all the digits successfully if(number == null) return true; msdIdx = getMsdIdx(number); msd = getMsd(number); //check if the idx above where we are is already full if(mynums[msdIdx][msd+1] > 99) { return false; } else if(putInTop100Array(removeMSD(number)){ mynums[msdIdx][msd]++; //we've found 100 digits here, no need to keep looking below where we are if(mynums[msdIdx][msd] > 99){ for(int i = 0; i < mds; i++){ //making it 101 just so we can tell the difference //between numbers where we actually found 101, and //where we just set it mynums[msdIdx][i] = 101; } } return true; } return false; } 

The function getMsdIdx(int num) would return the index of the most significant digit (non-zero). The function getMsd(int num) would return the most significant digit. The funciton removeMSD(int num) would remove the most significant digit from a number and return the number (or return null if there was nothing left after removing the most significant digit).

Once this is done, all that is left is traversing mynums to grab the top 100 digits. This would be something like:

 int[] nums = int[100]; int idx = 0; for(int i = 7; i >= 0; i--){ int timesAdded = 0; for(int j = 16; j >=0 && timesAdded < 100; j--){ for(int k = mynums[i][j]; k > 0; k--){ nums[idx] += j; timesAdded++; idx++; } } } 

I should note that although the above looks like it has high time complexity, it will really only be around O(7*100) .

A quick explanation of what this is trying to do: Essentially this system is trying to use every digit in a 2d-array based upon the index of the digit in the number, and the digit's value. It uses these as indexes to keep track of how many numbers of that value have been inserted in the array. When 100 has been reached, it closes off all "lower twigs".

The time of this algorithm is something like O(billion*log(16)*7)+O(100) . I could be wrong about that. Also it is very likely this needs debugging as it is kinda complex and I just wrote it off the top of my head.

EDIT: Downvotes without explanation are not helpful. If you think this answer is incorrect, please leave a comment why. Pretty sure that StackOverflow even tells you to do so when you downvote.

Managing a separate list is extra work and you have to move things around the whole list every time you find another replacement. Just qsort it and take the top 100.