Écrire un programme pour trouver les 100 plus grands nombres d’un tableau de nombres 1 milliard

Question

J’ai assisté récemment à une interview où on m’a demandé « écrire un programme pour trouver les 100 plus grands nombres d’un tableau de nombres 1 milliard ».

Seulement, j’ai été en mesure de donner une solution de force brute qui consistait à trier le tableau en complexité en temps O(nlogn) et prendre les 100 derniers numéros.

L’intervieweur a été à la recherche d’une meilleure complexité, j’ai essayé quelques autres solutions, mais n’a pas pu lui répondre. Y a-t-il une meilleure solution de complexité de temps ?

Answer 1

Vous pouvez garder une file d'attente prioritaire de les 100 plus grand nombre, l'itération à travers les milliards de chiffres, chaque fois que vous rencontrez un nombre plus grand que le plus petit numéro dans la file d'attente (la tête de la file d'attente), de supprimer la tête de la file d'attente et ajouter le nouveau numéro de la file d'attente.

EDIT: en tant que Dev a noté, avec une file d'attente de priorité mis en œuvre par un segment de mémoire, la complexité de l'insertion pour la file d'attente est - O(logN)

Dans le pire des cas, vous obtenez billion*log ce qui est mieux que ₂

En général, si vous avez besoin le plus grand K nombres à partir d'un ensemble de N nombres, la complexité est - (100) plutôt que d' billion*log, ce qui peut être très important lorsque K est très faible en comparaison des N.

EDIT2:

Le temps de cet algorithme est assez intéressant, car à chaque itération une insertion peut ou peut ne pas se produire. La probabilité de la i-ième nombre pour être inséré dans la file d'attente est la probabilité d'une variable aléatoire est supérieure à au moins ₂ variables aléatoires à partir de la même distribution (les k premiers nombres sont automatiquement ajoutés à la file d'attente). Nous pouvons utiliser les statistiques d'ordre (voir lien) pour calculer cette probabilité. Par exemple, supposons les nombres ont été choisis au hasard uniformément à partir d' (billion), la valeur attendue de (i-K), le nombre (de je numéros) O(NlogK), et la probabilité d'une variable aléatoire étant plus grande que cette valeur est O(NlogN).

Ainsi, le nombre d'insertions est:

Et la durée de temps d'exécution peut être exprimé comme:

(i-K temps de génération de la file d'attente avec le premier {0, 1} éléments, (i-k)/i comparaisons, et le nombre d'insertions, comme décrit ci-dessus, chacun prend une moyenne 1-[(i-k)/i] = k/i du temps)

Notez que lors de l' k est très grand en comparaison des k, cette expression est beaucoup plus proche d' n-k plutôt que d' log(k)/2. C'est un peu intuitif, comme dans le cas de la question, même après 10000 itérations (ce qui est très faible comparer à un milliard de dollars), les chances d'un certain nombre pour être inséré dans la file d'attente est très faible.

Answer 2

Si cela est demandé dans une interview, je pense que l'intervieweur veut probablement voir votre processus de résolution de problème, et pas seulement vos connaissances des algorithmes.

La description est tout à fait général, donc peut-être que vous pouvez lui demander de la plage ou de la signification de ces chiffres pour rendre le problème clairement. Cela peut impressionner l'intervieweur. Si, par exemple, ces numéros de stands pour les gens de l'âge de l'intérieur d'un pays (la Chine),alors il est beaucoup plus facile de problème. Avec une hypothèse raisonnable que la personne en vie est de plus de 200, vous pouvez utiliser un tableau int de taille 200(peut-être 201) pour compter le nombre de personnes ayant le même âge en une seule itération. Ici, l'indice moyen de l'âge.. Après, c'est un morceau de gâteau pour trouver les 100 plus grand nombre.

De toute façon, faire de la question plus spécifique et la plus claire qui est bon pour vous, dans une interview.

Answer 3

Vous pouvez itérer sur les numéros qui prend o (n)

Chaque fois que vous trouvez une valeur plus grande que le minimum actuel, ajouter la nouvelle valeur à une file d’attente circulaire avec taille 100.

La minute de cette file d’attente circulaire est votre nouvelle valeur de comparaison. Continuer à ajouter à cette file d’attente. S’il est plein, extraire le minimum de la file d’attente.

Answer 4

J'ai réalisé que c'est taggés avec "algorithme", mais va jeter quelques autres options, car il devrait également être étiqueté "entretien".

Quelle est la source de la 1 milliards de chiffres? Si c'est une base de données, puis "select valeur from table order by desc limit 100' faire le travail très bien, - il pourrait y avoir des différences dialectales.

Est-ce un one-off, ou quelque chose qui va être répété? En cas de récidive, à quelle fréquence? Si c'est un one-off et les données sont dans un fichier, puis "chat srcfile | tri (options) | tête -100' vous permettra de vous faire rapidement un travail productif que vous êtes payé pour le faire alors que l'ordinateur gère cette petite corvée.

Si elle est répétée, vous conseille cueillette toute bonne approche pour obtenir la réponse initiale et store / cache les résultats de sorte que vous pourriez être en permanence en mesure de faire rapport dans le top 100.

Enfin, il y a cette considération. Vous êtes à la recherche d'un emploi de niveau d'entrée et une entrevue avec un geek manager ou futur co-travailleur? Si oui, alors vous pouvez jeter toutes sortes d'approches décrivant la technique relative des avantages et des inconvénients. Si vous êtes à la recherche pour plus de gestion de l'emploi, puis l'aborder comme un gestionnaire, concernés par le développement et les coûts de maintenance de la solution, et de dire "merci beaucoup" et de laisser si c'est l'interviewer veut se concentrer sur CS de trivia. Il et vous serait probablement pas beaucoup d'avancement du potentiel.

Meilleure chance la prochaine entrevue.

Answer 5

Vous pouvez utiliser Rapide sélectionnez l'algorithme pour trouver le numéro(par ordre) index [milliards de dollars-101] et puis itérer sur les nombres et pour trouver les numéros qui biger à partir de ce numéro.

array={...the billion numbers...} 
result[100];

pivot=QuickSelect(array,billion-101);//O(N)

for(i=0;i<billion;i++)//O(N)
   if(array[i]>=pivot)
      result.add(array[i]);

Cet algorithme est la suivante: 2 X O(N) = O(N) (Moyenne des performances)

La deuxième option comme Thomas Jungblut suggérer, c'est:

L'utilisation de Segment de la construction de la MAXI tas prendre en O(N),puis le top 100 max numéros seront en haut de l'échelle, tous vous avez besoin est de les mettre dans le tas(100 X O(Log(N)).

Cet algorithme est la suivante:O(N) + 100 X O(Log(N)) = O(N)