Java Interview Question; Anagram of a Palindrome

Overview

In many interview questions, what they are looking for is a simple solution to an apparently complex problem. Unfortunately, the solutions are usually obvious if you know the solution, but very hard to come up with in an interview situation. ;)

Anagram of Palindrome

Write a method to test if a String is an anagram of a palindrome. The method should have O(n) time complexity and O(1) space complexity. You can assume all letters are between ' ' (space) and 'z'. Assume only letters matter and case is ignored.

e.g.
"kayak"
"Rats live on no evil star"
"A man, a plan, a canal, Panama"
"Doc, note: I dissent. A fast never prevents a fatness. I diet on cod."

The solution

A brute force approach is to generate anagrams and test if they are a palindromes. This is not required. All you need to test is if the String is the sort of string which can be turned into a palindrome.

Sample solution available HERE

Comments

  1. Is it OK to assume that O(k) space complexity is acceptable, where k is the size of the alphabet?

    ReplyDelete
  2. First I'd ask if I could do it programming in Scala ;-)

    def palindromAnagram(s: String) =
    s.groupBy((c: Char) => c).values
    .filterNot(_.length % 2 == 0)
    .size <= 1


    Group all the same characters together.
    Filter all those with an even number of characters.
    Find out if we are left with one or less odd character.

    (Okay, okay, so it doesn't really satisfy the O(1) space complexity requirement)

    ReplyDelete
  3. @aix, as long as it fixed for the problem and doesn't depend on the length of the message, I would call it O(1).

    @Karadoc, That's pretty cool and shows the general idea. DOes it filter only letters a to z and ignore case? (Something I imagine is also pretty easy in scala)

    Once we have a solution, we could compare the performance, ;)

    ReplyDelete
  4. What about this: http://pastebin.com/bBVWQh8r

    ReplyDelete
  5. @wonkydonky The garbage produced should also be O(1). Can you think of a better collection for storing 0 and 1's? ;)

    ReplyDelete
  6. What about a string array of "true" and "false" values ;)

    ReplyDelete
  7. I was thinking something more efficient (and a natural choice in this situation)

    ReplyDelete
  8. Hmm. boolean storage requirements are VM dependent right? - it could well be represented as int's under the hood. What else could I use?
    Even if there is a more efficient solution I'm not sure why my solution's garbage isn't O(1).

    ReplyDelete
  9. @wonkydonky, Using Character could be creating an object for each character, however in this specific case those are cache. It could be better to use char type.

    For the collection I would use BitSet which in this case wraps a single long value.

    ReplyDelete
  10. What about this http://pastebin.com/uy6P2Wf7

    ReplyDelete
  11. Thanks for the response. The Character object was a little redundant.
    However it's got be thinking. What about this: http://pastebin.com/AqTtSMHJ

    Uses 2 bytes, a char and an int for storage and does two passes of the string.

    ReplyDelete
  12. v1.1 : http://pastebin.com/AfLDjC7v
    1 int , 1 char , 1 byte, one pass

    ReplyDelete
  13. Nice fei, but you still need 2 ints (one for the array). However I was too hasty as my second byte should actually be an int :-/

    ReplyDelete
  14. And i'm missing a bit of logic in my second pass. Damm this is addictive.

    ReplyDelete
  15. wait a sec. the checking method should have two args: source palindrome and an anagram candidate to validate, right?

    otherwise it makes no sense

    ReplyDelete
  16. @ikcileibp I state at the end of the question this is not required, you only need to determine if the string could be turned into a palindrome, not find what the palindrome is.

    ReplyDelete
  17. @fel since you like low level answers, for bonus points, can you write "if('a'<=c && c<='z')" with one comparison instead of two. (Can be slightly faster;)

    ReplyDelete
  18. @fel For extra obscurity; how might using (c & 31) help combine the two if clauses.

    ReplyDelete
  19. This is my first attempt at this problem. I'm going to try to make a better solution than this.

    package tp;
    import java.util.Enumeration;
    import java.util.Scanner;


    import com.sun.org.apache.xalan.internal.xsltc.runtime.Hashtable;

    public class AOP {

    /**
    * @param args
    */
    public static void main(String[] args) {
    // TODO Auto-generated method stub
    System.out.println("Enter input:");
    Scanner scan=new Scanner(System.in);
    String input=scan.nextLine();
    input=input.toLowerCase();
    Hashtable alphabets=new Hashtable();
    for ( int i=0;i1 )
    { System.out.println("Input string is not an anagram of a palindrome ");
    break;
    }
    }



    }

    }

    ReplyDelete
  20. What about this solution?

    str.equals(new StringBuffer(str).reverse().toString());

    ReplyDelete
  21. I'm not able to correctly submit my code. I don't know what might be wrong, but the full code ain't getting published. Some formatting issue? Any other way through which I can publish?

    ReplyDelete
  22. @luiX_
    If you input as kaka, it would fail, when it should not

    ReplyDelete
  23. @szcukg just forgot the "anagram" part... xDDD

    Was thinking just about checking string's a palindrome :P

    ReplyDelete
  24. @Peter Lawrey : damned! You were absolutely right;)

    2 int, 1 char, one pass, one test solution :
    http://pastebin.com/jhZZ30Zm

    ReplyDelete
  25. @szcukg Unfortunately the code in the comment is considered to be HTML so you need to put &lt; instead of < :(

    ReplyDelete
  26. @fel, this fails for characters between 'Z' and 'a' (it counts them)

    BTW: What if you were to use (1 << c) instead of (1 << (c & 31)) ? ;)

    ReplyDelete
  27. O(n) space to radix sort, but I guess it is O(1) extra space if you do an in place radix sort.

    O(alphabet size) to do (parity) counting sort on a bitvector.

    A bit trie with a parity counter at the leaves would be elegant for sparse alphabets. If your alphabet is fixed a priori then you could write off the construction of the bit trie as preprocessing.

    ReplyDelete
  28. (untested) (parity) counting sort version
    https://gist.github.com/1477344

    ReplyDelete
  29. @Peter Lawrey

    Sorry, i didn't get your single comparison trick :(.
    However, despite my solution counts characters between 'Z' and 'a', the bitmask discard them before the bitcount, therefore only letters matters ; (btw, are you sure the isAnagramOfAPalindrome test fails because my unit tests are still ok)

    using 1<<c is very tricky (with 32 bits int ;) ). I made some performance test in order to compare (1<<c) and (1<<(c&31)) ; there is huge differences between jdk1.6 and 1.7 (64 bits version) but i miss time to investigate.

    my new proposition :
    http://pastebin.com/BtA6ydY3

    ReplyDelete
  30. @Chad Brewbaker In the palindrome examples on wikipedia, case is ignored and D matches with d.

    ReplyDelete
  31. @fel to do a range comparison in one compare you can try.

    if (c + Integer.MIN_VALUE - 'A' <= 'z' + Integer.MIN_VALUE - 'A')

    This maps 'A' to MIN_VALUE (any value less than this underflows to be close to MAX_VALUE) The compiler combines the constants. Note: Whether you add or subtract MIN_VALUE makes no difference. ;)

    ReplyDelete
  32. @Chad
    You're program would not work when there is an odd number of special characters, even when there are blank spaces and just one odd character.

    ReplyDelete
  33. @szcukg

    Yeah '.' can be odd regardless of string length if you only have one sentence. You can fix that corner case by ignoring the parity of special characters, or always setting them to even.

    @Peter if I remember my ASCII that is a simple bitwise AND. If you want to get really complicated you could give it a dictionary and list of allowable sentence grammars. Keeping that in O(n log n) let alone linear time would be extremely challenging. For example http://en.wikipedia.org/wiki/Buffalo_buffalo_Buffalo_buffalo_buffalo_buffalo_Buffalo_buffalo .

    ReplyDelete
  34. An anagram is a type of word, the result of rearranging the letters of a word or phrase to produce a new word or phrase, using all the original letters exactly once.

    For example: orchestra can be rearranged into carthorse or cat can be rearranged into act.

    We can find out the anagram strings using below algorithm:

    public static boolean isAnagram(String str1, String str2) {
    if (str1 == null || str2 == null) {
    return false;
    } else if (str1.length() != str2.length()) {
    return false;
    }

    Map map = new HashMap();

    for (int i = 0; i < str1.length(); i++) {
    char characters = str1.charAt(i);
    int charInStr1 = map.containsKey(characters) ? map.get(characters) : 0;
    map.put(characters, ++charInStr1);
    char charFromStr2 = str2.charAt(i);
    int charsInRight = map.containsKey(charFromStr2) ? map.get(charFromStr2) : 0;
    map.put(charFromStr2, --charsInRight);
    }

    for (int occurrences : map.values()) {
    if (occurrences != 0) {
    return false;
    }
    }
    return true;
    }

    I found below useful links for more information

    Write program to find if Strings are anagram

    ReplyDelete

Post a Comment

Popular posts from this blog

Java is Very Fast, If You Don’t Create Many Objects

System wide unique nanosecond timestamps

Unusual Java: StackTrace Extends Throwable