Fréquence des mots avec ordre dans la complexité O (n)

Lors d'une interview pour un poste de développeur Java, on m'a demandé ce qui suit:

Écrivez une fonction qui prend deux paramètres:

1. une chaîne représentant un document texte et
2. un entier indiquant le nombre d'articles à retourner.

Implémentez la fonction de telle sorte qu'elle retourne une liste de chaînes ordonnées par fréquence de mot, le mot le plus fréquent en premier. Votre solution doit s'exécuter en temps où est le nombre de caractères dans le document.$O(n)$$n$

Ce qui suit est ce que j'ai répondu (en pseudocode), ce n'est pas mais plutôt raison du tri. Je ne peux pas comprendre comment le faire temps. $O(n)$$O(n \log n)$$O(n)$

wordFrequencyMap = new HashMap<String, Integer>();
words = inputString.split(' ');

for (String word : words) {
  count = wordFrequencyMap.get(word);
  count = (count == null) ? 1 : ++count;
  wordFrequencyMap.put(word, count);
}

return wordFrequencyMap.sortByValue.keys

Quelqu'un sait-il ou quelqu'un peut-il me donner des indices?

Je suggère une variation du comptage de distribution:

1. Lisez le texte et insérez tous les mots rencontrés dans un trie , en conservant dans chaque nœud un décompte, à quelle fréquence le mot représenté par ce nœud s'est produit. De plus, gardez une trace du nombre de mots le plus élevé maxWordCound. - $O(n)$
2. Initialisez un tableau de taille maxWordCount. Le type d'entrée est une liste de chaînes. - , car le nombre ne peut pas être supérieur.$O(n)$
3. Parcourez le trie et pour chaque nœud, ajoutez la chaîne correspondante à l'entrée du tableau indiquée par le nombre. - , car la longueur totale des chaînes est limitée par n .$O(n)$$n$
4. Parcourez le tableau dans l'ordre décroissant et affichez le nombre de chaînes souhaité. - , car il s'agit d'une limite à la fois de la taille et de la quantité de données dans le tableau.$O(n)$

Vous pouvez probablement remplacer le trie par d'autres structures de données dans la première phase.

La collecte des nombres d'occurrences est O (n), donc l'astuce consiste vraiment à trouver uniquement les k premiers nombres d'occurrences.

Un tas est un moyen courant d'agréger les k premières valeurs, bien que d'autres méthodes puissent être utilisées (voir https://en.wikipedia.org/wiki/Partial_sorting ).

En supposant que k est le deuxième paramètre ci-dessus, et que c'est une constante dans l'énoncé du problème (il semble que ce soit):

1. Créez un trie de mots avec un nombre d'occurrences sur chaque nœud.
2. Initialisez un tas de taille k.
3. Parcourez le trie et le min-sonde / insérez chaque paire (feuille, nombre d'occurrences) dans le tas du haut k.
4. Sortez les k premières feuilles et compte (c'est en fait une sorte de douleur car vous avez besoin de pointeurs parents pour mapper chaque feuille en un mot).

Étant donné que la taille du tas est une constante, les opérations du tas sont O (1), donc l'étape 3 est O (n).

Le tas pourrait également être maintenu dynamiquement lors de la construction du trie.

Votre algorithme ne s'exécute même pas dans le temps ; insertion thetav ( n ) les choses dans un temps frais Hashtable Ω ( n 2 ) déjà (pire cas).$O(n \log n)$$\Theta(n)$$\Omega(n^2)$

Ce qui suit est faux ; Je le laisse ici pour le moment à des fins d'illustration.

L'algorithme suivant s'exécute dans le pire des cas (en supposant un alphabet Σ de taille constante), n le nombre de caractères dans le texte.$O(n)$$\Sigma$$n$

1. Construisez un arbre de suffixes du texte, par exemple avec l'algorithme d' Ukkonen .

   Si la construction ne le fait pas déjà, ajoutez le nombre de feuilles accessibles à chaque nœud (interne).

2. Traversez l'arbre de la racine et coupez toutes les branches au premier espace (blanc).

3. Parcourez l'arbre et triez la liste des enfants de chaque nœud en fonction de leur nombre de feuilles.

4. Le rendement de l'arbre (feuilles de gauche à droite) est maintenant une liste de tous les mots, triés par fréquence.

Concernant l'exécution:

1. L'algorithme d'Ukkonen (dans sa forme améliorée) s'exécute dans le temps ; le maintien du nombre de feuilles n'augmente pas le coût Θ de l'algorithme.$O(n)$$\Theta$
2. Nous devons traverser un nœud par caractère de chaque mot qui apparaît dans le texte. Puisqu'il y a au plus paires de mots-caractères différentes, nous visitons au plus n nœuds.$n$$n$
3. Nous visitons au plus nœuds (cf. 2.) et passons du temps O ( | Σ | ⋅ log | Σ | ) = O ( 1 ) par nœud.$n$$O(|\Sigma| \cdot \log |\Sigma|) = O(1)$
4. On peut obtenir le rendement (qui a bien sûr la taille ) par une simple traversée dans le temps O ( n ) (cf. 2.).$O(n)$$O(n)$

Des limites plus précises peuvent être obtenues en paramétrant l'exécution avec le nombre de mots différents; s'il y en a peu, l'arbre est petit après 2.

Utilisez une table de hachage (par exemple, HashMap) pour collecter tous les mots et leurs fréquences. Utilisez ensuite le tri par comptage pour trier les mots par ordre décroissant de fréquence. Comme toutes les fréquences sont des entiers compris entre , le tri du comptage prend O ( n ) . Le temps de fonctionnement total prévu est O ( n ) , ce qui est probablement plus que suffisant pour toutes les fins pratiques (à moins que l'enquêteur n'ait mentionné quelque chose qui a été omis de votre question). Assurez-vous de mentionner qu'il s'agit du temps d' exécution prévu plutôt que du pire des cas .$1..n$$O(n)$$O(n)$

Ce n'est peut-être pas la réponse qu'un enseignant chercherait dans une classe d'algorithmes, car il s'agit du temps d'exécution plutôt que du temps d'exécution O ( n ) dans le pire des cas. Si vous souhaitez marquer des points supplémentaires à la question d'entrevue, vous pouvez mentionner de manière désinvolte de manière désinvolte que cela est bien sûr le temps de fonctionnement prévu, mais cela peut également être fait dans le temps de fonctionnement le plus défavorable O ( n ) en remplaçant le table de hachage avec une structure de données plus sophistiquée - et vous seriez heureux d'expliquer comment vous choisiriez entre les algorithmes dans une situation comme celle-ci.$O(n)$$O(n)$$O(n)$

$O(n)$$O(n)$

Solution basée sur Hashtable

$\Omega(n^2)$$n$

$n$$\Omega(n)$

$O(1)$$O(n)$$O(n^2)$$n$

L'hypothèse est que l'algorithme de hachage est linéaire dans le temps par rapport au nombre de caractères.

Solution basée sur le tri Radix

$O(kN)$$k$$N$$n$$k$$O(n)$

$2n$$n$$O(n)$

Les quelques mots les plus longs en anglais sont ridiculement longs , mais alors on pourrait limiter la longueur du mot à un nombre raisonnable (tel que 30 ou plus petit) et tronquer les mots en acceptant la marge d'erreur qui pourrait l'accompagner.