Amazon Interview Question
Quality Assurance EngineersCountry: India
Interview Type: In-Person
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
#!/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]
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());
}
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;
}
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.
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;
}
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: 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: 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.
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;
}
}
The logic to check a palindrome is easy and not included here.
- kr.neerav February 13, 2014Case 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