Yahoo Interview Question
Software Development ManagersTeam: Y! Suite
Country: United States
Interview Type: In-Person
There is much better way to check if two strings are anagrams without using any maps in O(n) time and O(1) space where n is the length of the longest string.
1) Assign each of the 26 letters a unique prime number i.e. {'a'=>2, 'b'=>3, 'c'=>5, 'd'=>7, 'e'=>11, ..., 'l' = 37, ..., 's' => 67, .... ,'t' => 71,.... 'z' => 101}
2) All the anagrams of a word will have the same UNIQUE product. For example: prod(TEA) = prod(ATE) = prod(ETA) = prod(TAE) = prod(AET) = prod(EAT) = 71*11*2 = 154
public static final int primes[] = {2, 3, 5, 7, 11, 13, ......, 101} ;
public boolean isAnagram (String word1, String word2)
{
if(word1.length() != word2.length())
return false;
word1 = word1.toLower();
word2 = word2.toLower();
int word1Key = 1;
for(int i=0; i<word1.length; i++)
word1Key*=primes[word1[i]-'a'];
int word2Key = 1;
for(int i=0; i<word2.length; i++)
word2Key*=primes[word2[i]-'a'];
return word1Key == word2Key;
}
We are comparing the character of str2 with the str1. so increment the count on the character when encounter the character in str1 and decrement in str1.
if the length of the two string is different return false and if any of the element in the count array is non zero then return false .
bool areAnagram(char *str1, char *str2)
{
// Create two count arrays and initialize all values as 0
int count[NO_OF_CHARS] = {0};
int i;
for (i = 0; str1[i] && str2[i]; i++)
{
count[str1[i]]++;
count[str2[i]]--;
}
if (str1[i] || str2[i])
return false;
for (i = 0; i < NO_OF_CHARS; i++)
if (count[i])
return false;
return true;
}
complexity O(n).
space complexity : 265*sizeof(int)
But it's O(n+m) where m is NO_OF_CHARS. e.g. if your strings only have 5 chars each (areAnagram ("hello","elolh")), it is inefficient because it still loops through all possible chars.
I think better would be:
int lenstr1=0;
int lenstr2=0;
for (i=0; str1[i]; i++) {
count[str1[i]]++; //increment letter element same as your program
lenstr1++;
}
for (i=0; str2[i]; i++) {
if (--count[str2[i]] <0) {return false;} //decrement letter - if <0 then we had too many of this letter, so they're anagrams.
lenstr2++;
}
if (lenstr1!=lenstr2) {return false;} //if lengths are unequal, they're not anagrams
return true; //if lengths are the same and str2 didn't have too many of any particular letter, then it's an anagram
There is much better way to check if two strings are anagrams without using any maps in O(n) time and O(1) space where n is the length of the longest string.
1) Assign each of the 26 letters a unique prime number i.e. {'a'=>2, 'b'=>3, 'c'=>5, 'd'=>7, 'e'=>11, ..., 'l' = 37, ..., 's' => 67, .... ,'t' => 71,.... 'z' => 101}
2) All the anagrams of a word will have the same UNIQUE product. For example: prod(TEA) = prod(ATE) = prod(ETA) = prod(TAE) = prod(AET) = prod(EAT) = 71*11*2 = 154
public static final int primes[] = {2, 3, 5, 7, 11, 13, ......, 101} ;
public boolean isAnagram (String word1, String word2)
{
if(word1.length() != word2.length())
return false;
word1 = word1.toLower();
word2 = word2.toLower();
int word1Key = 1;
for(int i=0; i<word1.length; i++)
word1Key*=primes[word1[i]-'a'];
int word2Key = 1;
for(int i=0; i<word2.length; i++)
word2Key*=primes[word2[i]-'a'];
return word1Key == word2Key;
}
Time: O(n)
Space: 265*size of (int)
Disclaimer : Not sure it this works for alphabets other than English.
public static boolean areAnagrams(String first, String second){
if(first.length() != second.length())
return false;
int[] char_values = new int[256];
char charAt;
int uniqueCharsInFirstString = 0;
int completedCharsSecondString = 0;
for (int i = 0; i < first.length(); i++) {
charAt = first.charAt(i);
if(char_values[charAt] == 0){
uniqueCharsInFirstString++;
}
char_values[charAt]++;
}
for (int i = 0; i < second.length(); i++) {
charAt = second.charAt(i);
if(char_values[charAt] == 0)
return false;
--char_values[charAt];
if(char_values[charAt] == 0){
completedCharsSecondString++;
if(uniqueCharsInFirstString == completedCharsSecondString){
return (i == second.length()-1);
}
}
}
return false;
}
Generate the hash code for both the strings, then check the hash value. O(n) time complexity.
1.O(n) time. Space complexity depends on the type of character-set involved. For instance, ASCII requires 128, ANSI 256, and unicode demands 2^16 -1.
if(n1==0 && n2==0)
return 1;
if(n1==0 || n2==0)
return 0;
if(n1!=n2)
return 0;
for(i=0;i<n1;i++)
t[s[i]]++;
for(i=0;i<n2;i++)
{
if(t[s2[i]]==0)
return 0;
}
return 1;
If space is an issue but we can compromise on time: O(n lg n) time and O(1) space where n is the length of the longer string, if they are not anagrams.
if(n1==0 && n2==0)
return 1;
if(n1==0 || n2==0)
return 0;
if(n1!=n2)
return 0;
sort(s1);
sort(s2);
for(i=0;i<n1;i++)
{
if(s1[i]!=s2[i])
return 0;
}
return 1;
typedef unsigned int uint;
#define ALPH_SIZE 26 //for English alphabet
//so long as lower, upper case parts live in contiguous
//ranges of any underlying encoding (ascii, etc.)
uint count[2*ALPH_SIZE + 1]; //lower, upper case & other junk
uint h( char x )
{
return (x >= 'a' && x <='z' ? x-'a' : //lower case
x >= 'A' && x <='Z' ? x-'A'+ALPH_SIZE : //upper case
2*ALPH_SIZE) //all other characters
}
/* precondition: you supply it with strings on English alphabet
that is, the rest of the code in your program
should not create junk strings/characters if you want proper results */
if( s1.length != s2.length ) return false;
for(i=0; i < s1.length ; i++) count[h(s1[i])]++, count[h(s2[i])]--;
for(i=0; i < 2*ALPH_SIZE ; i++) if ( count[i] ) return false;
return true;
this is solution in python .It uses dictionary dataype .The solution can be obtained in O(n).Here the sample inputs given are "rescue" and "secure".You can change it as per your need
#!/usr/local/bin/python2.7
dic = {}
flag = 0
inp1 = "rescue"
inp2 = "secure"
for i in range(0,len(inp1)) :
dic[inp1[i]] = 0
for i in range(0,len(inp1)) :
dic[inp1[i]] = dic[inp1[i]] + 1
for i in range(0,len(inp2)) :
if dic[inp2[i]] > 0 :
dic[inp2[i]] = dic[inp2[i]] - 1
else :
flag = 1
break
if flag == 0 :
for key in dic.keys() :
if dic[key] > 0 :
flag = 1
break
if flag == 1 :
print "not anagram"
else :
print "anagram"
Time: O(n)
Space: O(1)
If s2 is an anagram of s1, then s2 will be part of s1s1
eg:
s1 = computer
s2 = tercompu
then s2 will be part of s1s1 = computercomputer
just check is s2 is part of s1s1
package edu.sjsu.java.string;
import java.util.Arrays;
public class AnagramTest {
public static boolean isAnagram(String s1, String s2) {
if (s1 == null || s2 == null) {
return false;
}
if (s1.length() != s2.length()) {
return false;
}
char[] c1 = s1.toCharArray();
char[] c2 = s2.toCharArray();
Arrays.sort(c1);
Arrays.sort(c2);
String sc1 = new String(c1);
String sc2 = new String(c2);
return sc1.equals(sc2);
}
}
All we have to do is to tell if the two strings have exact same characters if I'm not misunderstanding from what I read from the wikipedia.
Thus, we can just use a hash table with the key as the hash and the value of number of times it shows up. Once we have this hash table, we traverse through it.
All the values should be divisible by 2 (i.e. value %2 ==0) if not, it is not an anagram.
This is O(n) time and constant space.
public static boolean areAnagrams(String s1, String s2){
if(s1.length() != s2.length())
return false;
s1 = s1.toLowerCase();
s2 = s2.toLowerCase();
int xorResult = 0;
for(int index = 0; index < s1.length(); index ++){
xorResult ^= s1.charAt(index);
}
for(int index = 0; index < s2.length(); index++){
xorResult ^= s2.charAt(index);
}
return xorResult == 0;
}
There is much better way to check if two strings are anagrams without using any maps in O(n) time and O(1) space where n is the length of the longest string.
1) Assign each of the 26 letters a unique prime number i.e. {'a'=>2, 'b'=>3, 'c'=>5, 'd'=>7, 'e'=>11, ..., 'l' = 37, ..., 's' => 67, .... ,'t' => 71,.... 'z' => 101}
2) All the anagrams of a word will have the same UNIQUE product. For example: prod(TEA) = prod(ATE) = prod(ETA) = prod(TAE) = prod(AET) = prod(EAT) = 71*11*2 = 154
- zahidbuet106 May 12, 2014