Amazon Interview QuestionSoftware Engineer / Developers
- 0of 0 votes
You have a list of 1 million distinct English words. Each word is between 1 to 40 letters long and contains only alphabets, no space or special characters. The list is already sorted alphabetically.
Given a word shorter than 40 letters, find all words in this list that are only 1 letter different from this word, spelling order is not important.
There are 3 types of matches: 1. Swap one letter with another and you have an exact match 2. Remove one letter and you have an exact match and 3 Add one letter and you'll have an exact match. For example: Given the word "coverage", these are valid matches:
1. "converge". Swap 'n' with 'a'
2. "coverages". Remove 's'.
3. "overage". Add a 'c'.
What's the time complexity of your algorithm?
Can your algorithm handle the request to find words that are 2 letters different from the given word?
Country: United States