Amazon Interview Question for Quality Assurance Engineers


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

- kr.neerav February 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Killedsteel February 13, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

#!/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[1], 0, str("not set"))
        if token[0] == 1:
                if token[2] == str("None"):
                        print "palindrome"
                else:
                        print "palindrome"
                        get_dup = set(token[1])
                        unique = token[2]
                        l = ('').join(get_dup)
                        if unique != 0:
                                print l + str(token[2]) + l[::-1]
                        else:
                                print l + l[::-1]

- aka February 14, 2014 | Flag
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());
    }

- Johnb February 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Johnb February 13, 2014 | Flag
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;
        }

- Mak February 12, 2014 | Flag Reply
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.

- Anonymous February 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- kr.neerav February 13, 2014 | Flag
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;
        }

- korser February 13, 2014 | Flag Reply
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)

- vinwebin February 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class CheckPalindrome {

	public static void main(String[] args) throws IOException {
		BufferedReader obj = new BufferedReader(new InputStreamReader(System.in));
		System.out.println("Enter the number");
		int input1 = Integer.parseInt(obj.readLine());
		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[10];
		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;
	}

}

- martin1990 February 13, 2014 | Flag Reply
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?

- Balaji Ramamurthy March 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- martin1990 March 15, 2014 | Flag
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;
}

}

- Sivambigai July 31, 2014 | 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