## Amazon Interview Question for Quality Assurance Engineers

• -1
of 1 vote

Country: India
Interview Type: In-Person

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

The logic to check a palindrome is easy and not included here.

Case 1: the digits in the number are capable of forming a palindrome number
1) capture frequencies of each digits in an array
2) all frequencies will be even or there will be only 1 digit with odd frequency
3) In case of former append a string of half the frequency of a digit to the output string e.g. '22'+outputString+'22'
4) In case of latter make the odd frequency digit as the central digit in the output string. Now repeat the above step for the rest of the digits.

Case2: In case the digits in the number are not capable of forming a palindrome number and we have to creating the palindrome by adding/removing min number of digits
1) Same as above case
2) To identify case 2 the logic is that if there are more than 1 digit with odd frequency then it cannot be converted into a palindrome.
3) add/remove digits to make all frequencies even except 1
4) repeat steps of case 1

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

Can you provide space/time bounds please? I think this will be O(n):O(n) in space:time, where n = number of digits in original number

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

``````#!/usr/bin/python
import sys

def isPalini(string):
return string == string[::-1]

def count_freq(string):
count_list = {}
for i in string:
if count_list.has_key(str(i)) == False:
count_list[str(i)] = 1
else:
value = count_list.get(str(i))
value += 1
count_list[str(i)] = value
return count_list

def make_palin(string, unique, recur_flag):
if isPalini(string) == True:
return True, str("None"), str("None")
c_list = count_freq(string)
print len(string)
if len(string)%2 == 0:
char = 0
dup = []
for i in string:
if c_list[i]%2 != 0:
return False, None
else:
dup.append(i)
if recur_flag == "set":
return True, dup, unique
else:
return True, dup, False
else:
char = 0
for i in string:
if c_list[i]%2 != 0:
return make_palin(str(string[:string.find(i)]) + (string[string.find(i)+1:]), i, str("set"))
if __name__ == "__main__":
token = make_palin(sys.argv, 0, str("not set"))
if token == 1:
if token == str("None"):
print "palindrome"
else:
print "palindrome"
get_dup = set(token)
unique = token
l = ('').join(get_dup)
if unique != 0:
print l + str(token) + l[::-1]
else:
print l + l[::-1]``````

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

Not sure if you can use Java APIs, but here is the most elegant solution

``````public static boolean isPalindromeSimple(String str) {
return str.equals(new StringBuilder(str).reverse().toString());
}``````

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

Assuming that the integer is in string form... if not you can convert it to a string of course

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

``````private static bool IsNumberPalin(int number)
{
int msbdiv = 10; // find highest power of 10 that is smaller than number
while (number / msbdiv != 0)
{
msbdiv *= 10;
}

msbdiv /= 10;

while (number >= 10)
{
// find msb and lsb
int msb = number / msbdiv;
int lsb = number % 10;

if (msb != lsb) return false;

// shrink the number by removing msb and lsb.
number = number % msbdiv; // remove msb
number /= 10;             // remove lsb

// update msb, since number is 2 digit smaller.
msbdiv /= 100;
}
return true;
}``````

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

Converting to strings, and solving for a palindrome probably won't impress the interviewer, although you can mention it.

There is a way to reverse a number and then compare it against the original, but you can face overflow problems. A more clever way to do this is you need to check if the left most digit is the same as the right most digit, strip them both and repeat while the number != 0.

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

The string conversion is not to check if its a palindrome or not, but to make it a palindrome if its not.

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

``````public static bool IsPalindrome(int n)
{
while (n > 0)
{
// last digit
var l = n % 10;

// first digit calculation by dividing to closest power of 10
var powerOf10 = 1;
while (n / powerOf10 > 10)
{
powerOf10 *= 10;
}

var m = n / powerOf10;

if (l != m)
{
return false;
}

// cut first and last digits
n = (n % powerOf10) / 10;
}

return true;
}``````

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

For Korser code, a small correction:
while (n / powerOf10 > 10) >>>>>> while (n / powerOf10 >= 10)

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

``````import java.io.BufferedReader;
import java.io.IOException;

public class CheckPalindrome {

public static void main(String[] args) throws IOException {
System.out.println("Enter the number");
boolean isPalindrome = checkPalindrome(input1);
if (isPalindrome) {
System.out.println("The input is Palindrome");
} else {
boolean isPalindromePossible = checkifPalindromePossible(input1);
if(!isPalindromePossible)
{
System.out.println("Palindrome number not possible");
}
}
}

private static boolean checkifPalindromePossible(int number) {
int digitsCount[] = new int;
int remainder = 0, numberOfDigitsWithOddCount = 0, inputLength = 0,temp=number;
while (number > 0) {
remainder = number % 10;
digitsCount[remainder]++;
number /= 10;
inputLength++;
}
for (int i = 0; i < 10; i++) {
if (digitsCount[i] % 2 == 1) {
numberOfDigitsWithOddCount++;
}
}
if (numberOfDigitsWithOddCount > 1)
return false;
else {
char[] characterArray=new char[inputLength];
int charPlace = 0;
for (int i = 0; i < 10; i++) {
if (digitsCount[i] % 2 == 0 && digitsCount[i] > 0) {
characterArray[charPlace]=  (char) ('0' + i);
characterArray[inputLength - charPlace-1]=(char) ('0' + i);
charPlace++;
} else if (digitsCount[i] % 2 == 1) {
characterArray[(int) Math.ceil(inputLength / 2)]=(char) ('0' + i);
}

}
System.out.println(String.valueOf(characterArray));
return true;
}
}

private static boolean checkPalindrome(int input1) {
int temp = input1, rem = 0, temp2 = 0;
while (temp > 0) {
rem = temp % 10;
temp2 = temp2 * 10 + rem;
temp /= 10;
}
if (input1 == temp2)
return true;
return false;
}

}``````

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

@martin1990: Could you please explain the algorithm of your code. I do not seem to understand "digitsCount[remainder]++;"

Question to interviewer: How are you supposed to make the given number a palindrome? Can we remove digits? or alter their positions to make it a palindrome?

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

@Balaji: digitsCount[remainder]++ stores the number of times the digit between 0-9 repeats in the given number. For making a number palindrome by altering the position( as per the example mentioned) , only one digit can have odd count and should be placed at the mid position. If there are more than one digits whose count is odd, palindrome number can't be formed from the given number.

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

static int changePalindrome(int n){
int t;
int index = 0, div = 1, digitCount = 0;
if (n > 10){
while (n/div > 0) {
div = div * 10;
digitCount ++;
}
int array[] = new int[digitCount];
div = div/10;
for (int i = 1; i <= digitCount; i ++){

array[index++] = n / div;
n = n%div;
div = div/10;
}

for (int j = 0; j < digitCount; j++) {
for (int k = j+1; k < digitCount; k++ ){
if (array[j] == array[k]){
t = array[k];
array[k] = array[digitCount-1-j];
array[digitCount-1-j] = t;
break;
}
}
}
int r =0;
for (int i = digitCount -1; i >= 0; i--){
r += array[i] * Math.pow( 10, digitCount-1 - i);
}

System.out.println ("Result " + r);
return r;
}
else {
return n;
}

}

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.