При заданном префиксе верните топ N искомых слов с этим префиксом

Question

Мне задали этот вопрос во время интервью. Проблема в поиске Google-автозаполнения предложений.

При заданном префиксе функция должна возвращать первые N (постоянные) искомые слова с этим префиксом, то есть N слов, которые искались чаще всего в прошлом, выбранных из всех слов с этим префиксом, которые были искал когда-либо.

Например: для префикса "ab", N = 3, и все слова с этим префиксом, которые были найдены:

• ab c - 1 раз
• abcd - 1 раз
• abcde - 5 раз
• abgh - 6 раз
• abnm - 3 раза

Функция должна return abcde, abgh, abnm.

Я думал о дереве tr ie, но изо всех сил пытался получить из него самые популярные слова.

Answer 1

Вы думали в правильном направлении, однако наряду с Tr ie вы должны использовать другую структуру данных, например кучу, для хранения частот / количества слов. Таким образом, используя tr ie, вы можете идентифицировать слова, а с помощью кучи вы тянете верхний N.