Vaclav
BAN USERTry to use linked list.
Generally interviewers don't interested in common API, they are interested in algorithms. So, BigInteger not suitable. Array cannot be used too because interviewers interested in "unlimited" numbers, so only linked list is apropriate for this task.
I'll propose another one solution:
final static int LETTERS_LEN = 256;
public static boolean isAnagram(String s1, String s2) {
if (s1 == null || s2 == null)
return false;
int len = s1.length();
if (len != s2.length() || len < 2)
return false;
int[] letters = new int[LETTERS_LEN];
for (int i = 0; i < len; i++) {
letters[s1.charAt(i)]++;
letters[s2.charAt(i)]--;
}
for (int i = 0; i < LETTERS_LEN; i++) {
if (letters[i] != 0) {
return false;
}
}
return true;
}
This solution is based upon the following. When you are scanning first string you are "raising" rate for every letter in hash. In the same (!) loop you are downgrades it for every letter founded in the second string. So, if all letters in the both words will be appeared exactly the same times, their value in hash position must be zero.
And the test for proof:
public class AnagramStringTest {
private static final String[] in = { "node", "salvador dali", "stream" };
private static final String[] out = { "done", "avida dollars", "master" };
@Test
public void test() {
assertFalse( foo.bar.StringUtil.isAnagram(null, null));
assertFalse( foo.bar.StringUtil.isAnagram(null, ""));
assertFalse( foo.bar.StringUtil.isAnagram("", null));
assertFalse( foo.bar.StringUtil.isAnagram("", ""));
assertFalse( foo.bar.StringUtil.isAnagram("1", "2"));
assertFalse( foo.bar.StringUtil.isAnagram("1", "21234"));
assertFalse( foo.bar.StringUtil.isAnagram("23", "34"));
assertFalse( foo.bar.StringUtil.isAnagram("23", "45"));
for (int i = 0; i < in.length; i++){
assertTrue( foo.bar.StringUtil.isAnagram(in[i], out[i]));
}
}
}
Eugene, I can agree with you due to technical issues. But I'm still thinking that interviewers would like see something "linked list"-based. Maybe I'm wrong :)
- Vaclav September 21, 2012P.S. You can easily find answer for this question at Laakmann's book "CRACKING THE CODING INTERVIEW, FOURTH EDITION", page 108