Amazon Interview Question Software Engineer / Developers
Team: RCX
Country: United States
Interview Type: In-Person
Create an array of the size of the domain of the note (i.e. smallcase and uppercase letter, punctuation, numbers etc, i.e. ascii search space of 256 characters).
Populate the respective array cell with the number of occurences of that element in the note.
Now read the magazine and decrement the respective cell count by 1 when you encounter that element in magazine.
Also, keep a global counter of number of distinct elements which have a current count > 0. Hence as soon as the count of an element decrements to 0, decrement the global counter as well (This will help in avoiding unnecessary further reading of the magazine even after all the elements of the note have been found in magazine).
solution at the granularity of words
create a trie out of the magzine string with the occurrences of each of them and try to find the strings in the note in the trie, if you find the string in the trie then reduce the occurance of that string by 1(since its cut paste not copy paste)...in this way if we could find all the strings then the kidnapper wins!
Cant we create a multidimensional string for both the ransom not and magazine.
Let the total no. of words present in magazine and note be m and n respectively.
then we are going to look for the first string in multidimensional string from note and search(binary) it in multidimensional string from magazine.
In this way we can search for each string present in note whether it is present in magazine.
Complexity will be logm X logn....
Cant we create a multidimensional string for both the ransom not and magazine.
Let the total no. of words present in magazine and note be m and n respectively.
then we are going to look for the first string in multidimensional string from note and search(binary) it in multidimensional string from magazine.
In this way we can search for each string present in note whether it is present in magazine.
Complexity will be logm X logn....
find the LCS(longest common subsequence) . If the length is equal to that of the note then it contains
Seriously, what is it with everyone trying to use LCS for everything? LCS is a relatively inefficient algorithm (quadratic) at best, and incorrect in most problems, like this one, since the words can appear in a different order in the magazine than they do in the ransom note.
Remember, LCS is applicable in a relatively narrow range of situations.
Its a classic anagram check problem with a twist. Assuming that the letters are alphabets, you can declare a integer array of size 26, increment the character count as you scan the note. Decrements the count as you scan the magazine. Finally when you scan the character count array, it should have values >=0
- CSPrasad January 06, 2012