Amazon Interview Question Software Engineer / Developers
@Rytis
Nice and easy approach :) meets all the constrains forced in the question.
keep it up !!
one small patch in da ans is to treat both uppercase and lowercase chars to be same .....
otherwise da answer is perfect..
//This program is same as above but using map in STL
int RansomeNote(string& article , string& note){
map<char,int> charCount;
for(string::const_iterator it = article.begin() ; it != article.end() ; it++)
charCount[*it] += 1;
for(string::const_iterator it = note.begin() ; it != note.end() ; it++)
charCount[*it] -= 1;
for(string::const_iterator it = note.begin() ; it != note.end() ; it++)
{
if(charCount[*it] < 0)
return -1;
}
return 1;
}
int main( )
{
string str("Sam from Baffalo at university of Binghamton , NY kidnapped") , sub("sam kidnapped kidnapped");
cout << RansomeNote(str,sub); // Returns -1
sub("sam kidnapped")
cout << RansomeNote(str,sub); // Returns 1
int i ;
cin >> i;
return 0;
}
.......... clearly we all know how to solve the trivial problem you have proposed, however it is not clear at all as to what he is asking.
Counting the characters and checking that there are enough is a dumb question.
I think the problem is "o(1) space complexity", so
int[] availableChars = new int[256];
above (etc.) doesn't quite solve it (stricktly speaking);
- maybe that's the catch? (YAISAQ).
doesnt an array of constant size have O(1)space complexity?... If the array size was to vary linearly with input(n) complexity would have been O(n)...... Am I wrong?
O(1) space complexity means 1 element storage. Here its 1 char.I guess here the problem is to find whether the chars of set Sn is subset of chars of another set Sm with the given constraints.
Joy - O(1) space complexity means a *constant* amount of storage, not 1 element storage. To see this, think about what we mean when we say O(1) time. We don't mean in "1 element of time", we mean a constant amount of time. That is, if we can do something in 300 steps, that would be constant time. Likewise, if we need 300 elements of storage, that would also be constant time.
O(1) time/space put another way means the time required/space required to solve the problem does not depend on the number of inputs, in this case either the number of characters in the magazine article, or the number of characters in the ransom note. You'll only need int[256] to store the character counts whether you have a 160-character-article or a million-character-article.
Although, if you are talking about 2-billion-plus character articles, you might want to use 64 bit ints. Still technically constant.
You guys can all claim it is a dumb question. But you are supposed to write _bug free_ code. It is a reasonable interview question, IMO.
Another interpretation could be that cutting out one letter from page x, might remove options for another letter on the back, on page x+1, but seems too open ended for an interview.
Use a hash table. Scan the magazine letters to add ‘em to the hash table. Keep a count of the letters. This is done in O(m). Now, iterate through the ransom note and check if the letter in ransomnote[i] exists in the hash table. If so, decrement the value. If the letter doesn’t exist or the value is already zero, exit with negative status. This is done in O(n). The final solution will be done in O(m+n).
Rabin-Karp Algorithm will not work since it computes the hashcode of a whole String and each time shift by one and keep comparing, and also Rabin-Karp takes O(mn) in the worst case scenario + o(m) space. Read from wiki. More importantly you don't want to do exact string matching for this problem, instead you want to know how many characters from the magazine that can be rearranged and used for the note.
suppose I have a ransom money of 12345678 and magazine String contains "something 1 and blah blah 2 blan 8 ....." so my job is to find if I can get letter 1,2,3...8 out of the String.
I will create a HashMap of the Ransom money with key = the letter and value= number of time the letter has occured in the Rasom money.
Like in ransom money 255000. HashMap will look like {(2,1);(5,2);(0;3)}. This HashMap will have max size of 10 for each value of 0,1,2,3...9. (here instead of Map we can also use array of size 10);
Now I will I iterate throught the lenght of the Magazine article and for each letter I will look for the same in the HashMap.
if we find the match we decrement the count of the value of the key, and if the key has value =1 and match is found then we remove the Key from the map(this means that we got all the letter for that key)
we keep on doing the above step till the map is empty.
If the map.isEmpty()==true then return true;(ie it is possible to make the ransom amount)
else if we have reached the end of the magazine article but the map is not empty the retrun false;(we could not complete the ransom amount).
public boolean isRansomPossible(String ransom,String article)
{
int ransomLength = ransom.length();
int articleLength = article.length();
HashMap<Character,Integer> map = new HashMap();
for(int i=0;i<ransomLength;i++)
{
if(!map.containsKey(ransom.charAt(i)))
map.put(ransom.charAt(i),1);
else{
int value = map.get(ransom.charAt(i));
map.put(ransom.charAt(i),value+1)
}
}
for(int i=0;i<articleLength;i++)
{
if(map.isEmpty)
return true;
if(map.get(article.charAt(i)))
if(map.get(article.charAt(i)==1)
map.remove(article.charAt(i))
else
{
int value = map.get(article.charAt(i));
map.put(article.charAt(i),value-1);
}
}
return false;
}
All code seems to solve the problem while you consider the ransom note and magazine as collection of charecters.
what if you want to consider them as collection of words?
Can you still think of an algorithm with space complexity of O(1)?
I consider 2 solutions but not in O(1):
1. Using a HashMap <string, int> which map words as key to their amount in magazine as value and the rest of code is somehow similar. time: O(m) and Space :O(m)
2. Using BST which contains words and their amount. time: O(m log m) and Space :O(m)
all in all you can reduce the time complexity of such algorithms by searching the magazine for a letter or word while simultaneously creating hash map.
If you can help to reduce the space complexity in word matching situation or if you have any hints to improve the algorithms, please help.
Best
Unless I'm missing something, I don't think this is a hard problem.
- Rytis January 04, 2009public boolean isRansomMessagePossible(String message, String article){
int[] availableChars = new int[256];
for(int r = 0; r < article.length(); r++){
int asciiCode = (int)(article.charAt(r));
availableChars[asciiCode]++;
}
for(int r = 0; r < message.length(); r++){
int asciiCode = (int)(message.charAt(r));
availableChars[asciiCode]--;
if(availableChars[asciiCode] < 0)
return false;
}
return true;
}
As far as the problem statement goes, I think it's pretty clear when you know the idea, so don't blame the author of the question if you've never done anything like that. I remember I wrote one of my first love letters this way :-P.