Microsoft Interview Question
Software Engineer / DevelopersFWIW, I said trie during the interview and justified it with all of the repetition of letters in words. my structure had the following fields:
1. char data
2. int is_legitimate_ending (e.g. can a word end at this node)
3. node **children (dynamically allocated array of node pointers)
I debated using a double pointer for children or an array of pointers (e.g. size 256 if assuming ASCII) but went with the double ptr because you can (1) save space and (2) include more than 256 characters. array would have had a more constant time lookup than iterating through the dynamically allocated array though.
@woohoo: just my curiosity, how much time you were given to code the entire TRIE stuffs, like, building, inserting, searching.
I had about 30 minutes for the problem. I only had to define the structure and write the verify() method. I did not have to code building & inserting.
Is the verify implementation mean: if the word is not found in Dictionary its misspelled else correct word.
I think TRIE can b used. Using TRIE suggestions can also be given.
- Tulley March 28, 2011