## Amazon Interview Question for Quality Assurance Engineers

• 0

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``````

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``

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

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

Comment hidden because of low score. Click to expand.
0

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

Comment hidden because of low score. Click to expand.
0

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

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

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``````

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

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``

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"``````

Comment hidden because of low score. Click to expand.
0

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

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

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

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

Comment hidden because of low score. Click to expand.
0

just use recursive language (refal)

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

all is easy

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. )

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?

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

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

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

}
else
{
Console.WriteLine("Input string is empty!!"); ;
}
}``````

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

}

Comment hidden because of low score. Click to expand.
0

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

}

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

}
}

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

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

public static boolean canBePalindrome(String input){
for (int i=0; i<input.length(); 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;
}

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

private static boolean canBePalindrome(String input){
for (int i=0; i<input.length(); 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;
}

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)
{
{
set.Remove(letter);
}
}

return set.Count <= 1;
}``````

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.

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

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

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{
}
}
return set.size() == 0|| set.size() == 1;
}``````

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.

### 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.