Google Interview Question
Web:
www.google.com
|
HQ:
Mountain View, CA
Overview |
| |
Salaries |
| |
Reviews |
| |
Interviews |
| |
Photos |
| |
Jobs |
| |
|
1,230 Interview Reviews |
Back to all Google Interview Questions & Reviews
Interview questions and reviews posted anonymously by interview candidates
Interview Question for Engineering at Google:
Oct 20, 2011
Helpful Question?
Yes |
No
Inappropriate?
Answers & Comments (4)
Oct 26, 2011
not a big deal, but make sure to check the lengths for #3 (or for really any of the solutions).
1. sorting and strcmp is straightforward and no extra memory, but n log n.
2. not too bad for memory. O(n)
3. could get nasty with super long strings. O(n)
1. sorting and strcmp is straightforward and no extra memory, but n log n.
2. not too bad for memory. O(n)
3. could get nasty with super long strings. O(n)
Helpful Answer?
Yes |
No
Inappropriate?
Nov 12, 2011
#2 and #3 are basically the same thing. the first thing in any algorithm here is to check lengths. the next thing i would do it make an array of ints the length of the range of input. then, i would read the first one in, incrementing the corresponding integer for its position. then compare this list of character frequency with the second string for a match. if you do not know the range of the input, or it is otherwise prohibitive, you can do a has from each character object to the integer keeping record of its frequency.
Helpful Answer?
Yes |
No
Inappropriate?
Nov 12, 2011
more clearly:
boolean areAnagrams?( String s1, String s2)
{
int[] frequencies = new int[128]; //assuming ascii. make a hash table for unicode
for( int i = 0; i < frequencies.length; i++)
{
frequencies[ i ] = 0;
}
for(int i = 0; i < s1.length(); i++)
{
frequencies[ (int)s1.charAt(i) ]++;
}//now we have an int array corresponding to letter frequencies
for(int i = 0; i < s2.length(); i++)
{
frequencies[ (int)s2.charAt(i) ]--;
}//now, if they are anagrams, all will be zero
for(int = 0; i < s1.length(); i++)
{
if( frequencies[ (int)s1.charAt(i) ] )
{
return false;
}
}
return true;
}
boolean areAnagrams?( String s1, String s2)
{
int[] frequencies = new int[128]; //assuming ascii. make a hash table for unicode
for( int i = 0; i < frequencies.length; i++)
{
frequencies[ i ] = 0;
}
for(int i = 0; i < s1.length(); i++)
{
frequencies[ (int)s1.charAt(i) ]++;
}//now we have an int array corresponding to letter frequencies
for(int i = 0; i < s2.length(); i++)
{
frequencies[ (int)s2.charAt(i) ]--;
}//now, if they are anagrams, all will be zero
for(int = 0; i < s1.length(); i++)
{
if( frequencies[ (int)s1.charAt(i) ] )
{
return false;
}
}
return true;
}
Helpful Answer?
Yes |
No
Inappropriate?
To comment on this
question,
Sign In with Facebook or
Sign Up
You might also be interested in: Interview Questions, Engineering Interview Questions, Google Interview
1 of 1 people found this helpful
by srikanth:
1. sort them and strcmp()
2. hash them ( function should be independent of characte sequence) and if they map to same value they are anagrams.
3. assign primary numbers to each letter of the word. get the product. do the same with target. if product matches then they are anagrams.