Amazon Interview Question
SDE1sCountry: India
Interview Type: In-Person
Hash with KEY=stringsort of string, VALUE=ArrayList of all strings with this KEY
Duhhhhhhhhhhhhhh (GOOGLE IT DUHHH)
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.
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;
}
Can some help me understand the problem its not clear? Thanks
- airtemple March 07, 2014