Microsoft Interview Question
Country: India
@Sathya
What do u mean by "brute force" and could you please point me in the original problem posting to any constraints (time or space). On the other hand, I would appreciate if the comments are in more the constructive form rather than what was stated by you. I believe that the comments like "your solution has some drawbacks (specific), and I suggest to improve it to this" are more welcome in this type of forums.
Thanks,
Ashot
There is an easier way around this:
We are trying to find anagrams :in these the sum of ascii values of all characters is equal.Use any sorting algorithm (quick sort for example ),but for comparision use the sum of characters.This way
equal values strings(Anagrams) will lie next to each other.
1. Loop through the array.
2. For each word, sort the characters and add it to hash map with key as sorted word and value as original word.
At end of loop, you will all anagrams as value to a key (which is sorted by its constituent chars).
3. Iterate over the hashmap, print all values of a key together and then move to next key.
Space complexity: O(n), time complexity: O(n)
assuming all the strings are meaningfull
set i=0
repeat while i<n (
set j=0 and value[i]=0
convert s[i] to upperString
change s[i] to character array c
repeat while c[j] != '\0'
(
if c[j]>='A' & c[j] <='Z'
value[i]= value[i]+c[j]
)
)
compare value
typdef struct node
{
char *str;
struct node*next;
}node;
int check_for_anagram(char *str1,char *str2)
{
int i,j,hash[256]={0};
if(strlen(str1)!=strlen(str2))
return(0);
for(i=0;i<strlen(str1);i++)
hash[(str1[i])-48]++;
for(i=0;i<strlen(str2);i++)
{
if(hash[str2[i]-48]==0)
return(0);
hash[str2[i]-48]--;
}
return(1);
}
void add_anagram(node *hash,int new_array[],int i,int min,char **arr)
{
node *temp,*tem,*head;
head = hash[(new_array[i]-min)];
if(strcmp(head->str,arr[i])>0)
{
temp = malloc(sizeof(node));
temp->str = malloc(strlen(arr[i]));
temp->str = arr[i];
temp->next = head;
hash[(new_array[i]-min)] = temp;
}
else
{
tem = head;
while(head)
{
if(strcmp(head->str,arr[i])>0)
{
temp = malloc(sizeof(node));
temp->str = malloc(strlen(arr[i]));
temp->str = arr[i];
temp->next = head;
tem->next = temp;
}
tem = head;
head = head->next;
}
if(head == NULL)
{
temp = malloc(sizeof(node));
temp->str = malloc(strlen(arr[i]));
temp->str = arr[i];
temp->next = NULL;
tem->next = temp;
}
}
}
sort_by_anagram(char **arr,int length)
{
int i,j,sum,min=0,max = 0;
int new_array[length];
for(i=0;i<length;i++)
{
sum =0;
for(j=0;j<strlen(arr[i]);j++)
{
sum = sum + (arr[i][j]-48)+(arr[i][j]-48)*(arr[i][j]-48);
}
new_array[i]=sum;
}
min = max = new_array[0];
for(i=1;i<length;i++)
{
if(max<new_array[i])
max = new_array[i]
else if(min>new_array[i])
min = new_array[i]
}
node *temp,*head,tem;
node *hash[max-min]=NULL;
for(i=0;i<length;i++)
{
if(hash[(new_array[i]-min)]==NULL)
{
temp = malloc(sizeof(node));
temp->str = malloc(strlen(arr[i]));
temp->str = arr[i];
temp->next = NULL;
hash[(new_array[i]-min)] = temp;
}
else
{
if(check_for_anagram(hash[(new_array[i]-min)]->str,arr[i]))
add_anagram(hash,new_array,i,min,arr);
else
{
for(k=0;k<(max-min);k++)
{
if(hash[k]!=NULL)
{
if(check_for_anagram(hash[k]->str,arr[i]))
{
add_anagram(hash,new_array,k,min,arr);
break;
}
}
}
if(k==(max-min))
//then store that any null place of hash array and then continue;
}
}
}
}
typdef struct node
{
char *str;
struct node*next;
}node;
int check_for_anagram(char *str1,char *str2)
{
int i,j,hash[256]={0};
if(strlen(str1)!=strlen(str2))
return(0);
for(i=0;i<strlen(str1);i++)
hash[(str1[i])-48]++;
for(i=0;i<strlen(str2);i++)
{
if(hash[str2[i]-48]==0)
return(0);
hash[str2[i]-48]--;
}
return(1);
}
void add_anagram(node *hash,int new_array[],int i,int min,char **arr)
{
node *temp,*tem,*head;
head = hash[(new_array[i]-min)];
if(strcmp(head->str,arr[i])>0)
{
temp = malloc(sizeof(node));
temp->str = malloc(strlen(arr[i]));
temp->str = arr[i];
temp->next = head;
hash[(new_array[i]-min)] = temp;
}
else
{
tem = head;
while(head)
{
if(strcmp(head->str,arr[i])>0)
{
temp = malloc(sizeof(node));
temp->str = malloc(strlen(arr[i]));
temp->str = arr[i];
temp->next = head;
tem->next = temp;
}
tem = head;
head = head->next;
}
if(head == NULL)
{
temp = malloc(sizeof(node));
temp->str = malloc(strlen(arr[i]));
temp->str = arr[i];
temp->next = NULL;
tem->next = temp;
}
}
}
sort_by_anagram(char **arr,int length)
{
int i,j,sum,min=0,max = 0;
int new_array[length];
for(i=0;i<length;i++)
{
sum =0;
for(j=0;j<strlen(arr[i]);j++)
{
sum = sum + (arr[i][j]-48)+(arr[i][j]-48)*(arr[i][j]-48);
}
new_array[i]=sum;
}
min = max = new_array[0];
for(i=1;i<length;i++)
{
if(max<new_array[i])
max = new_array[i]
else if(min>new_array[i])
min = new_array[i]
}
node *temp,*head,tem;
node *hash[max-min]=NULL;
for(i=0;i<length;i++)
{
if(hash[(new_array[i]-min)]==NULL)
{
temp = malloc(sizeof(node));
temp->str = malloc(strlen(arr[i]));
temp->str = arr[i];
temp->next = NULL;
hash[(new_array[i]-min)] = temp;
}
else
{
if(check_for_anagram(hash[(new_array[i]-min)]->str,arr[i]))
add_anagram(hash,new_array,i,min,arr);
else
{
for(k=0;k<(max-min);k++)
{
if(hash[k]!=NULL)
{
if(check_for_anagram(hash[k]->str,arr[i]))
{
add_anagram(hash,new_array,k,min,arr);
break;
}
}
}
if(k==(max-min))
//then store that any null place of hash array and then continue;
}
}
}
}
can anyone tell me that the words which are not anagrams...how those words should be arranged?
Suppose the array has abc, def, bac, ijk , acb, fde
The output should be : abc, bac, acb, def, fde, ijk
Hope its clear.
Wrong. There is no requirement for lexicographic sort. The order can be anything as long as each group of anagrams are located in a sequence within the sorted array.
void AnagramSort( string[] input )
{
int index = 0;
for ( int i=0; i < input.Length; i++ )
{
if ( IsAnagram(input[i]) )
{
Swap( input, index, i );
index++;
}
}
// Array is now partitioned with all anagrams on the left, all non-anagrams on right.
// If nicer formatting is desired, QuickSort each block of the subArray
// e.g. Array.Sort( input, 0, index - 1 ) and Array.Sort( input, index, input.Length )
}
var input = new string[] {"orchestra", "cat", "old", "dog", "add", "god", "dad", "carthorse", "tac", "tca", "old", "notanagram"};
Console.WriteLine("Before Sort: ");
Console.WriteLine(string.Join(",", input));
var map = new Dictionary<string, List<string>>();
foreach (var word in input)
{
var wordArray = word.ToLowerInvariant().ToCharArray();
Array.Sort(wordArray);
var sortedWord = new string(wordArray);
if (!map.ContainsKey(sortedWord))
{
map[sortedWord] = new List<string>();
}
map[sortedWord].Add(word);
}
var counter = 0;
foreach (var item in map.Values.SelectMany(list => list))
{
input[counter++] = item;
}
Console.WriteLine("After Sort: ");
Console.WriteLine(string.Join(",", input));
// Example illustrating the use of multimap STL container
#include <iostream>
#include <map>
#include <algorithm>
#include <string>
#include <utility>
using namespace std;
int main()
{
string arr[] = {"abc", "def", "bca", "ijk", "fde", "hello"};
multimap<string, string> m;
string temp;
for (int i = 0; i < 6; ++i)
{
temp = arr[i];
std::sort(temp.begin(), temp.end());
m.insert(pair<string,string>(temp, arr[i]));
}
for (multimap<string, string>::iterator it = m.begin();
it != m.end();
++it)
{
cout << " [" << (*it).first << ", " << (*it).second << "]" << endl;
}
m.clear();
}
int compare(const void* f, const void* s)
{
char *first = *((char**)f);
char *second = *((char**)s);
static vector<int> first_char(26);
static vector<int> second_char(26);
struct setzero
{
void operator()(int& i)
{
i = 0;
}
};
for_each(first_char.begin(), first_char.end(), setzero());
for_each(second_char.begin(), second_char.end(), setzero());
for(int i=0; first[i]; ++i)
{
first_char[first[i]-'a']++;
}
for(int i=0; second[i]; ++i)
{
second_char[second[i]-'a']++;
}
for(int i=0; i<26; ++i)
{
if (first_char[i] != second_char[i])
{
return strcmp(first, second);
}
}
return 0;
}
use qsort(sv, SIZEOF(sv), sizeof(char*), &compare);
For every word create auxiliary array size of 256 and count every character in the word(like counting sort). Sort strings with using auxiliary arrays. Or better count CRC for auxiliary arrays and compare CRC.
struct Word {
const unsigned char* str;
char* hash;
};
bool Compare(Word& w1, Word& w2) {
return (memcmp(w1.hash, w2.hash, 256) < 0);
}
void Sort(const unsigned char** a, int len)
{
Word* arr = new Word[len];
for (int i = 0; i < len; i++) {
arr[i].str = a[i];
arr[i].hash = new char[256];
memset(arr[i].hash, 0, 256);
for (const unsigned char* p = arr[i].str; *p; p++){
arr[i].hash[*p]++;
}
}
sort(arr, arr+len, Compare);
for (int i = 0; i < len; i++) {
a[i] = arr[i].str;
delete [] arr[i].hash;
}
delete [] arr;
}
/* Following code will sort array so that all anagrams are together rather than arranging in lexicographic order.
For Ex. { "ef","bac","tre", "abc","ret"}
{ "ef", "bac","abc", "tre","ret"}
*/
void sort_Anagram(char *a[], size n)
{
int i,j,k;
for(i=0;i <n-2; i++)
{
k=i+1
for(j=k+1; j < n-1 ; j++)
{
if(is_Anagram(a[i],a[j]))
{
swap(&a[k],&a[j]);
k++;
}
}
i=k;
}
}
void swap(char **a, char **b)
{
char **c;
c=b; b=a; a=c;
}
int is_Anagram(char *a,char *b)
{
int i=0, alpha[26];
if(sizeof(a)!=sizeof(b))
return 0;
for(i=0;i<26;i++)
alpha[i]=0;
while(a[0]!= '\0' ))
{
alpha[a[0]-48]++;
a++;
}
while(b[0]!= '\0' ))
{
alpha[b[0]-48]--;
b++;
}
for(i=0;i<26;i++)
{
if( alpha[i]!=0)
return 0;
}
return 1;
}
This is a particular sorting problem. Type of element is string and the key issue is to define the "==", "<" and ">" operation. If string1 and string2 are anagrams, then string1"=="string2; else string1 "<" string2 or string1 ">"string2. Here's my solution:
1. Map the 26 letters to 26 prime numbers starting from 2, e.g. 2, 3, 5, 7,...
2. For a certain string a, compute map(a[0])*map(a[1])*map(a[2])*...*map(a[a.length()-1])
3. Assume string a gets _a and string b gets _b: if (_a==_b), then a==b; if(_a<_b), then a<b; if(_a>_b), then a>b
4. Depend on the compare operation, we just use Quick sort to sort the array.
void AnagramBasedSort(vector<string> &vec)
{
map<string, set<string>> strIdx;
map<string, set<string>>::iterator it;
for (size_t i = 0; i < vec.size(); i++){
string anagram = vec[i];
sort(anagram.begin(), anagram.end());
strIdx[anagram].insert(vec[i]);
}
for (it = strIdx.begin(); it != strIdx.end(); it++){
for (set<string>::iterator sit = it->second.begin(); sit != it->second.end(); sit++){
cout << *sit << ",";
}
}
}
public string SortAna(string str)
{
Dictionary<string, string> ang = new Dictionary<string, string>();
string tmp = "";
if (str.Length <= 0)
return str;
string[] list = str.Split(' ');
for (int i = 0; i < list.Count(); i++)
{
tmp = Sort(list[i]);
if (!ang.ContainsKey(tmp))
{
ang.Add(tmp, list[i]);
}
else
{
string t = ang[tmp];
ang[tmp] = t + " " + list[i];
}
}
foreach (string s in ang.Values)
{
tmp += s;
tmp += " ";
}
return tmp.Trim();
}
If two strings are anagrams, then they shall be the same strings as soon as they are sorted.
Using this approach, you can use the following algorithm
to arrange all the anagram strings of the string array.
For each string @s in the string array @sa sort the string @s and form @skey use the @skey to insert this string @s into a hash table @HT of the form <string, vector<string> > After all the strings are inserted into the @HT, just print out the @HT.And here codepad.org/YhV1wjgY you can find the implemenatation that contains solutions both with and without hash table.
- ashot madatyan June 05, 2012