3
\$\begingroup\$

Description:

Given two strings check if those two are permutation of each other. Its expected that input string can contain ASCII characters.

Code:

class Main {
  public static boolean isPermutation(String s1, String s2) {
    if (s1 == null || s2 == null) {
      throw new IllegalArgumentException("Input string cannot be null");
    }
    if (s1.length() != s2.length()) {
      return false;
    }
    int[] count = new int[256];
    for (int i = 0; i < s1.length(); i++) {
      int index = s1.charAt(i) - '0';
      count[index] += 1;
    }
    for (int i = 0; i < s2.length(); i++) {
      int index = s2.charAt(i) - '0';
      count[index] -= 1;
    }
    for (int i = 0; i < count.length; i++) {
      if (count[i] != 0) return false;
    }
    return true;  
  }

  public static void main(String[] args) {
    //System.out.println(isPermutation(null, null) == true);
    System.out.println(isPermutation("", "") == true);
    System.out.println(isPermutation("a", "") == false);
    System.out.println(isPermutation("", "b") == false);
    System.out.println(isPermutation("a", "a") == true);
    System.out.println(isPermutation("a", "b") == false);
    System.out.println(isPermutation("foo", "bar") == false);
    System.out.println(isPermutation("eat", "ate") == true);
    System.out.println(isPermutation("1010", "1100") == true);
  }
}

Questions:

  1. From interview point of view are the test cases sufficient?

  2. am I using Java features correctly?

  3. I think I can merge the two for loops but I did above coding in time bounded fashion, can it raise red flag from interviewer perspective?

PS: According to me I can use map if the input string can contain unicode characters.

\$\endgroup\$

1 Answer 1

Reset to default
4
\$\begingroup\$

Test cases

From an interview perspective, I would suggest that you're missing the test case for the null-handling. Creating full unit test cases in an interview is overkill, but is it too much to just add:

try {
    System.out.println("Should not happen: " + isPermutation(null, ""));
} catch (IllegalArgumentException e) {
    System.out.println("Got expected exception for null");
}

Java features

Your use of Java features is OK, but you are not really doing a whole lot.

Bugs

Your spec says the strings will contain ASCII characters, and, to me, things like spaces and punctuation -_!@#$%.... are all ASCII. Your code subtracts the 0 character value from the string's character to get the array index. This will fail for the spaces and punctuation. Why do you need to do the 0 subtraction at all? The code would work for all ASCII without that anyway.

Algorithm

My biggest suggestion is about the algorithm, anyway. Your code counts each character and compares the counts. A much simpler, and intuitive algorithm, is to sort the characters and compare the results.....

Consider:

private static String normalize(String value) {
    char[] chars = value.toCharArray();
    Arrays.sort(chars);
    return new String(chars);
}


public static boolean isPermutation(String s1, String s2) {
    if (s1 == null || s2 == null) {
      throw new IllegalArgumentException("Input string cannot be null");
    }
    return normalize(s1).equals(normalize(s2));
}
\$\endgroup\$
7
  • 1
    \$\begingroup\$ Can you please let me know why it would fail for the space? also the running time complexity of my algorithm is O(n) which is less than your suggestion i.e. O(nlogn), wdyt? \$\endgroup\$ Commented Mar 27, 2018 at 21:24
  • 2
    \$\begingroup\$ The index for a space, in your code, is int index = s2.charAt(i) - '0' which is ..... 32 - 48 which is ... -16, and that will never be a valid array index. \$\endgroup\$ Commented Mar 27, 2018 at 21:27
  • \$\begingroup\$ I thought int index = s2.charAt(i) - '0' = 32 - 0 \$\endgroup\$ Commented Mar 27, 2018 at 21:31
  • \$\begingroup\$ Check it out: ideone.com/ATBtCi \$\endgroup\$ Commented Mar 27, 2018 at 21:33
  • 1
    \$\begingroup\$ As for the \$O(n \log n)\$ issue, yes, you're correct that it's complexity is worse than \$O(n)\$ ... but you are also allocating large arrays, etc. In practice, I expect the code I suggest to have better performance for small input values, and for larger inputs, the log n characteristics are essentially constant, so won't scale badly at all. \$\endgroup\$ Commented Mar 27, 2018 at 21:43

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.