Amazon Interview Question for SDE1s


Country: India
Interview Type: In-Person




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

Can some help me understand the problem its not clear? Thanks

- airtemple March 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 4 vote

Hash with KEY=stringsort of string, VALUE=ArrayList of all strings with this KEY

Duhhhhhhhhhhhhhh (GOOGLE IT DUHHH)

- ARE YOU STUPID March 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 votes

I don't think it is that simple. For example, if the given file contains 100 words, out of which there total 9 anagrams then you end up creating 91 keys which are overhead with this solution. If you extend the example to...10000 words etc, It will lot of overhead.

The parameters such as M anagrams, K words needs to be considered while designing the solution.

- Kumar March 06, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thats okay because in the question it is mentioned that k can be equal to 1, that means we can have a list with only one word that is the anagram of itself.
So, the remaining 91 will still matter according to the question.

- Sumit September 14, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Just a small improvement to above solution.We can also create keys entries
on number of each alphabets present. For eg: word :singasong key : a1g2i1o1n2s2 . This will reduce the size of key and can be done in one pass.

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

@pavan can u pls post the solution for this..

- Anonymous March 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

How about using LinkedHashMap, Sorted string is the key for the hash map and linked list will hold k anagrams.

- Rams April 14, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Not a complete soln, but gives the logic.
Idea is to read all the words from the file into a vector<string>
compare each word again others in the vector and if it is anagram, store their indices
in a map where key is the anagram string and value is a vector of indices.

#include <iostream>
#include<vector>
#include<algorithm>
#include<map>

using namespace std;

int main() {
	// your code goes here
	vector<string> words; // assume its populated from the file
	
	vector<string>::iterator it1=words.begin();
	vector<string>::iterator it2=words.begin();
	map<string,vector<int> > anagramList;
	int matched = 0;
	it2++;
	for(int i=0;it1!=words.end();it1++,i++)
	{
		string tmpword1 =*it1;
		matched = 0;
		sort(tmpword1.begin(),tmpword1.end());
		if(anagramList.find(tmpword1) != anagramList.end())
		{
                  //already inserted in the map, so skip it
			continue;
		}
		for(int j=i+1; it2!=words.end();it2++,j++)
		{
			string tmpword2 = *it2;
			sort(tmpword2.begin(),tmpword2.end());
			if(tmpword1 == tmpword2)
			{
				matched = 1;
				anagramList[tmpword1].push_back(j);
			}
		}
		if(matched)
		{
			anagramList[tmpword1].push_back(i);
		}
	
	}
	return 0;
}

- learner March 19, 2014 | 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