Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
I had the same answer but XOR would be '0' when done on unrelated characters together i.e.
Example:
. XOR on the binary representations of 0,1,2,3 is '0'
but ASCII(0), ASCII(1), ASCII(2) ASCII(3) cannot be used to construct a palindrome
Yes, you're right.
The only other answer I have is sorting the array and counting each element sequence - but it would be O(n log n) + O(n)
Another idea. We could use bitindex with 256 bit size (or 64 bytes) - we'll assume that alphabet is fixed.
We inverse each char bit. After all chars are passed there should be only 1 or 0 bits set for "palindrom string".
So as the size of the bitindex is fixed we have O(n) memory space and we will spend N steps over the initial array and fixed steps over bitindex (to count the number of bits) - so we could say we need less than 2n operations
Then why not just use a hashtable with char as key and a bool as value. then iterate over all the keys in the string. if a char key doesnot exist in the hash table then add the char, true to it. if it exists, then just toggle its bool value. once gone through all the chars, just check that not more than one value in the hash table is true. time complexity is O(n) with first n operations while iterating and then a fixed count of iteration while checking the values in the hashtable. also hash table will be at most have 2^8 or 2^16 elements depending on a char length,
Hi all,
I this problem can be solved using Hashmap. Store Characters in hashmap and increment the value depending on the occurence of character. The scan through the hash and if any two of hash are not n%2. It means that it is not palindrome. and if all of the occurence is mod of 2 == 0 or any one of them is mod of 2 == 1. Then it is palindrome.
The string is a palindrome if there are even copies of every char OR there are even copies of every char except one char. Standard approach to count even number of char is XOR operation. So the algorithm is
- Nickolay Mazurkin October 09, 2011PASS_1 O(n) - make XOR of all chars. If we have XOR_RESULT_1==0 the string is a palindrome. If XOR_RESULT_1!=0 go to the next step
PASS_2 O(n) - make XOR of all char with char code is not equals to XOR_RESULT_1. If XOR_RESULT_2==0 we have a "palindrom string", if XOR_RESULT_2!=0 this string is not a palindrome