chriscareercup
BAN USER- 0of 0 votes
AnswersYou 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.
- chriscareercup in United States
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?| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 0of 0 votes
AnswersGiven an integer (assume it's smaller than 50), write an algorithm that will generate all possible combinations of integers greater than 1 and they produce a sum equals to this number. The same number can appear more than once in a combination. What's the time complexity of your algorithm?
- chriscareercup in United States
For example:
<=1 -> {}
2 -> {2},
3->{3},
4->{[4], [2, 2]},
5->{[5], [3, 2]},
6->{[6], [4, 2], [3, 3], [2, 2, 2]}
7->{[7], [5, 2], [4, 3], [3, 2, 2]}
8->{[8], [6, 2], [5, 3], [4, 4], [4, 2, 2], [3, 3, 2], [2, 2, 2, 2]}
....| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Algorithm - 2of 2 votes
AnswersI have 10 million 10-bit integers to sort, how would you sort them and what's the time complexity?
- chriscareercup in United States
Follow-on question: Instead of sorting integers, I now have 10 million pairs to sort. Each pair consists of a 10-bit integer and an object, the sort order is determined by the 10-bit integer. Will your original sort algorithm hold or do you need sort it differently?
(A word of advice: Ask as many questions as you want during the interview, but you MUST be quick. Also, don't mention anything until you've thought it through clearly, otherwise you're just inviting more questions. Time is of essence, you're too slow if this question takes you more than 15 minutes to come up with the optimal solution, because remember, you have to leave time for explanations and other questions)| Report Duplicate | Flag | PURGE
Amazon Software Engineer / Developer Sorting
Your algorithm is basically Fibonacci, you have completely ignored the data structure to store the results and de-duplication.
- chriscareercup November 12, 2012Absolutely, thanks for spotting it. I've updated the question.
- chriscareercup November 12, 2012I've added clarification to the question, please check again.
- chriscareercup November 12, 2012I've added clarification to the question, please check again.
- chriscareercup November 12, 2012
}
- chriscareercup November 12, 2012