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

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)

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.

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.

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.

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

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

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.

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

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