Как разработать систему автозаполнения поиска Yandex ?!

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

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

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