Внедрение автозаполнения

Question

(Из вопроса о собеседовании)

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

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

Вопрос касается только планирующие дц и pseudocoding Вставка, поиск и т.д.

Примечание: Вы не можете использовать TRIE DS.

Любые идеи?

Answer 1

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

Вы видели похожие вопросы здесь?

autocomplete algorithms, papers, strategies, etc