Amazon Interview Question
Software Engineer / DevelopersI guess only a prefix tree would do good.
A and C are directly possible by the trie
for B we can have permutation algorithm to look into the data structure for possible trie if there is a limitation to the space complexity to be O(n)
if not hash table with the values being the link list to the possible anagrams(nodes in trie)
A multiway trie(256 way for ascii)Trie supports search and string with given prefix directly.
And search for anagrams can also be easily implemented efficiently.
Sketch for anagrams:
Say search for "abcd"
search(root,"abcd")
{
Node[] nodes = // get nodes for a,b,c,d as the characters.
search(nodeforchar(a), "bcd");
search(nodeforchar(b), "acd");
search(nodeforchar(c), "abd");
search(nodeforchar(d), "abc");
}
TRIE is suitable for both a) and c)
- siva.sai.2020 December 15, 2010a) search in dictiorry
c) typing prefix of a valid string suggests valid words
---------
Hash table is suitable for
b) given a string find all valid anagrams in a dictionary
---------
so we need TRIE + HASH data stractures to satisfy all operations