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."
Is it OK to assume that O(k) space complexity is acceptable, where k is the size of the alphabet?
ReplyDeleteFirst I'd ask if I could do it programming in Scala ;-)
ReplyDeletedef 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)
@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).
ReplyDelete@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, ;)
What about this: http://pastebin.com/bBVWQh8r
ReplyDelete@wonkydonky The garbage produced should also be O(1). Can you think of a better collection for storing 0 and 1's? ;)
ReplyDeleteWhat about a string array of "true" and "false" values ;)
ReplyDeleteI was thinking something more efficient (and a natural choice in this situation)
ReplyDeleteHmm. boolean storage requirements are VM dependent right? - it could well be represented as int's under the hood. What else could I use?
ReplyDeleteEven if there is a more efficient solution I'm not sure why my solution's garbage isn't O(1).
@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.
ReplyDeleteFor the collection I would use BitSet which in this case wraps a single long value.
What about this http://pastebin.com/uy6P2Wf7
ReplyDeleteThanks for the response. The Character object was a little redundant.
ReplyDeleteHowever 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.
v1.1 : http://pastebin.com/AfLDjC7v
ReplyDelete1 int , 1 char , 1 byte, one pass
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 :-/
ReplyDeleteAnd i'm missing a bit of logic in my second pass. Damm this is addictive.
ReplyDeletewait a sec. the checking method should have two args: source palindrome and an anagram candidate to validate, right?
ReplyDeleteotherwise it makes no sense
@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@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@fel For extra obscurity; how might using (c & 31) help combine the two if clauses.
ReplyDeleteThis is my first attempt at this problem. I'm going to try to make a better solution than this.
ReplyDeletepackage 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;
}
}
}
}
What about this solution?
ReplyDeletestr.equals(new StringBuffer(str).reverse().toString());
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@luiX_
ReplyDeleteIf you input as kaka, it would fail, when it should not
@szcukg just forgot the "anagram" part... xDDD
ReplyDeleteWas thinking just about checking string's a palindrome :P
@Peter Lawrey : damned! You were absolutely right;)
ReplyDelete2 int, 1 char, one pass, one test solution :
http://pastebin.com/jhZZ30Zm
@szcukg Unfortunately the code in the comment is considered to be HTML so you need to put < instead of < :(
ReplyDelete@fel, this fails for characters between 'Z' and 'a' (it counts them)
ReplyDeleteBTW: What if you were to use (1 << c) instead of (1 << (c & 31)) ? ;)
O(n) space to radix sort, but I guess it is O(1) extra space if you do an in place radix sort.
ReplyDeleteO(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.
(untested) (parity) counting sort version
ReplyDeletehttps://gist.github.com/1477344
@Peter Lawrey
ReplyDeleteSorry, 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
@Chad Brewbaker In the palindrome examples on wikipedia, case is ignored and D matches with d.
ReplyDelete@fel to do a range comparison in one compare you can try.
ReplyDeleteif (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. ;)
@Chad
ReplyDeleteYou'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.
@szcukg
ReplyDeleteYeah '.' 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 .
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.
ReplyDeleteFor 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