Microsoft Interview Question for Software Engineer / Developers






Comment hidden because of low score. Click to expand.
0
of 0 vote

I solved the question by finding permutations and comparing in dictionary for each valid combination

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

- Anonymous November 25, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- acoader November 26, 2008 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

can u give an algo for finding out all the possibilities of the given word?? like.. how to find the permutations?

- Anonymous November 27, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- dhilip@Gct November 29, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

pls give the algorithm rather than typing the code so that the concept could be easily understood..

- Anonymous February 02, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can anyone pls explain the algorithm to compute permutation

- SM April 11, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@dhilip, it seems really complex, can u please provide an algo?

Thanks.

- Anonymous April 30, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

In the above algorithm, the basic idea used is about the backtracking where we will keep the first character of the string fixed swapping the first character first followed by the other two characters and so on till all possible anagrams are not printed.

- swapnilkant11 June 03, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

@dhilip, it seems really complex, can u please provide an algo?

Thanks.

- Anonymous April 30, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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 ?

- amit October 01, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

AFAIK, in the second algo(to avoid duplicate permutation), we do an extra check before swapping and calling permutation if we are swapping the same two characters. bcos that would lead to redundant calls(on same input giving same output and hence repetition).

- abc November 18, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

    }

}

- megha December 22, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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;
}

- dhilip@Gct November 29, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

In a nutshell, Can you differentiate the two sets of code you have mentioned here?

- Anonymous January 01, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous July 26, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

apologies for my last comment.. There is nothing wrong with this approach. Its perfect!

- Anonymous July 26, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think you didn't read the question properly. It is asked to print only meaningful anagrams which exists in dictionary , not all possible permutations.

- prity July 14, 2013 | Flag


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More