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

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

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

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

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() {
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;
}``````

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.

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