Microsoft Interview Question
Software Engineer / DevelopersIts kind of tough these days to please interviewer!
For the original problem, it would be easier is the dictionary were already organized into such anagram sets. Then the problem would be reduced to a simple hashing of the given word & assuming the key is the sorted word, it would just take O(word length).
It is during generation of such a key, that you'd have noticed that case must be taken care of. So that keys are always in a single uniform case, such as all lower.
Of course, the cost to organize the original dictionary is high, but its one time.. and probably over repeated uses of it would pay off.
void swap(char* src, char* dst)
{
char ch = *dst;
*dst = *src;
*src = ch;
}
/* permute [set[begin], set[end]) */
int permute(char* set, int begin, int end)
{
int i;
int range = end - begin;
if (range == 1) {
printf("set: %s\n", set);
} else {
for(i=0; i<range; i++) {
swap(&set[begin], &set[begin+i]);
permute(set, begin+1, end);
swap(&set[begin], &set[begin+i]); /* set back */
}
}
return 0;
}
int main()
{
char str[] = "aaa";
permute(str, 0, strlen(str));
return 0;
}
How about having a hash table with keys as sorted letters combined to make a string, of the valid dictionary words and the value as all the possible words in the dictionary that fit into the group of letters which make up the key.
For eg --> Valid words like 'dog','god' will be values in a hash table entry with key as 'dgo' {sorted order of letters that make up the word}
This is precomputed, assuming we have access to the dictionary.
Now try checking for a word, which would essentially mean sorting all the letters of the word. Then basically it many involve performing a look up for the values for this key and print all the words in the value List.
Any opinions ?
public class Dictionary {
public static void main(String[] args){
String[] Dictionary=new String[]{"dog","god","tool","loot","rose","sore"};
HashMap<String,String> h=new HashMap<String, String>();
QuickSort q=new QuickSort();
for(int i=0;i<Dictionary.length;i++){
String temp =new String();
temp= q.quickSort(Dictionary[i]);//sorted word e.g dgo for dog
if(!h.containsKey(temp)){
h.put(temp,Dictionary[i]);
}
else
{
String s=h.get(temp);
h.put(temp,s + " , "+ Dictionary[i]);
}
}
String word=new String(){"tolo"};
String sortedword = q.quickSort(word);
if(h.containsKey(sortedword.toLowerCase())){ //used lowercase to make the words case sensitive
System.out.println("anagrams from Dictionary : " + h.get(sortedword.toLowerCase()));
}
}
}
the code is used to find all permute strings with repetition character
int permute(char* set, int begin, int end)
{
int i;
int range = end - begin;
if (range == 1) {
printf("set: %s\n", set);
} else {
for(i=0; i<range; i++) {
if(set[begin]!=set[begin+i]||i==0)
{
swap(&set[begin], &set[begin+i]);
permute(set, begin+1, end);
swap(&set[begin], &set[begin+i]);
} /* set back */
}
}
return 0;
}
int main()
{
char str[] = "abcd";
clrscr();
permute(str, 0, strlen(str));
return 0;
}
nice one! I guess it has a couple of bugs but does a nice job of explaining the basic concept of using swap to permute.
apologies for my last comment.. There is nothing wrong with this approach. Its perfect!
I solved the question by finding permutations and comparing in dictionary for each valid combination
- Anonymous November 25, 2008He then modified it to accomodate permutations with repetition.
I wasn't able to accomodate the change. He then told me the solution and ask me to break the code.
The key there was that if there were upper and lower case the software will misfunction.(Testing scenario)
I wasn't able to tell this scenario and i was out.