HCL America Interview Question
Software Engineer in TestsSolution 1:
I would use an Array IndexA[26]. IndexA[0] corresonds to 'a'........IndexA[25] corresponds to 'z'. Each element of IndexA has a pointer to a tree(could be TRIE). This will reduce the memory used as in TRIE and provide fast search(as hash).
Solution 2:
To further reduce the memory and improve fast search, each element of IndexA contains a pointer to IndexB[26]. Each element of IndexB could be TRIE.
The above algorithm is more like double hash table(hence fast search) with TRIE(reduced node). The reason we used such complex data-structure is that we know dictonary contains words starting with 'aa', 'ab', 'ac'.....'ze'...'zz' with few exceptions such as 'zz'.
One approach is using ternary tree.
1> create a ternary tree of all the words.
2> nodes of this ternary tree, instead of having " isEnd" field would have a pointer of Meaning type.Meaning is a structure having description, synonyms, antonyms, meaning and pronunciation kind of fields.
3>for all non end nodes "isEnd" pointer will be NULL.
One approach is using ternary tree.
1> create a ternary tree of all the words.
2> nodes of this ternary tree, instead of having " isEnd" field would have a pointer of Meaning type.Meaning is a structure having description, synonyms, antonyms, meaning and pronunciation kind of fields.
3>for all non end nodes "isEnd" pointer will be NULL.
how about using TRIE to get started. as we know trie's are the best option for implementing contact list in cellphones, right? i dont know how scalable it would be in case of a complete dictionary, though.
- googler August 12, 2009