Bloomberg LP Interview Question Financial Software Developers
Wow, that doesn't sound like something someone with just one programming class would know...
Why to use suffix tree? Every leaf of this tree means suffixe and here we need words. Instead one may use prefix tree (trie) and there will be the whole words in it.
I agree about the idea that suffix tree is not required here. Also I think it would use too much excesive memory. I know that it uses O(n) memory, but that O(n) have an assumption that we store edge as a two indexes from the original word, so here we should store words somewhere or store edges as a string, what would result in O(n^2) memory. Anyway PATRICIA trees would be much better choice than TRIE, since it compresses edges. Tree aproach is not perfect, since they doesn't utilize the property of languages that many deal of words end with the same suffix. We can on example make additional tree for ends of a nouns/werbs, and if we are on the end of the noun we go to the noun tree.
The optimal solution would be using Directed Acyclic Word Graph (DAWG). More about it here: http://en.wikipedia.org/wiki/Directed_acyclic_word_graph . The image on the right shows good comparision of space efficency of DAWG and TRIE.
To check spellings of words - which have a set of delimiters - why not do a last word spell check every time one of the characters in the delimiter is typed? Use a preprocessed dictionary for word lookup. If no such word, highlight the word.
Cancel lookup on backspace or word alteration.
Checking on every character typed is more like auto-completion, not necessary for just spell check I think.
Preprocess all the dictionary words in a Suffix tree.
- Tulley December 03, 2010Traverse the node of suffix as per the character is typed.
If the traversal doesnt leads to any of the node in suffix tree, highlight the word.
If backspace is also allowed to make correction after user sees the highlighted word then each node of Suffix Tree should contain the pointer to its parent node also.