## Microsoft Interview Question for Software Engineer in Tests

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

sort the 2 words and compare if both strings are same then both are anagrams

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

Another approach with O(n) space and time is use a hash to keep track of count of each char in string1, While parsing string2, decrement the count of the char in hash table(delete when count becomes zero). If hash table is empty at end, its anagram.

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

Also unlike array we do not need to allocate space in advance for any possible character. If there are only 50 different characters in a string. Size of HashMap will be 50 only after iterating first string.

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

I will use extra space to solve this question, as sorting is a costly affair.

Regarding extra space, we only need to use memory for 256 character, not of O(n) if we know that string is made up of only ASCII characters. We can do more optimization on space, if we can put more restriction on our data type like if string will consist only of lower and upper character than I need space for only 50 characters......

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

From "http://www.careercup.com/question?id=18382"

solution was provided by "nirmalr" (modified slightly)

O(n) algorithm to check anagram :
+++++++++++++++++++++++++++++++++

variant of counting sort can be used here as the range is known.

algorithm :

input : string1, string2 (to be checked)

step 1: allocate one integer array c[26]
step 2: initialize elements of array c to zero

step 3 : for each character in string1
increment corresponding element in c by one (ex : for 'a', c[0]++)

step 4 : for each character in string2
decrement corresponding element in c by one (ex : for 'a', c[0]--)

step 5 : if "c" contains all zero then string1 & 2 are anagrams.

for optimization, step 3 and 4 can be merged together as they are independent activities.

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

AWESOME, thanks buddy!

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

wat awesome.. this is what hash map is doing

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

LOL... "wat awesome".

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

I bet he is a Chinese

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

@Anonymous, are you racist cock sucker?

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

nirmalr's algorithm assumes there is only alphabet characters. What about numbers and special characters? :)

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

bool isAnagram(string s1,string s2)
{
return s1.sort()==s2.sort();
}

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

This is the standard algorithm to find anagrams.
The logic is to find signatures of the string (in this case its alphabatical order) and then compare the signatures.
Anagrams have the same signatures.

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

i have a different approach using prime numbers.
all u need to do is maintain an array of first 26 prime numbers.

then for input string1 find its unique product value:
product_string1=1
for(i=0 to strlen(string1)) product_string1*=a[string[i]-'a']

if(strlen(string2)==strlen(string2)){
then find the product for string 2 in similar fashion
product_string2=1
for(i=0 to strlen(string2)) product_string2*=a[string[2]-'a']
if(product_string1==product_string2) string is anagram of string 1
}

Time complexity: Find the first 26 prime numbers, this will be done once only.
After that for every input it can said in o(n) time whether it is anagram or not where n is the string size. and space complexity is only int array of 26 to store first 26 prime numbers.

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

Try multiple 43 fives times and 45 five times.. and it will overflow..

elegant solution if we have something like big decimal data type.. however operations with big decimal will introduce their own complexity..

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

Test cases..
compare with null
compare with one char less
compare with few chars less
compare with extra chars
compare with upper and lower case
compare with numbers
compare with spl chars
compare with white space
compare with just last char diff(cat , pac)

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

This question can also be inverted with a very clever trick: ensure two strings are not anagrams. In this case take XOR of two strings and see if it is non-zero :). I should ask this in the interview !

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

XOR == 0 does not mean anagrams..

String AA and BB when xored will yield zero however they are not anagrams..

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

/**
* This follows a mathematical formula ab = cd & a+b=c+d cannot be the same for any numbers greater than 0
*/
public static void findAnagram(String str1, String str2)
{
str1 = str1.toLowerCase();
str2 = str2.toLowerCase();

int sum = 0;
int mult = 0;
int sum2 = 0;
int mult2 = 0;

if(str1.length()!=str2.length()){System.out.println("An anagram should have the same length"); return;}

for(int i=0;i<str1.length();i++)
{
sum += str1.charAt(i);
mult *= str1.charAt(i);
sum2 += str2.charAt(i);
mult2 *= str2.charAt(i);
}
if(sum == sum2 && mult == mult2)
{
System.out.println("The strings are anagram");
}
}

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

I used a Hashmap, the complexity is O(n)

``````public class CheckAnagrams {

public static void main(String[] args){

String str1=new String();
String str2=new String();

Scanner s=new Scanner(System.in);
System.out.println("Enter the String1");
str1=s.nextLine();

System.out.println("Enter the String2");
str2=s.nextLine();
CheckAnagrams c=new CheckAnagrams();

System.out.println("the strings are anagrams:      " + c.checkAnagrams(str1,str2));

}

boolean checkAnagrams(String str1, String str2){

HashMap<Character,Integer> h=new HashMap<Character, Integer>();

if(str1.length()!=str2.length()){

return false;
}

else

{    int dup ;

for(int i=0;i<str1.length();i++)   {

dup=1;
if(h.containsKey(str1.charAt(i))) {

dup=h.get(str1.charAt(i));

dup++;

}

h.put(str1.charAt(i),dup);

}

for(int i=0;i<str2.length();i++)   {

if(!h.containsKey(str2.charAt(i))) {

return false;
}

else{
dup=h.get(str1.charAt(i));
dup--;
h.put(str1.charAt(i),dup);

}

}

for(Character ch:h.keySet() ){

if(h.get(ch)>0){

return false;
}

}

return true;

}

}
}``````

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