Entretien d'algorithme

Question

Je suis allé à une entrevue aujourd'hui et on m'a posé cette question:

Supposons que vous avez 1 milliard d'entiers non triés sur un fichier de disque. Comment détermineriez-vous les 100 plus grands nombres?

Quiconque a des idées, s'il vous plaît partager!

Answer 1

De toute évidence les enquêteurs veulent vous faire remarquer deux faits essentiels:

• Vous ne pouvez pas lire l'ensemble de la liste d'entiers en mémoire, car il est trop grand. Ainsi, vous aurez à lire un par un.
• Vous avez besoin d'une structure de données efficace pour tenir les 100 plus grands éléments. Cette structure de données doit prendre en charge les opérations suivantes:
  • Get-Size: Obtenir le nombre de valeurs dans le conteneur.
  • Find-Min: Obtenir la valeur la plus petite.
  • Delete-Min: Enlever la plus petite valeur de la remplacer par une nouvelle, plus grande valeur.
  • Insert: Insérer un autre élément dans le conteneur.

En évaluant les exigences de la structure de données, un professeur d'informatique attendez vous recommandons l'utilisation d'un Segment de mémoire (Min-Tas), car il est conçu pour soutenir exactement les opérations dont nous avons besoin ici.

Par exemple, pour des tas de Fibonacci, les opérations d' Get-Size, Find-Min et Insert de toutes les sommes O(1) et Delete-Min est O(log n) (avec n <= 100 dans ce cas).

Dans la pratique, vous pouvez utiliser une file d'attente de priorité à partir de votre langue préférée de la bibliothèque standard (par exemple, priority_queue de#include <queue> en C++), qui est généralement mis en œuvre à l'aide d'un tas.

Answer 2

Voici mon algorithme initial:

create array of size 100 [0..99].
read first 100 numbers and put into array.
sort array in ascending order.
while more numbers in file:
    get next number N.
    if N > array[0]:
        if N > array[99]:
            shift array[1..99] to array[0..98].
            set array[99] to N.
        else
            find, using binary search, first index i where N <= array[i].
            shift array[1..i-1] to array[0..i-2].
            set array[i-1] to N.
        endif
    endif
endwhile

C'est la (très léger) avantage est qu'il n'y a pas de O(n^2) brassage pour les 100 premiers éléments, juste un O(n log n) de tri et de vous identifier très rapidement et jeter celles qui sont trop petites. Il utilise également une recherche binaire (7 comparaisons max) pour trouver le bon point d'insertion au lieu de 50 (en moyenne) pour une simple recherche linéaire (non pas que je suggère à quiconque proféré une telle solution, il suffit qu'il peut impressionner l'intervieweur).

Vous pouvez même obtenir des points de bonus pour ce qui suggère l'utilisation d'excellents shift des opérations comme l' memcpy dans C condition que vous pouvez être sûr que le chevauchement n'est pas un problème.

---

Une autre possibilité que vous pourriez envisager est de maintenir trois listes (jusqu'à 100 entiers de chaque):

read first hundred numbers into array 1 and sort them descending.
while more numbers:
    read up to next hundred numbers into array 2 and sort them descending.
    merge-sort lists 1 and 2 into list 3 (only first (largest) 100 numbers).
    if more numbers:
        read up to next hundred numbers into array 2 and sort them descending.
        merge-sort lists 3 and 2 into list 1 (only first (largest) 100 numbers).
    else
        copy list 3 to list 1.
    endif
endwhile

Je ne suis pas sûr, mais qui peut finir par être plus efficace que le brassage continuel.

La fusion de tri est une simple sélection, le long de la lignes de (pour la fusion et le tri des listes 1 et 2 en 3):

list3.clear()
while list3.size() < 100:
    while list1.peek() >= list2.peek():
        list3.add(list1.pop())
    endwhile
    while list2.peek() >= list1.peek():
        list3.add(list2.pop())
    endwhile
endwhile

Il suffit de mettre, en tirant le top 100 des valeurs de la liste en vertu du fait qu'ils sont déjà triés dans l'ordre décroissant. Je n'ai pas vérifié en détail si cela allait être plus efficace, je suis juste en offrant une possibilité.

Je soupçonne que les enquêteurs seraient impressionnés par le potentiel de "out of the box" la pensée et le fait que tu avais dit qu'il faut en évaluer les performances.

Comme avec la plupart des entrevues, la compétence technique est l'une des choses qu'ils regardent.

Answer 3

Créez un tableau de 100 nombres, tous étant -2 ^ 31.

Vérifiez si le premier numéro lu sur le disque est supérieur au premier de la liste. Si c'est le cas, copiez le tableau vers le bas 1 index et mettez-le à jour avec le nouveau numéro. Si ce n'est pas le cas, cochez le suivant dans le 100, etc.

Lorsque vous avez fini de lire les 1 milliard de chiffres, vous devriez avoir les 100 meilleurs chiffres du tableau.

Travail accompli.

Answer 4

Je parcourais la liste dans l'ordre. Au fur et à mesure, j'ajoute des éléments à un ensemble (ou multiset selon les doublons). Lorsque l'ensemble atteint 100, je n'insère que si la valeur est supérieure au minimum de l'ensemble (O (log m)). Puis supprimez le min.

Appel du nombre de valeurs de la liste n et du nombre de valeurs à rechercher m:

c'est O (n * log m)

Answer 5

La rapidité de l'algorithme de traitement n'a absolument aucune importance (à moins que ce soit complètement stupide).

Le goulot d'étranglement ici est I / O (il est spécifié qu'ils sont sur le disque). Veillez donc à utiliser de grands tampons.