What data structure would you use to implement a dictionary?

Question

So I had an interview question about what data structure I would use to implement a dictionary. I said a map because you can enter the word and get the definition in return.

The follow up question was what data structure I would use to implement a system where the user only wanted to lookup a certain number of the starting letters of a word (i.e the first 3 letters) such that the user can get a list of, for example, all the words in the dictionary that start with fic.

I said something about a binary tree but really I had NO idea; the interviewer said the answer was TYPEAHEAD, something like what Microsoft Visual Studio's intellisense does. I had no idea what that was and I have tried to look it up on google but am getting some weird search results. Even though I have no idea what this is and never used it before it is definitely an interesting question.

Does anyone know how to do this? What kind of data structure and what would be the implementation method?

Edit: I'm confused why this is being closed. Is this not a programming question?

Answer 1

Use Trie, a type of tree. Follow this link for solution and better understanding: Trie