Worthäufigkeit mit Reihenfolge in O (n) -Komplexität

11

Während eines Interviews für eine Java-Entwicklerposition wurde ich wie folgt gefragt:

Schreiben Sie eine Funktion, die zwei Parameter akzeptiert:

eine Zeichenfolge, die ein Textdokument darstellt, und

eine Ganzzahl, die die Anzahl der zurückzugebenden Elemente angibt.

Implementieren Sie die Funktion so, dass eine Liste der nach Worthäufigkeit geordneten Zeichenfolgen zurückgegeben wird, wobei das am häufigsten vorkommende Wort zuerst angezeigt wird. Ihre Lösung sollte in -Zeit ausgeführt werden, wobei die Anzahl der Zeichen im Dokument ist. $O(n)$ $n$

Folgendes habe ich beantwortet (im Pseudocode), es ist nicht , sondern Zeit wegen der Sortierung. Ich kann nicht herausfinden, wie es Zeit geht. $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

Weiß jemand Bescheid oder kann mir jemand Hinweise geben?

algorithms sorting strings data-mining user2712937
quelle

1

Verwenden Sie eine Hash-Tabelle.

Yuval Filmus

Die Verwendung einer Hashtabelle löst das Problem nicht. Darüber hinaus ist Hashtable Legacy-Java.

user2712937

Hash-Tabellen sind normalerweise der Trick, um die Komplexität von

auf

zu

. Auch wenn es sich um Legacy-Java handelt, was auch immer das bedeutet. Ich habe diesen speziellen Fall nicht überprüft, daher haben Sie möglicherweise Recht.

O (n \log n)

$O(n\log n)$

O (n)

$O(n)$

Yuval Filmus

@ YuvalFilmus. Danke, aber die Hash-Tabelle ist so ziemlich die gleiche wie die Hash-Map, die ich bereits verwende (Hauptunterschied zwischen den beiden Datenstrukturen ist die Synchronisation, die hier nicht gilt). Das Protokoll (n) in meinem stammt aus dem Sortieren der Werte in der Hash-Map.

user2712937

3

Diese Seite konzentriert sich übrigens auf Konzepte und Algorithmen, nicht auf Code. Daher bitten wir Sie normalerweise, den Java-Code zu entfernen und eine konzeptionelle Beschreibung Ihres Ansatzes zu geben (möglicherweise mit einem präzisen Pseudocode auf hoher Ebene, falls erforderlich). Auf dieser Site ist auch die relevante Frage, welche Datenstrukturen und Algorithmen verwendet werden sollen. Die spezifische Java-API ist für diese Site nicht themenbezogen (Sie können jedoch in StackOverflow danach fragen). Ebenso Hashtableist es für die Zwecke dieser Site irrelevant , ob es sich um Legacy-Java handelt oder nicht.

DW

10

Ich schlage eine Variation der Verteilungszählung vor:

Lesen Sie den Text und fügen Sie das gesamte gefundene Wort in einen Versuch ein , wobei Sie in jedem Knoten eine Zählung beibehalten, wie oft das von diesem Knoten dargestellte Wort vorgekommen ist. Verfolgen Sie außerdem die höchste Wortzahl maxWordCound. - $O(n)$
Initialisieren Sie ein Array mit einer Größe maxWordCount. Eintragstyp sind Listen von Zeichenfolgen. - , da die Anzahl nicht höher sein kann. $O(n)$
Durchlaufen Sie den Versuch und fügen Sie für jeden Knoten die entsprechende Zeichenfolge zu dem durch die Anzahl angegebenen Array-Eintrag hinzu. - , da die Gesamtlänge der Zeichenketten durch . $O(n)$ $n$
Durchlaufen Sie das Array in absteigender Reihenfolge und geben Sie die gewünschte Anzahl von Zeichenfolgen aus. - , da dies sowohl an die Größe als auch an die Datenmenge im Array gebunden ist. $O(n)$

Sie können den Versuch wahrscheinlich in der ersten Phase durch andere Datenstrukturen ersetzen.

FrankW
quelle

+1, obwohl ich mir nicht sicher bin. Es ist O (n), da die Anzahl der zurückzugebenden Wörter durch n, die Anzahl der Zeichen, begrenzt ist. Aber ist dies das, was die Frage stellt? Oder ein Ergebnis unabhängig von der Anzahl der zurückgegebenen Wörter?

Nikos M.

n

$n$

@ Raphael, ja richtig, ich denke darüber nach, da es in einem Interview gefragt wurde, mögliche Tricks in der Frage ..

Nikos M.

Ich frage mich, ob es einen platzsparenden linearen Zeitalgorithmus gibt.

Saadtaame

3

O (n \lg n)

$O(n \lg n)$

O (n)

$O(n)$

3

Die Erfassung der Anzahl der Vorkommen ist O (n), der Trick besteht also darin, nur die Anzahl der Top-k-Vorkommen zu finden.

Ein Heap ist eine übliche Methode, um die Top-k-Werte zu aggregieren, obwohl auch andere Methoden verwendet werden können (siehe https://en.wikipedia.org/wiki/Partial_sorting ).

Angenommen, k ist der zweite Parameter oben und es ist eine Konstante in der Problemstellung (es scheint zu sein):

Erstellen Sie eine Wortreihe mit Vorkommenszahlen auf jedem Knoten.
Initialisieren Sie einen Haufen der Größe k.
Durchqueren Sie das Trie- und Min-Probe / Insert-Paar (Blatt, Anzahl der Vorkommen) im Top-k-Haufen.
Geben Sie die obersten k Blätter und Zählungen aus (dies ist tatsächlich eine Art Schmerz, da Sie übergeordnete Zeiger benötigen, um jedes Blatt wieder einem Wort zuzuordnen).

Da die Heap-Größe eine Konstante ist, sind die Heap-Operationen O (1), also ist Schritt 3 O (n).

Der Haufen könnte auch dynamisch gepflegt werden, während der Versuch erstellt wird.

KWillets
quelle

2

$O(n \log n)$ $\Theta(n)$ $\Omega(n^2)$

Was folgt, ist falsch ; Ich lasse es vorerst zur Veranschaulichung hier.

$O(n)$ $\Sigma$ $n$

Erstellen Sie einen Suffixbaum des Textes, z. B. mit dem Ukkonen-Algorithmus .

Wenn die Konstruktion dies noch nicht tut, addieren Sie die Anzahl der erreichbaren Blätter zu jedem (inneren) Knoten.
Durchquere den Baum von der Wurzel und schneide alle Zweige am ersten (weißen) Platz ab.
Durchlaufen Sie den Baum und sortieren Sie die Liste der untergeordneten Elemente jedes Knotens nach ihrer Blattzahl.
Der Ertrag des Baumes (Blätter von links nach rechts) ist jetzt eine Liste aller Wörter, sortiert nach Häufigkeit.

Zur Laufzeit:

$O(n)$ $\Theta$
$n$ $n$
$n$ $O(|\Sigma| \cdot \log |\Sigma|) = O(1)$
$O(n)$ $O(n)$

Genauere Grenzen können erhalten werden, indem die Laufzeit mit der Anzahl verschiedener Wörter parametrisiert wird. Wenn es wenige gibt, ist der Baum nach 2 klein.

Raphael
quelle

Der Algorithmus ist falsch (er sortiert nicht). Ich bin mir nicht mehr sicher, ob eine lineare Zeit überhaupt möglich ist.

Raphael

1

HashMap $1..n$ $O(n)$ $O(n)$

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

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

DW
quelle

Θ (n)

$\Theta(n)$

Ω (n^{2})

$\Omega(n^2)$

Ich kann nicht für die Interviewer sprechen, aber ich zögere, ihre Schlamperei als Entschuldigung für mehr davon zu verwenden. Außerdem geht es auf dieser Seite um die Wissenschaft (wie Sie selbst oben kommentiert haben), nicht um handwinkende Programmiertricks "Wie werde ich früher bezahlt?".

Raphael

Solange dieses Verständnis explizit gemacht wird, bin ich damit einverstanden. Ich habe hier zu viele Fragen gesehen, die in Verwirrung begründet waren, weil implizites "Verstehen" falsche Ideen förderte.

Raphael

0

Hashtable-basierte Lösung

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

$n$ $\Omega(n)$

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

Die Annahme ist, dass der Hashing-Algorithmus in Bezug auf die Anzahl der Zeichen zeitlich linear ist.

Radix sortbasierte Lösung

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

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

Die obersten paar längsten Wörter auf Englisch sind lächerlich lang , aber dann könnte man die Wortlänge auf eine vernünftige Zahl (wie 30 oder kleiner) begrenzen und Wörter abschneiden, die die damit verbundene Fehlerquote akzeptieren.

Omer Iqbal
quelle

Θ (n)

$\Theta(n)$

Θ (n)

$\Theta(n)$

O (n + n)

$O(n+n)$

O (n^{2})

$O(n^2)$

(3) Welche Hash-Funktion Sie auch wählen, ich kann eine Eingabe finden, bei der sich diese spezifische Funktion verschlechtert. Die Auswahl der Hash-Funktion nach Kenntnis der Eingabe ist normalerweise keine Option. (Und denken Sie daran, dass der Kommentar, den Sie vermutlich angesprochen haben, den schlimmsten Fall

betraf

O (n^{2})

$O(n^2)$

O (n^{2})

$O(n^2)$

O (1)

$O(1)$

Ω (1)

$\Omega(1)$

O (1)

$O(1)$

O (1)

$O(1)$

Worthäufigkeit mit Reihenfolge in O (n) -Komplexität

Antworten: