6
\$\begingroup\$

I decided to use Java TreeMap because it seems like a great data structure to fit this problem. However, I am not sure if there could be much simpler methods using better data structure or how I could start improving the time complexity of this algorithm. I would also like to know how I can improve the style of the current code.

Is the time complexity of following algorithm \$O(n \log n)\$?

/**
 * Created by mona on 5/25/16.
 */
import java.util.Map;
import java.util.TreeMap;

public class isAnagram {

    public static boolean areAnagrams( String s1 , String s2 ) {

        if ( s1.length() != s2.length() ) {
            return false;
        }

        Map< Character , Integer > charFrequencyS1 = new TreeMap<>();
        Map< Character , Integer > charFrequencyS2 = new TreeMap<>();

        for ( int i=0 ; i<s1.length() ; i++ ) {
            if ( charFrequencyS1.containsKey(s1.charAt(i)) ) {
                int freq = charFrequencyS1.get(s1.charAt(i));
                charFrequencyS1.put(s1.charAt(i), freq+1);
            }

            else {
                charFrequencyS1.put(s1.charAt(i), 1);
            }

            if ( charFrequencyS2.containsKey(s2.charAt(i)) ) {
                int freq = charFrequencyS2.get(s2.charAt(i));
                charFrequencyS2.put(s2.charAt(i), freq+1);
            }

            else {
                charFrequencyS2.put(s2.charAt(i), 1);
            }

        }

        return charFrequencyS1.equals(charFrequencyS2);

    }

    public static void main( String args[] ) {

        String s1="mona";
        String s2="noea";

        System.out.println(areAnagrams(s1,s2));

    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Are there any restrictions for the String (for example, it can only use english letters, dots, commas and spaces)? Usually, the more restrictions for the input, the more efficient your solution may be. \$\endgroup\$ – SJuan76 May 26 '16 at 20:19
  • \$\begingroup\$ My understanding is generally in programming interviews they don't make crazy restrictions at first but if you continue doing well, they might bring up new restriction in the input (or output). In the question above I was thinking of a very normal string. \$\endgroup\$ – Mona Jalal May 26 '16 at 21:12
  • \$\begingroup\$ No, my point is that if you are told that the String only has, say, ASCII symbols, you may use the ASCII code of each character as an index to an array of frequencies. Way faster than your solution, but will only work with a subset of the possible Strings. \$\endgroup\$ – SJuan76 May 26 '16 at 22:21
  • \$\begingroup\$ I was reading comments from other answers. Just to be clear this is an interview question I have found in glassdoor with no answer so I thought to solve it myself and discuss it here even though my solution might sound naive. I am not disclosing an interview question that I was asked in my own interviews. \$\endgroup\$ – Mona Jalal May 26 '16 at 22:27
  • \$\begingroup\$ If there is no additional info, then your code is ok. \$\endgroup\$ – SJuan76 May 26 '16 at 22:29
7
\$\begingroup\$

Replace the TreeMap with a HashMap since a TreeMap offers \$O(log(n))\$ lookup (containsKey and get) and insertion (put) time whereas a HashMap offers amortized constant or \$O(1)\$ time for those same methods.

The time complexity of this algorithm (with a HashMap) is in fact O(length(s1)) or rather \$O(n)\$ because the contains, add and remove methods of a HashMap work in amortized constant or \$O(1)\$ time (it is \$O(n)\$ when the internal arrays have to be expanded).

You can make the code cleaner by getting rid of all those ifs in the loop. The get method returns null if the key doesn't exist, which helps us remove that containsKey call.

    for ( int i=0 ; i<s1.length() ; i++ ) {
        Integer freq = charFrequencyS1.get(s1.charAt(i));
        charFrequencyS1.put(s1.charAt(i), freq == null ? 1 : freq.intValue() + 1);

        Integer freq = charFrequencyS2.get(s2.charAt(i));
        charFrequencyS2.put(s2.charAt(i), freq == null ? 1 : freq.intValue() + 1);
    }

You could even go a step further and extract those two lines into a method, like

void addCharToMap(Map<Character, Integer> charMap, Character char) {
    Integer freq = charMap.get(char);
    charMap.put(char, freq == null ? 1 : freq.intValue() + 1);
}

And use the above method twice.

One thing to note is that if you are sure that your input is going to be numeric or alphanumeric, you can set the initialCapacity of the HashMap to be 26 or 36 respectively, because that amount is the maximum number of possible unique characters in the strings.

\$\endgroup\$
  • \$\begingroup\$ I have used TreeMap because I need to check if they are equal so order matters \$\endgroup\$ – Mona Jalal May 26 '16 at 6:01
  • 1
    \$\begingroup\$ @MonaJalal Do you mean the last row return charFrequencyS1.equals(charFrequencyS2); ? \$\endgroup\$ – coderodde May 26 '16 at 6:17
  • \$\begingroup\$ yes that is what I mean. \$\endgroup\$ – Mona Jalal May 26 '16 at 6:21
  • 1
    \$\begingroup\$ That method does not take any order into account, only actual content, so you don't need to stick to TreeMap. Even better, if you are given a TreeMap and a HashMap, and both of them has the same content, treeMap.equals(hashMap) will return true. (Try it!) \$\endgroup\$ – coderodde May 26 '16 at 6:29
  • \$\begingroup\$ @MonaJalal The extra cost of iteration on a hashmap rather than on a treemap is, for common implementations of hashmap, a constant factor. \$\endgroup\$ – Taemyr May 26 '16 at 11:52
5
\$\begingroup\$

1 Coding conventions

You abuse your code (a little bit) vertically. Instead of

public static boolean areAnagrams( String s1 , String s2 ) {

    if ( s1.length() != s2.length() ) {
        return false;
    }
    ...

I would write

public static boolean areAnagrams( String s1 , String s2 ) {
    if ( s1.length() != s2.length() ) {
        return false;
    }
    ...

Also, I would fix

... areAnagrams( String s1 , String s2) {

to

... areAnagrams(final String s1, final String s2) {

Like in natural languages, a space before commas is bad style.

2 Map data structure

You should use java.util.HashMap instead of java.util.TreeMap, and that is why: HashMap runs its non-bulk operations in \$\mathcal{O}(1)\$, whereas TreeMap does the same in \$\mathcal{O}(\log n)\$. TreeMap is a good choice whenever you need to traverse the key/value pairs in order by keys, which is not your use case.

Summa summarum

All in all, I had these in mind:

// Easy way: Sort characters and compare. Runs in O(n log n).
public static boolean areAnagrams1(final String s1, final String s2) {
    if (s1.length() != s2.length()) {
        return false;
    }

    final char[] chars1 = s1.toCharArray();
    final char[] chars2 = s2.toCharArray();

    Arrays.sort(chars1);
    Arrays.sort(chars2);

    return Arrays.equals(chars1, chars2);
}

// Runs in O(n).
public static boolean areAnagrams2(final String s1, final String s2) {
    if (s1.length() != s2.length()) {
        return false;
    }

    final Map<Character, Integer> frequencyMap = new HashMap<>();

    for (final char c : s1.toCharArray()) {
        frequencyMap.put(c, frequencyMap.getOrDefault(c, 0) + 1);
    }

    for (final char c : s2.toCharArray()) {
        if (frequencyMap.getOrDefault(c, 0) == 0) {
            return false;
        }

        frequencyMap.put(c, frequencyMap.get(c) - 1);
    }

    return true;
}

Hope that helps.

\$\endgroup\$
  • \$\begingroup\$ why are you using final in final String s1 for argument? \$\endgroup\$ – Mona Jalal May 26 '16 at 6:04
  • 1
    \$\begingroup\$ @MonaJalal final qualifier makes it impossible to reassign to the variable declared with it. You do not actually need it: some people are in love with it and put it wherever possible; others never use it. I think that those people who use final just want to be more verbose about what they code and put it as a sort of documentation. \$\endgroup\$ – coderodde May 26 '16 at 6:08
  • \$\begingroup\$ but String types are immutable so I wonder if that is necessary? \$\endgroup\$ – Mona Jalal May 26 '16 at 6:21
  • 2
    \$\begingroup\$ Correct, Strings are immutable. What I meant is that if you have String name = "Josh";, you can reassign new String value to name. If you, however, add the final to the declaration of name, you would not be able to (erroneously) assign new String value to it. \$\endgroup\$ – coderodde May 26 '16 at 6:23
  • \$\begingroup\$ Ah. I was looking for a method like getOrDefault, I couldn't find one in the Java 7 docs. I'm too inexperienced with Java; I despise the language. \$\endgroup\$ – EvilTak May 26 '16 at 15:56
4
\$\begingroup\$

I think using Maps here goes just over the top. I would simply write:

private static boolean areAnagrams(String one, String  two) {
    if (one.length() != two.length()) {
        return false;
    }
    int[] sortedOne = one.chars().sorted().toArray();
    int[] sortedTwo = two.chars().sorted().toArray();
    return Arrays.equals(sortedOne, sortedTwo);
}
\$\endgroup\$
  • 1
    \$\begingroup\$ True. But this increments the time complexity by a factor of \$\Theta(\log n)\$. \$\endgroup\$ – coderodde May 26 '16 at 15:51
  • \$\begingroup\$ @coderodde Could you elaborate? For me it looks like O(n log n), as the original approach. \$\endgroup\$ – Landei Jun 6 '16 at 7:03
  • \$\begingroup\$ Correct, your version is \$O(n \log n)\$, since you sort the strings. However, building a frequency map using HashMap would improve it to \$O(n)\$. \$\endgroup\$ – coderodde Jun 6 '16 at 7:08
1
\$\begingroup\$

If this is an interview question, I would add something different to think about: Making your code pretty and performant will help, but as it stands this approach would be too slow for actual use on e.g. a website. So now think about the context of where this program might run. Probably on a server, and what are servers good at even though they are not high-speed? They can store large amounts of data in advance and look it up fast.

For a general answer to the problem, I would suggest:

  • At the start of the program (or at some initialization time of the server) create a giant HashMap(?)* with key-list pairs.
  • Sort every word from your natural language dictionary alphabetically,
  • then store it as a key in your map. Also add the unsorted version to the list for that key.
  • If the key already exists, just add the unsorted version of the word to the list.

This method will run a long time depending on the system and size of the word list, but once it is cached somewhere, the lookup time is constant.

When hiring programmers it's actually easy to find people who are good "craftsmen", because everybody can look up clean syntax and concrete problem solutions on the internet. A good way to stand out is to demonstrate problem solving skills that don't have to do anything with the programming language or concrete implementation.

*I'm unsure about which data structure would be the best, as it's implementation specific. In C# I've used a generic Dictionary.

Here is my version in C# just to show how I tackled the problem. There might be missing some error handling and there are probably faster algorithms for sorting, but this already fast enough for a real-life application.

/// <summary>
/// Retrieves all anagrams for a given input word from the buffer.
/// </summary>
public static List<string> GetAnagrams(string input, Dictionary<string, List<string>> buffer)
{
    return buffer[SortWord(input)];
}

/// <summary>
/// Given a list of words, creates a buffer of sorted word keys and all matching anagrams in the list.
/// </summary>
public static Dictionary<string, List<string>> CreateBuffer(List<string> words)
{
    var buffer = new Dictionary<string, List<string>>();
    foreach (var word in words)
    {
        string sorted = SortWord(word);
        if (buffer.ContainsKey(sorted))
            buffer[sorted].Add(word);
        else
            buffer.Add(sorted, new List<string>() { word });
    }
    return buffer;
}

public static string SortWord(string input)
{
    if (input == null)
        throw new ArgumentNullException(nameof(input));

    char[] output = input.ToArray();
    Array.Sort(output);
    return new string(output);
}
\$\endgroup\$
  • \$\begingroup\$ This is an interesting approach, but it seems to solve a different problem. You have made all sorts of assumptions about the requirements that haven't been given. The solution by @Landei is simple to follow and will work for any two strings. Your approach massively increases the memory overhead and complexity(what happens if an error occurred reading the dictionary) and doesn't work for all strings (consider people's names, words from other languages, strings with spaces, strings of apparently random characters etc). \$\endgroup\$ – forsvarir May 26 '16 at 14:04
  • \$\begingroup\$ Sure, I'm only showing another side to look at the problem from. Especially in interviews, it's important to show you can look at problems from different angle, but also for a real-life implementation, my approach is the one used for anagram websites, so that was the first thing that came to mind. You could also turn the question around and say you're making a puzzle word game and have totally different requirements. The other answers have already given good tips to refactor the given code. \$\endgroup\$ – Xarbrough May 26 '16 at 15:30

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.