Автозаполнение реализации

Question

(из интервью)

Допустим, у вас есть таблица БД с двумя столбцами: SearchPhrase (String) | Популярность (Int).

Вам нужно инициализировать DS, чтобы вы могли использовать его для реализации автозаполнения функция (как Google предлагает) удобно. Требование: однажды данные из БД обрабатывается в структуре данных, когда вы набираете букву, вы получаете 10 самых популярных поисковых фраз из БД, начиная с этой буквы, затем, когда вы набираете следующую, вы получаете 10 .... с этими двумя буквами и так далее.

Вопрос касается только планирования вставки ds и псевдокодирования, поиска и т. Д.

Примечание: ВЫ НЕ МОЖЕТЕ ИСПОЛЬЗОВАТЬ TRIE DS.

Есть идеи?

Answer 1

Лучше всего подойдет три, но так как вы не можете его использовать, как насчет DAWG ?

Вы видели подобные вопросы здесь?

алгоритмы автозаполнения, документы, стратегии и т. Д.