Microsoft Interview Question
Country: India
Interview Type: In-Person
1. Take an auxiliary array & copy all the strings of the original array.
2. Sort each of the string in auxiliary array.
3. Take another auxiliary array keeping track of the indices of the original array.
4. Sort auxiliary array & simultaneously change the index array.
5. Print the original array according to the index array[while checking contents of the auxiliary array, we want only anagrams right.].
Time complexity: O(N*d*log N)
where d is the max number of chars in a string.
EDIT:
Taking an example:
Lets say, the array contains "abc","abd","bac","bca"
Aux array after sorting each slot: "abc","abd","abc","abc"
The index array would be: 0,1,2,3
After sorting aux array: "abc","abc","abc","abd"
Corresponding Index array: 0,2,3,1
Print Original array a/c to Index array:
abc[at index 0]
bac[at index 2]
bca[at Index 3]
Don't print "abd" [Index 1], it hasn't any anagram.
Umm... Just wanted to ask at following step:
< After sorting aux array: "abc","abc","abc","abd"
Corresponding Index array: 0,2,3,1 >
How did you sort string..U will use strcmp() right ? But then what will be the complexity
Do merge sort.Yes strcmp() will be used for comparing two strings.
That is how time complexity comes out to be N*d*log(N).
I have taken care of time complexity of strcmp(). Here its 'd'.
@shondik..
why are u sorting the individual stings...
charecters of those strings will contibute to forming many anagrams..
if sorted
many annagrams wont be formed then
@shreyans, Individual strings are being sorted so that after sorting the array, all the anagrams will be closer. Where did you find it not working?
can you provide counter example?
Please correct me if I'm wrong but the anagrams are 'abc' and 'cba' but not 'abc' and 'acb'.
'abc' and 'acb' are permuations but not anagrams, right?
1. copy string into auxiliary space
2. sort string kept in auxiliary space
3. compute hash key from sorted string.
4. store (unsorted/original) string in a given hash bucket
For any string, we can now get all its anagrams by simply computing hash function and printing all strings kept in that bucket
Assume we have a function isAnagram(char *s,char *d) which returns true if strings pointed to by s and d are anagram.
Now Fix one string and check if we have anagram for that .If found then print else move to next string.
Implementation of isAnagram() will be using first sorting of both strings and then strcmp()
/* WAP to return all anagrams from the array of strings. */
// WORKING CODE || RECURSIVE
#include<stdio.h>
#include<string.h>
int anagram(char S[10],int l,char C[10])
{
char D[10];
int j,k,m=strlen(C),i;
for(j=0;j<=m;j++)
{
for(k=m;k>j;k--)
D[k]=C[k-1];
D[k]=S[m];
D[m+1]=NULL;
for(k=j-1;k>=0;k--)
D[k]=C[k];
if((m+1)==l)
printf("%s\n",D);
else
anagram(S,l,D);
}
return 0;
}
int main()
{
char S[10],C[10];
C[0]=NULL;
gets(S);
printf("\n");
anagram(S,strlen(S),C);
return 0;
}
if there will be repeating of word then this algo will give same string multiple times, but one can remove it by comparing either is al-ready printed or not(do-it urself)
-------------------
http://www.geeksforgeeks.org/archives/767
There it is good code
# include <stdio.h>
/* Function to swap values at two pointers */
void swap (char *x, char *y)
{
char temp;
temp = *x;
*x = *y;
*y = temp;
}
/* Function to print permutations of string
This function takes three parameters:
1. String
2. Starting index of the string
3. Ending index of the string. */
void permute(char *a, int i, int n)
{
int j;
if (i == n)
printf("%s\n", a);
else
{
for (j = i; j <= n; j++)
{
swap((a+i), (a+j));
permute(a, i+1, n);
swap((a+i), (a+j)); //backtrack
}
}
}
/* Driver program to test above functions */
int main()
{
char a[] = "ABC";
permute(a, 0, 2);
getchar();
return 0;
}
Algorithm Paradigm: Backtracking
Time Complexity: O(n*n!)
This generates all the permutations of the input string. I think the key observation is that an anagram is a permutation of the characters in a string that's also a WORD. So what we would need in this situation is a dictionary which tell us whether or not a given permutation is an English word. All n! permutations would have to be examined anyway...that's the lower bound AFAIK.
Sort each of the string word individually. O(nlogn)
- Anonymous July 22, 2012Then insert each of the strings in a trie. Mark the end of the word in the trie by increasing the count.
Traverse trie and wherever count >=1 print the string and the value. The value gives the anagrams to those strings.
Hope its clear ! :)