Amazon Interview Question
Software Engineer / DevelopersTeam: Intern
Country: United States
Interview Type: Phone Interview
to delete word
n= no of words
m=Max(length of word)
1> first way is to pick one word and search in entire book
if u find that delete it O(m*n^2)
2> short all the word
delete repeated word O(m*nlogn)
3>create a hash of al word and store in table
if you find a wrod which is already in table delete it
O(n*m)
space O(n*m)
1) Take a linked list of words as deletion is easy compared to array.
2) Traverse the list one by one and put each word in a hash table.
3) While inserting each node check it with hash table.
4) If you already find that string delete it from list.
Time Complexity O(n) n=number of strings
We can store each word in a trie. If the word that we are trying to insert is already available in the trie, then we go ahead and delete the word.
- Anonymous March 16, 2012