Amazon Interview Question
Quality Assurance EngineersCountry: United States
Interview Type: Phone Interview
Get the string length as x
Put all characters with respective count in a map or array with count as value and character ascii as index
Scan through the map and apply the following logic
if x is even
then each unique character count should be even
else
there should be atleast one unique character count to odd, rest all should be even
How about using XOR. If the result is 0 or outside the bounds of a lower case character then the result is false. Otherwise check to make sure that only one instance of the found results exists as a character within the string.
public static boolean isPalindronePossible(String s) {
// check for null
if(s == null || s.isEmpty()) {
return false;
}
// XOR each character against each other within the string
int test = 0;
for(int i = 0; i < s.length(); i++) {
test ^= (int) s.charAt(i);
}
// this means even characters
if(test == 0) {
return true;
}
// this means not a palindrone possible given that the result
// is outside the lowercase character range
if(test < 97 || test > 122) {
return false;
}
// check the result ensuring that the result exists and only one instance
// of the character exists, without this something like "zab" would return true
int count = 0;
for(int i = 0; i < s.length(); i++) {
if((int) s.charAt(i) == test) {
count++;
if(count > 1) {
return false;
}
}
}
return count == 1;
}
public static boolean canBePalidrome(String str){
int[] charCount = new int[Character.MAX_VALUE];
for(char ch : str.toCharArray()) {
charCount[ch]++;
}
if(str.length()%2 == 0){
for(int count : charCount){
if(count % 2 == 1){
return false;
}
}
} else {
int oddCount = 0;
for(int count : charCount){
if(count % 2 == 1){
if(oddCount > 1){
return false;
} else {
oddCount++;
}
}
}
}
return true;
}
This is my solution:
Logic,
1. From the given string, get the unique characters and put it in an ArrayList.
2. For even length string --> check if the unique Arraylist size is less than or equal to given string's length / 2 OR for odd length string --> check if the unique Arraylist size is less than or equal to (given string's length / 2 + 1)
If true - palindrome
Code:
public static void stringAnagramPalindrome(String str){
if(str==null || str.isEmpty()){
System.out.println("The given string" + str + " or its anagram(s) is not a palindrome");
return;
}
str.toLowerCase();
int len = str.length();
char [] charArr = str.toCharArray();
ArrayList<Character> uniqueList = new ArrayList<Character>();
for(int i = 0; i<=charArr.length-1; i++){
if (uniqueList.indexOf(charArr[i])==-1){
uniqueList.add(charArr[i]);
}
}
for(int k=0; k<uniqueList.size(); k++){
System.out.println("Item in uniquelist" + k + "th element is " + uniqueList.get(k));
}
if (len%2==0 && uniqueList.size()<=len/2 || uniqueList.size()<=len/2+1)
System.out.println("The given string " + str + " or its anagram is a palindrome");
else
System.out.println("The given string " + str + " or its anagram is NOT a palindrome");
}
Get the string length as x
Put all characters with respective count in a map or array with count as value and character ascii as index
Scan through the map and apply the following logic
if x is even
then each unique character count should be even
else
there should be atleast one unique character count to odd, rest all should be even
Given a string, how do we check if any anagram of it can be a palindrome?
For example let us consider the string "AAC". An anagram of it is "ACA" which is a palindrome. We have to write a method which takes a string and outputs true if we can form a palindrome from any anagram of the given string. Otherwise outputs false.
We can immediately think of a solution where we can generate all anagrams of the given string and check if there is any palindrome exists. But this approach is very lengthy and has exponential time complexity (O(n!)).
The key to solve this problem efficiently is to understand how a palindrome is formed. We all know that a palindrome reads the same when you read from left to right or right to left.
A palindrome can be broken into two halves. where in the first half is the reverse of second half. In case of odd length of strings, we have to ignore the middle character.
So for every character in the first half, there is a corresponding matching character in the second half. This indicates that all the characters in a string must occur even number of times except for one which appears in the middle of the string.
Hence if we check if there is at most one character with odd occurrences in the string we can say that we can form a palindrome from any anagram.
Here is the Python code which implements this algorithm. For simplicity, I assumed that the input string contains only lowercase English alphabets.
import os
def palindrome (input_str):
count = []
for i in xrange(0,26):
count.append(0)
for i in xrange(0,len(input_str)):
ch = input_str[i]
count[ord(ch) - ord('a')] = count[ord(ch) - ord('a')] + 1
oddOccur = 0
for i in xrange(0,len(count)):
if (oddOccur > 1):
return False
if ((count[i] % 2) == 1):
oddOccur = oddOccur + 1
return True
input_str = "travel"
if (palindrome(input_str)):
print "String is palindrome"
else:
print "String is not a palindrome"
Another solution in Python:
Please provide if you have better solutions.
def ispalindrome(word):
n = len(word)
lowerword = word.lower()
dictcount = {i:lowerword.count(i) for i in set(lowerword)}
oddCount = 0
if n%2 == 0:
for key in dictcount.keys():
if dictcount[key] % 2 != 0:
return False
else:
for key in dictcount.keys():
if dictcount[key] % 2 != 0:
oddCount += 1
if oddCount > 1:
return False
else:
return True
def main():
word = raw_input("Enter the word : ")
if ispalindrome(word):
print "True"
else:
print "False"
if __name__ == '__main__':
main()
Output:
>python palindrome.py
Enter the word : mmo
True
Enter the word : yakak
True
Enter the word : travel
False
I believe with a palidrome there can only be one (or zero) characters of an odd count in the string. The rest of the characters counted in the string have to be even.
bool canBePalidrome(string s)
{
map<char,int> mCount;
for(int i=0;i<s.length();i++)
{
mCount[s[i]]++;
}
map<char,int>::iterator iter = mCount.begin();
bool bOddFound = false;
while(iter != mCount.end())
{
if(iter->second % 2 != 0)
{
if(bOddFound)
return false;
bOddFound = true;
}
iter++;
}
return true;
}
package random;
import java.util.Map;
import java.util.HashMap;
class PalindromCheck {
public boolean isPalindromPossible(String str){
if(str == null || str.length() == 0){
System.out.println("empty string");
return false;
}
else {
boolean isEven = (str.length() % 2 == 0);
Map<Character, Integer> charMap = new HashMap<>();
for(char c: str.toCharArray()){
if(charMap.get(c) == null){
//if a char is entered only for the first time
charMap.put(c, 1);
}
else{
//already value present in the map, increment the count
charMap.put(c, charMap.get(c) + 1);
}
}
//Now all the values are present in the map.
if(isEven){
//checking for the even String,
//logic is every element present in the string must be even
for(Map.Entry<Character, Integer> me : charMap.entrySet()){
if(me.getValue() % 2 != 0){
//if in a string there is odd number of a character
System.out.println("there are odd number of a char :"+ me.getKey()+" so this cant be a palindrome ");
return false;
}
}
System.out.println("All the chars in the even string are even , so it can form a palindrome");
return true; //else all the chars in the string are even, palindrome possible
}
else{
//for odd number of chars in the string
//logic is there can be at max only one char in the map that can be odd
//all the other chars must be even.
int numberOfOddChars = 0;// number to count how many odd chars are found in the map
for(Map.Entry<Character,Integer> me : charMap.entrySet()){
if(me.getValue() % 2 != 0){
//odd char is now found, increment the numberOfOddChars
numberOfOddChars ++;
}
}
if(numberOfOddChars == 1){
//only 1 odd char found, so palindrome can be formed
System.out.println("Only One odd char found, palindrome possible");
return true;
}
return false;// default case i.e. if there are more than one odd char then
}
}
}
public static void main(String[] args) {
PalindromCheck demo = new PalindromCheck()
;
System.out.println(demo.isPalindromPossible("yakak"));
}
}
Implementation using std::map
bool isPalindrome(string const& s)
{
size_t odd = 0;
size_t length = s.length();
map<char, size_t> counts;
for (string::const_iterator it = s.begin(); it != s.end(); it++)
counts[*it]++;
for (map<char, size_t>::const_iterator it = counts.begin(); it != counts.end(); it++)
if (it->second % 2)
if (!(length % 2))
return false;
else if (++odd > 1)
return false;
return true;
}
Implementation using sort() one for-loop:
bool isPalindrome1(string const& s)
{
size_t count = 1, odd = 0;
size_t length = s.length();
string s1(s);
sort(s1.begin(), s1.end());
for (size_t i = 1; i < length; i++)
{
if (s1[i] == s1[i - 1])
count++;
else
{
if (count % 2)
if (!(length % 2))
return false;
else if (++odd > 1)
return false;
count = 1;
}
}
return true;
}
Maybe I'm misunderstanding the question...I think the only thing that should return true is if all elements are the same. The statement is "test weather a string and all strings that can be made using the characters", so doesn't that mean every anagram must equal a palindrome? If it read something like "test weather a string or any strings that can be made using the characters" then the submitted code samples would be more accurate. Right?
private bool CheckPalindrome(string inputstring)
{
bool result=false;
char[] resultchars = inputstring.ToCharArray();
Dictionary<string, int> dresult = new Dictionary<string, int>();
int count = 0;
foreach (char c in inputstring.ToUpper().ToCharArray())
{
if (dresult.ContainsKey(c.ToString()))
{
dresult[c.ToString()] = Convert.ToInt32(dresult[c.ToString()]) + 1;
}
else
{
dresult.Add(c.ToString(), 1);
}
}
if (inputstring.Length % 2 == 0)
{ //even
foreach (int i in dresult.Values)
{
if (i % 2 != 0)
{
result = false;
break;
}
result = true;
}
}
else
{ //odd
foreach (int i in dresult.Values)
{
if (i % 2 != 0)
{
count++;
}
}
if (count > 1)
result = false;
else
result = true;
}
return result;
}
Below code is written in c#
public static void CheckEWordIsPalindrome(string inputString)
{
Hashtable ht = new Hashtable();
if (!string.IsNullOrEmpty(inputString))
{
for (int counter = 0; counter < inputString.Length; counter++)
{
if (ht.Contains(inputString[counter]))
{
ht[inputString[counter]] = Convert.ToInt32(ht[inputString[counter]]) + 1;
}
else
{
ht.Add(inputString[counter], 1);
}
}
int odd = 0; ;
foreach (DictionaryEntry entry in ht)
{
if (Convert.ToInt32(entry.Value) == 1)
{
odd++;
}
}
if (odd > 1)
Console.WriteLine("Word is not Palindrome");
else
Console.WriteLine("Word is Palindrome");
Console.ReadLine();
}
else
{
Console.WriteLine("Input string is empty!!"); ;
Console.ReadLine();
}
}
package amazon;
/**
* @author Allwin S
*
*/
public class CanFormPalindrome {
/**
* @param args
*/
public static void main(String[] args) {
String arr[] = {"mmoo", "yakak", "travel","abcdefghijklmnopqrstuvwxyz","absdba"};
for (String s : arr) {
int sum = 0;
for(int i = 0; i< s.length(); i++){
int n = s.charAt(i);
sum ^= n;
}
if(sum ==0 || (sum >= 90 && sum <= 122))
System.out.println(s);
}
}
}
UPDATED
package amazon;
/**
* @author Allwin S
*
*/
public class CanFormPalindrome {
/**
* @param args
*/
public static void main(String[] args) {
String arr[] = { "mmoo", "yakak", "travel",
"abcdefghijklmnopqrstuvwxyz", "absdba" };
for (String s : arr) {
int sum = 0;
for (int i = 0; i < s.length(); i++) {
int n = s.charAt(i);
sum ^= n;
}
if (sum == 0 || (sum >= 90 && sum <= 122)) {
System.out.println(s + " = true");
} else {
System.out.println(s + " = false");
}
}
}
}
import java.util.*;
class FindPalindrome{
//function will try to form palindrome
static String findPalindrome(String str)
{
char ch=' ';
ArrayList<Character> al1=new ArrayList<Character>();
ArrayList<Character> al2=new ArrayList<Character>();
for(int i=0;i<str.length();i++)
{
ch=str.charAt(i);
if(al1.contains(ch))
{
al2.add(ch);
}
else
{
al1.add(ch);
}
}
Collections.sort(al1);
Collections.sort(al2);
String palindrome="";
for(char c:al1)
{
if(al2.contains(c))
{
palindrome=palindrome+c;
}
else{
ch=c;
}
}
palindrome=palindrome+ch;
int len=al2.size();
len--;
for(int i=len;i>=0;i--)
{
palindrome=palindrome+al2.get(i);
}
return palindrome;
}
//function to check the recieved String is palindrome or not
static boolean checkPalindrome(String checkString)
{
String test=checkString;
boolean b=false;
StringBuffer s1=new StringBuffer(test);
test=s1.reverse().toString();
if(test.equals(checkString))
{
b=true;
}
return b;
}
public static void main(String[] args)
{
Scanner in=new Scanner(System.in);
//Take String input from user
System.out.println("Enter String ");
String str=in.next();
// gets String from findPalindrome() method
String palindromeString=findPalindrome(str);
if(str.length()==palindromeString.length())
{
boolean b=checkPalindrome(palindromeString);
System.out.println(palindromeString);
if(b){
System.out.println("Given String "+str +" Palindrome String "+palindromeString);
}
else
{
System.out.println("Palindrome can not be formed for this String");
}
}
else
{
System.out.println("Palindrome can not be formed for this String");
}
}
}
Logic:
XOR the characters of the strings.
If the result is 0, then it's a palindrome (XOR of a number with itself is 0, so all numbers must exist in pairs)
If the result is not 0, then check if the output lies in {A-Z, a-z}. If it does, it can be a palindrome.
bool canItBePalindrome (char *str)
{
int len = strlen (str);
int xr = str[0] - '0';
for (int i = 1; i < len; ++i)
{
xr = xr ^ (str[i] - '0');
}
if (xr == 0 ||
(((xr + '0') >= 'A') && ((xr + '0') <= 'Z')) ||
(((xr + '0') >= 'a') && ((xr + '0') <= 'z')))
return true;
else
return false;
}
public static boolean canBePalindrome(String input){
List<String> list = new LinkedList<String>();
for (int i=0; i<input.length(); i++){
list.add(String.valueOf(input.charAt(i)));
}
boolean isCenterLetterFound = false;
while (!list.isEmpty()){
String targetLetter = list.get(0);
if(list.indexOf(targetLetter) != list.lastIndexOf(targetLetter)){
list.remove(list.indexOf(targetLetter));
list.remove(list.lastIndexOf(targetLetter));
}else if (!isCenterLetterFound){
list.remove(list.indexOf(targetLetter));
isCenterLetterFound = true;
}else{
return false;
}
}
return true;
}
private static boolean canBePalindrome(String input){
List<String> list = new LinkedList<String>();
for (int i=0; i<input.length(); i++){
list.add(String.valueOf(input.charAt(i)));
}
boolean isCenterLetterFound = false;
while (!list.isEmpty()){
String targetLetter = list.get(0);
if(list.indexOf(targetLetter) != list.lastIndexOf(targetLetter)){
list.remove(list.indexOf(targetLetter));
list.remove(list.lastIndexOf(targetLetter));
}else if (!isCenterLetterFound){
list.remove(list.indexOf(targetLetter));
isCenterLetterFound = true;
}else{
return false;
}
}
return true;
}
The simplest way to solve this is to use a frequency array. Why this works:
if the length of a string is a even number, all letters should be even numbers too,
if the length of a string is a odd number, only one letter has to appear as a odd number, others needs to be even
If these 2 properties are violated, our string can not be a palindrome no matter how you permute it.
public boolean validPalindrome(String s) {
if(s == null || s.length() == 0){
return false;
}
Set<Character> set = new HashSet<Character>();
for(int i = 0; i < s.length(); i++){
char c = s.charAt(i);
if(set.contains(c)){
set.remove(c);
}else{
set.add(c);
}
}
return set.size() == 0|| set.size() == 1;
}
- Vir Pratap Uttam April 12, 2015