Amazon Interview Question for Software Engineer / Developers






Comment hidden because of low score. Click to expand.
1
of 1 vote

Unless I'm missing something, I don't think this is a hard problem.

public 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.

- Rytis January 04, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Rytis
Nice and easy approach :) meets all the constrains forced in the question.

keep it up !!

- Addy May 27, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

one small patch in da ans is to treat both uppercase and lowercase chars to be same .....
otherwise da answer is perfect..

- rhino November 07, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It says use O(1) space

- No-one November 13, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

256 is constant, is O(1)

- xyz January 02, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

256 is constant, is O(1)

- xyz January 02, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

//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;
}

- sachin February 27, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Is this question ask us to find whether the node is a subset of article, in terms of words used?

any ideas?

- Anonymous December 20, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I'm not sure, people phrase their questions horribly on this site. It could be find whether the letters in the note are a subset of those in the article, or whether the words themselves are a subset.

Who knows?

- Anonymous December 22, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

i can't see any ambiguity in the question since we have to use letter cuttings from the magazine to write the message we can use a letter instance only once...

- newera December 23, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

hey, why don't you improve your english first and then attend the interview. Can't understand a single word in your questions

- master December 25, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This can be solved taking an array of char[256] . It is difficult to solve the problem with both time and space complexity limitations.

- Anonymous December 28, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

.......... 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.

- Anonymous January 05, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

the intent of the question is to check how many different ways a person can solve this problem.
you will come up with one solution and interviewer will ask you if you can optimize it ..
hope you got my point.
nobody wants you to give most optimized solution on 1 attempt.

- no question is a dumb question February 22, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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).

- 8x January 29, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- Anonymous February 05, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I agree. char[256] is clearly fine with O(1) space complexity

- oldcap March 10, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 April 29, 2009 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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.

- Gayle L McDowell April 29, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous May 01, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Anonymous March 11, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Actually, having asked this question as an interviewer to a lot of (google) candidates, few candidates get an O(n) time solution immediately.

Additionally, not all interview questions are intended to stump you. It's good practice, as an interviewer, to ask some easier questions.

- Gayle L McDowell March 11, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think it just pattern matching question as u get a match for a letter pick it out.
any comments?

- biker March 31, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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).

- Girish Nandagudi June 24, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I have heard a slightly different question : instead of the letters I have heard of words ... You cut out the words and then have to form sentence. but I don't know if they allowed to take individual letters.
means from wheell you could make he well previously but not now ...

- pull the bull August 27, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

the simplest solution is just to check that all chars used in the message are available in the given article keeping track of the count. If yes then the answer is YES else NO.
This logic is implemented clearly by Rytis. Thanks Rytis.

- Seema August 31, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

i have a query ....

> we can use a bool array of size 256 instead of char arr[256] , but in C we cannot define such a thing . what to do ?

- Anonymous September 14, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

i think the question should be asking the minimize number of cuts. If you have a sentence/phrase match that will be perfect, cut the sentence. Usually you cut words, but when you have no choice you cut prefix/suffix, cutting single letters will be the last resort.

- Anonymous November 06, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

Use Rabin-Karp algorithm

- anon November 11, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Teng August 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

I guess Rabin Karp algorithm is a better solution. All other approaches seem too naive. Also the question is not clear at all.

- lance_armstrong June 14, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- Ravi Ranjan March 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Nikkhah April 24, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

One optimization is to put the Note (of size K) in the hash, not the Article (of size N). This way, the best case run time is O(2*K). The way it's written now, the best case runtime is O(N+K) where N >> K.

- Joe September 18, 2016 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More