Amazon Interview Question for Quality Assurance Engineers


Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
7
of 7 vote

1. Make a suffix tree for all permutation of T such that T$Reverse(T)#
2. Check for all permutation for same node

- Vir Pratap Uttam April 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
4
of 4 vote

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

- JK April 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

If x is odd, there should be not at least but at most one char count to odd.

- Anonymous April 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

If x is odd there should be not at least but at most one char count to odd

- madi.sagimbekov April 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Or just exactly one char should be count to odd, if x is odd

- madi.sagimbekov April 06, 2015 | Flag
Comment hidden because of low score. Click to expand.
2
of 4 vote

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;
    }

- amp April 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You code will fail if string is like that say example str = "pyyypaaaa"

- Shakti June 15, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

your code will fail if str = "pyyypaaaa" for example

- Shakti June 15, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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;
	}

- Adnan Ahmad April 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

// ZoomBA one liner :
#|select ( mset(s.toCharArray) ) :: {  $.o.value % 2 != 0 }| <= 1

- NoOne October 09, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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");		
	}

- Sunil_Padiyar April 03, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- JK April 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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"

- umang.agrawal91 April 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Rajesh April 08, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- Alex April 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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"));
	}
}

- Partha April 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- Teh Kok How April 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

just use recursive language (refal)

- andy April 04, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

all is easy

- Andrey April 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Pallindrom
{
=<Prout 'yes'> /*empty string */
s.symb = <Prout 'yes'> /*string Of 1 char*/
s.symb e.string s.symb = <Palindrom e.string>
e.other = =<Prout 'Not'> /* error string */

'welcome to MEPHI. )

- Andy (andykx@rambler.ru) April 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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?

- Joshua April 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;           
        }

- anu.anssy19 April 06, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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();
            }
        }

- Aarti April 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}
}



}

- Allwin S April 20, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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");
}
}
}

}

- Allwin S April 20, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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");
}

}
}

- Abhimanyu Chopra April 22, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- vivek.katarya May 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- Anonymous July 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- Anonymous July 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static bool CanBePalindrome(string input)
        {
            HashSet<char> set = new HashSet<char>();

            foreach (char letter in input)
            {
                if (!set.Add(letter))
                {
                    set.Remove(letter);
                }
            }

            return set.Count <= 1;
        }

- MS coder September 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Catalin September 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

my $s = 'happa paa spp';
foreach my $i (0 .. length($s) - 1) {
local $\ = "\n"; # add newline to print
if (substr($s, $i) =~ /((.*).?(??{ quotemeta reverse $2 }))/) {
if(length($1) > 1) {
print "$1";
}
}
}

- Raghavendra pai July 06, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

$string= "haa paa spp" return all palindrome option like aa,aa,pp
my $s = 'happa paa spp';
foreach my $i (0 .. length($s) - 1) {
local $\ = "\n"; # add newline to print
if (substr($s, $i) =~ /((.*).?(??{ quotemeta reverse $2 }))/) {
if(length($1) > 1) {
print "$1";
}
}
}

- Anonymous July 06, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- zhengyino1 December 09, 2016 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More