3
\$\begingroup\$

I've lately been asked in a job interview to program a solution for the well known anagrams problem: given two strings s1 and s2, decide if they are anagrams or not.

Additionally, the characters should be one of [a-zA-Z] and case-insensitive, so AbA and Baa should be valid anagrams.

As a side-note, the interviewer was especially interested in a low space complexity and in particular, to use the heap as less as possible.

In the interview I came up with a Map/histogram solution and in retrospective I implemented another solution, focusing on reducing space complexity.

public class Anagram {

    private static final long [] FIRST_26_PRIMES = new long [] {
            2,
            3,
            5,
            7,
            11,
            13,
            17,
            19,
            23,
            29,
            31,
            37,
            41,
            43,
            47,
            53,
            59,
            61,
            67,
            71,
            73,
            79,
            83,
            89,
            97,
            101
    };

    private static final int A_Z_SIZE = Character.getNumericValue('Z') - Character.getNumericValue('A') + 1;
    private static final int CHARACTER_A_OFFSET = Character.getNumericValue('a');


    public static boolean isAnagram(String s1, String s2) {
        if (s1.length() != s2.length() || s1.length() < 1) {
            return false;
        }
        if (s1.length() < 10) {
            return isAnagramUsingPrimes(s1, s2);
        }
        return isAnagramUsingArray(s1, s2);
    }

    private static boolean isAnagramUsingPrimes(String s1, String s2) {
        long product = 1L;

        for (int i = 0; i < s1.length(); i++) {
            int currChar = Character.getNumericValue(s1.charAt(i)) - CHARACTER_A_OFFSET;
            long currPrime = FIRST_26_PRIMES[currChar];

            product *= currPrime;
        }

        for (int i = 0; i < s2.length(); i++) {
            int currChar = Character.getNumericValue(s2.charAt(i)) - CHARACTER_A_OFFSET;
            long currPrime = FIRST_26_PRIMES[currChar];

            if (product % currPrime != 0) {
                return false;
            }
            product /= currPrime;
        }
        assert product == 1L;
        return true;
    }

    private static boolean isAnagramUsingArray(String s1, String s2) {
        int [] countsArray = new int[A_Z_SIZE];

        for (int i = 0; i < s1.length(); i++) {
            int currChar = Character.getNumericValue(s1.charAt(i)) - CHARACTER_A_OFFSET;
            int count = countsArray[currChar];
            countsArray[currChar] = count + 1;
        }

        for (int i = 0; i < s2.length(); i++) {
            int currChar = Character.getNumericValue(s2.charAt(i)) - CHARACTER_A_OFFSET;
            int count = countsArray[currChar];

            if (count == 0) {
                return false;
            }
            countsArray[currChar] = count - 1;
        }
        return true;
    }
}

So my basic idea is to have two methods, one for short strings (< 10 characters) and a second method for strings of arbitrary lengths.

The method for the shorter strings uses prime number multiplication and division and lives entirely on the stack if I am not mistaken.

The method for the longer strings creates an array with a size of 26, which is the only object that lives on the heap.

I would be happy about any comments/feedback and also further ideas.

BENCHMARK

Out of curiosity I also added a JMH benchmark in order to see which of the two methods performs better. I basically picked a list of 40k 9-letter words which appear in online dictionaries.

The upper-bound of 9 letters was chosen because otherwise the prime method would not work correctly.

As it looks like, the array variant beats the prime variant in terms of ops/ns in my benchmark. My out-of-the-blue guess is that with the prime variant, a lot of multiplication/division/modulo operations are performed while the array variant simply uses increment and decrement on the values.

The allocations, as expected look much better with the prime numbers variant. Here is the benchmark:

import org.openjdk.jmh.annotations.*;
import org.openjdk.jmh.infra.Blackhole;

import java.io.BufferedReader;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.concurrent.TimeUnit;

@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@Warmup(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS)
@Measurement(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS)
@Fork(5)
@State(Scope.Benchmark)
public class AnagramBenchmark {


    private static final int WORDS_ARRAY_SIZE = 40727;
    private String [] words;

    @Setup
    public void setup() {
        try ( InputStream is = getClass().getResourceAsStream("/9-letter-words.txt");
              InputStreamReader isr = new InputStreamReader(is);
              BufferedReader br = new BufferedReader(isr)) {

            words = new String[WORDS_ARRAY_SIZE];

            for (int i = 0; ;i++) {
                String line = br.readLine();
                if (line == null) {
                    break;
                }
                words[i] = line;
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    @Benchmark
    @OperationsPerInvocation(WORDS_ARRAY_SIZE - 1)
    public void primsAnagram(Blackhole bh) {
        for (int i = 0; i < (WORDS_ARRAY_SIZE - 1); i++) {
            String s1 = words[i];
            String s2 = words[i + 1];

            bh.consume(Anagram.isAnagramUsingPrimes(s1, s2));
        }
    }

    @Benchmark
    @OperationsPerInvocation(WORDS_ARRAY_SIZE - 1)
    public void arrayAnagram(Blackhole bh) {
        for (int i = 0; i < (WORDS_ARRAY_SIZE - 1); i++) {
            String s1 = words[i];
            String s2 = words[i + 1];

            bh.consume(Anagram.isAnagramUsingArray(s1, s2));
        }
    }
}

Here is the the command to run it from the console, including a profile that measures allocations as well:

mvn clean install && java -jar target/benchmarks.jar AnagramBenchmark -prof gc

This benchmark gave the following results:

# Run complete. Total time: 00:02:35

Benchmark                                                       Mode  Cnt     Score     Error   Units
AnagramBenchmark.arrayAnagram                                   avgt   25    48.758 ±   0.995   ns/op
AnagramBenchmark.arrayAnagram:·gc.alloc.rate                    avgt   25  1564.522 ±  32.580  MB/sec
AnagramBenchmark.arrayAnagram:·gc.alloc.rate.norm               avgt   25   120.000 ±   0.001    B/op
AnagramBenchmark.arrayAnagram:·gc.churn.PS_Eden_Space           avgt   25  1580.981 ± 157.861  MB/sec
AnagramBenchmark.arrayAnagram:·gc.churn.PS_Eden_Space.norm      avgt   25   121.312 ±  12.255    B/op
AnagramBenchmark.arrayAnagram:·gc.churn.PS_Survivor_Space       avgt   25     0.087 ±   0.019  MB/sec
AnagramBenchmark.arrayAnagram:·gc.churn.PS_Survivor_Space.norm  avgt   25     0.007 ±   0.001    B/op
AnagramBenchmark.arrayAnagram:·gc.count                         avgt   25    81.000            counts
AnagramBenchmark.arrayAnagram:·gc.time                          avgt   25    47.000                ms
AnagramBenchmark.primsAnagram                                   avgt   25   124.970 ±   3.350   ns/op
AnagramBenchmark.primsAnagram:·gc.alloc.rate                    avgt   25    ≈ 10⁻⁴            MB/sec
AnagramBenchmark.primsAnagram:·gc.alloc.rate.norm               avgt   25    ≈ 10⁻⁴              B/op
AnagramBenchmark.primsAnagram:·gc.count                         avgt   25       ≈ 0            counts
\$\endgroup\$
2
\$\begingroup\$

As you are only interested in the value of c-'a'/c-'A' you can replace every usage of Character.getNumericValue(c) - CHARACTER_A_OFFSET with a call to

private static int indexOf(char c) {
    return c - 'A' & ~32;
}

The FIRST_26_PRIMES array can be an int array instead of a long array. You can replace the modulo operation with a multiplication and a subtraction (which could/should be faster).

int currPrime = FIRST_26_PRIMES[indexOf(s2.charAt(i))];
if (product - (product /= currPrime) * currPrime != 0)
    return false;

In the array version you can use post/pre increment and pre decrement (most likely no difference in terms of performance but shorter and in my opinion better readable).

private static boolean isAnagramUsingArray(String s1, String s2) {
    int[] countsArray = new int[26];
    for (int i = 0; i < s1.length(); i++)
        countsArray[indexOf(s1.charAt(i))]++;
    for (int i = 0; i < s2.length(); i++)
        if (--countsArray[indexOf(s2.charAt(i))] < 0)
            return false;
    return true;
}
\$\endgroup\$
  • \$\begingroup\$ Nice, I don't find the last variant more readable though, but I think that's a matter of taste. \$\endgroup\$ – u6f6o Jul 19 '17 at 18:28
3
\$\begingroup\$
  • A method for long strings gives false positive. Once the second string is exhausted, you should return true; only if each element of countsArray is 0.

  • I don't see how case insensitivity is addressed.

  • The FIRST_26_PRIMES suggests that you know a size of the alphabet beforehand. Given this knowledge it doesn't make sense to compute it again.

  • A method for short strings, while correct, uses modulo and division, which can be avoided:

    boolean isAnagramUsingPrimes(string s1, string s2) {
        return primeHash(s1) == primeHash(s2);
    }
    

    where primeHash(string s) computes your product of primes.

\$\endgroup\$
  • 1
    \$\begingroup\$ On the one hand I like your alternative prime solution. On the other it no longer quits early on a character in the second string that wasn't in the first. (For example s1= "aaaaa......" and s2="baaa...." his implementation would return false when checking that a.) \$\endgroup\$ – Imus Jul 19 '17 at 8:06
  • 1
    \$\begingroup\$ Note that his anagram( method first checks that the strings are equal lenght. So your first point isn't valid. If the second string is exhausted without returning false for any of the characters, than the countsArray will be 0. \$\endgroup\$ – Imus Jul 19 '17 at 8:08
  • \$\begingroup\$ Case insensitivity is addressed by Character.getNumericValueit gives you the same value for Character.getNumericValue('a') and Character.getNumericValue('A') \$\endgroup\$ – u6f6o Jul 19 '17 at 8:42
  • \$\begingroup\$ I agree, computing it again is not needed as the size is well-known beforehand, thx. \$\endgroup\$ – u6f6o Jul 19 '17 at 8:45
2
\$\begingroup\$
        for (int i = 0; i < s1.length(); i++) {
            int currChar = Character.getNumericValue(s1.charAt(i)) - CHARACTER_A_OFFSET;
            int count = countsArray[currChar];
            countsArray[currChar] = count + 1;
        }

You could write this more succinctly as

        for (char current : sl.toCharArray()) {
            counts[current - 'a']++;
        }

And then the second would become

        for (char current : s2.toCharArray()) {
             int index = current - 'a';
             if (counts[index] <= 0) {
                 return false;
             }

             counts[index]--;
        }

I find this much easier to follow. Instead of using a custom constant, we use 'a' directly. And we don't create an i variable that we immediately ignore.

I also prefer both of these because they use the natural increment functionality of the language rather than hiding what they're doing by going the long way around.

I'm not crazy about Hungarian Notation, where one embeds the type in the variable name. In my opinion, current and counts are sufficient description. It helps that current is of type char here.

If the interviewer knows that you have limited Java experience, this kind of stuff may not matter. They'll expect to train you in the details. The concept is more important.

It might be worth timing the two methods on the same inputs. Is ten characters the switching point? Also, the primes method may use less heap, but it adds elsewhere with the FIRST_26_PRIMES array.

\$\endgroup\$
  • \$\begingroup\$ s1.toCharArray() in the loop is what I initially had in mind. The problem though is, that Strings are immutable and this method internally performs an System.arrayCopy in order to give you back a "fresh" array, otherwise you could mutate the String internal array. So I basically agree with you, it just would have been worse in terms of space complexity, which was one of the core requirements. \$\endgroup\$ – u6f6o Jul 19 '17 at 8:31
  • \$\begingroup\$ I fully agree on the Hungarian notation, thx! \$\endgroup\$ – u6f6o Jul 19 '17 at 8:31
  • \$\begingroup\$ 10 characters is the switching point because otherwise the long would overflow, so you can fit 101^9 into an long. This is not very sophisticated though. \$\endgroup\$ – u6f6o Jul 19 '17 at 8:34
1
\$\begingroup\$

To add another point:

Error handling and Input Validation

You code is prone to NullPointerException. That might be okay, but I like it when there is a stricter argument checking that reports what exactly is wrong and why. For example:

if (s1 == null)
  throw new IllegalArgumentException("Argument 's1' must be a non-null String");

You should also validate the [a-zA-Z] requirement as soon as possible.

Tests

While probably not part of the assignment, you should write soms testcases that test valid input, and especially the edge cases (empty String, null String, out-of-AZ-range input).

General remark

As a more genetal rule: if you start thinking about how to break your algorithm, many times it will improve.

\$\endgroup\$
  • \$\begingroup\$ I agree, the input validation is not great atm. I thought about adding a check for int currChar = Character.getNumericValue(s1.charAt(i)) - CHARACTER_A_OFFSET; like if (currChar < 0 || currChar > 25) { throw ... } for example. \$\endgroup\$ – u6f6o Jul 19 '17 at 9:06
  • \$\begingroup\$ I am a bit indecisive about the null check on all other points I agree. \$\endgroup\$ – u6f6o Jul 19 '17 at 9:09
  • 1
    \$\begingroup\$ @u6f6o the NPE is a matter of taste I guess. Java does not explicitly tell you which variable caused it, only the line. That is why I prefer the explicit check. (Actually, I prefer the @NonNull annotation :) ) \$\endgroup\$ – RobAu Jul 19 '17 at 9:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.