Interview Question
Front-end Software EngineersTeam: Web Developer
Country: United States
Interview Type: Phone Interview
sort the 100 word's :
create trie of sorted words :
now create a function which :
1) take's input word sort's it.[ make a copy of word if changing original is not allowed .]
2) search word in trie
3) return's true or false accordingly .
I am not sure how you would implement trie on this case without sorting each word first alphabetically, like bag as abg and ball as abll.. in this case you would have single trie. now you would sort the input alphabetically and search it in the trie as the expense of space though.
One can also go for TRIE. Store all the 100 words in TRIE in sorted form.
As a new word comes, search for its sorted sequence in the TRIE.
The time complexity would be O(length of the word to be searched).
However, it is space consuming.Ternary search trees can be used to reduce the space..
1) For each word calculate key where key= word sorted in alphabetical order. Hence if the word is APPLE , the key becomes AELPP.
- Yoda July 17, 20122) Store these words in a hash with key as above and value as boolean true.
3) for any inpur word apply the above hash function and get key. Then search in the hash table for the key.