Algorithmen und Datenstrukturen · Senior · Frage 59 von 75
Welche Struktur würdest du für eine Autovervollständigung nutzen, die Vorschläge nach Beliebtheit ordnet?
- 1Einen Trie mit den besten Vorschlägen an jedem Knoten gecacht
- 2Eine Hash-Map von ganzen Wörtern nur zu ihren Zählern
- 3Ein sortiertes Array, das von vorne durchsucht wird
Antwort zeigen
Richtige Antwort: Einen Trie mit den besten Vorschlägen an jedem Knoten gecacht
Erklärung
Der Trie findet den Präfixknoten in O(Länge des Präfixes); die besten k pro Knoten zu cachen erspart das Durchlaufen des ganzen Teilbaums bei jedem Tastendruck. Eine einfache Map kann Wörter nicht effizient nach Präfix auflisten.