Design Search Autocomplete system for Yandex

Задача: необходимо разработать систему автозаполнения поиска, например для Yandex.

Изначально у вас есть массив строковых предложений, а также целочисленный массив times (оба массива одинаковой длины), где i-е строковое предложение — это ранее набранное предложение, а times[i] — соответствующее количество раз, когда предложение было набрано.

В системе необходимо реализовать алгоритм вывода для каждого входного символа, кроме ‘#’ (символ нажатия ‘Enter’) 3х самых популярных исторических предложения, которые имеют тот же префикс, что и часть уже набранного предложения. Вернуть 3 самые популярные предложения следует по убыванию степени популярности.

Разбор

Итак, давайте воспользуемся Префиксным деревом (Trie), которое мы разобрали в прошлой статье.

1. Для того, чтобы иметь возможность быстро получать всех кандидатов по заданному префиксу, добавим в префиксное дерево, список вводимых слов для каждого узла. Таким образом, наше дерево по заданному префиксу уже будет хранить все вводимые ранее слова.
2. Для того, чтобы считать популярность каждого из запросов заведем обычный HashMap, ктр для каждого запроса будет хранить кол-во его повторений.
3. Таким образом, при каждом новом вводе символа в систему, мы будем обновлять наш…