AutoComplete implementation - Interview Question

Question

Hi,

Say you have a DB table with two cols: SearchPhrase(String) | Popularity(Int).

You need to initialize a DS so that you could use it to implement an autocomplete feature (like google suggest) comfortably. The requirement: Once the data from the db is processed into the data structure, when you type a letter you get the 10 most popular searchphrases from the db starting with that letter,then when you type the next one you get the 10 .... with these two letters and so on.

The question only concerns planning the ds and pseudocoding Insert,Search etc.

Note: YOU CANNOT USE TRIE DS.

Any ideas?

Answer 1

A trie would be the best fit but since you can't use it, what about a DAWG?

Have you seen similar questions on here?

http://stackoverflow.com/questions/226963/autocomplete-algorithms-papers-strategies-etc