## Amazon Interview Question for Software Engineer / Developers

• 0

Country: India
Interview Type: In-Person

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

Reach the middle digit of num, say it is mid.
Increment it by 0, 1, 2.... .

If there is a carry over than increment the digit before it.Copy the from start to mid to digits after mid in reverse order.

At any instant the resultant no comes out to be greater than original no, stop the operation.

For eg: 394
mid = 9
9+0 = 9 393 < 394
9+1 = 10 inc 3->4 404 > 394
So 404.

3836
mid = 8
8+0 = 8 3883 > 3836
So 3883

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

1. mid = 9 @ index 1.
2. make mirror on the right side of mid. it gives 999.
3. increment mid by 1. it gives 1009.

as the number of digits have changed, we repeat the algo again? (gives 1001 which is correct!!)

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

sound promising with small change that we need to copy [left->mid] elements to [mid->right] in reverse order.. Here we are starting from mid (not from mid+1 as mentioned in original post) till right..

For 999 case,
middle element is 9,
9+1=10 so increment the next number which is 9
so now the number becomes 1009..
left->mid contents [10]
copy these in reverse order from [mid->right]
so final result is 1001
1001>999 so the next palindrom is 1001...

Hope this helps..

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

A palindrome can be of odd length or even length.

So if the given number is odd:

ex: 98099

1. if the reverse of the first of the palindrome is > the second half then the next palindrome = first half + middle number + reverse(first half) where + means concatenation. Otherwise go to step 2. For 98099, 89 < 99 so move to step 2
2. If the middle number is not 9, then increment the middle by 1 to get the new new middle, and the second half is the reverse(first half). Otherwise go to step 3
For 98099 this becomes 98189 so you're done
3. If the middle number is 9, set the new middle to 0, increment first half by 1, and reverse the new first half by 1 to get the second half. concatenate them all and you're done.

The is for cases like 96997 => 97079

Even case is easily derivable from the odd case. I leave that as an exercise for the reader

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

I meant if the given number is of odd length while describing the above algorithm

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

Hi Augustine,

Your solution is correct. I also worked it out, and it seems like the simplest solution. The solution for the Even # of digits case is even easier as you don't have to find a pivot, you just keep increasing the mirror(firstHalf) number by one until it's >= second half. Then replace the second half with it.

I was initially just increasing the value of the mirror half by 1. It works but it can be faster if you compare each digit in the mirror and second halves from left to right so if you have:

502343, you split the halves and reverse the first one:

205 and 343.

205 < 343, and 2 < 3, so you make 2 into 3

Now you have 305 and 343. 305 < 343, and 0 < 4, so you make that 0 into a 4.

You now have 345 > 343, and then you can replace the second half with 345 to get the next palindrome: 543345

If the # of digits is Odd, it works the same, except you take the pivot out and make it zero.

5027343 would become two halves like above 205 and 343, leaving the pivot out and also making it zero. you end up with 5430345, and then the pivot just increases by 1 in a loop if one wants:

``````for(int i=0; i < 9; i++)
println(firstHalf.toString + (pivot+i) + secondHalf.toString);``````

.

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

The result for 502343 should be 503305 (which is less than 543345)

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

So this solution can be improved by not comparing the entire RHS with the reversed LHS. Because one increment in LHS automatically makes the number way higher than the previous number. So the moment 2 is incremented to 3...we can stop.and copy the LHS.

Or going back to Augustines solution, we can check the middle digits...like 502343 the nearest palindrome is 502205...but since its lesser we increment the middle pair.

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

for 301, next palindrome is 303, not 313.

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

oh sorry right
for 301, next palindrome is 303, not 313.
thanks anon

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

Please correct me if i'm wrong
1. Reach the middle point of number, (if total number of digits are odd, middle number is the pivot, else better to insert a 0 and make the number of digits odd and proceed, and don't forget to remove it while comparing or in final product)

2. Copy the left side of pivot to right side in reverse order

3. If the resultant is greater than the given, then done,
4. If not, then increase both the digits with smallest distance from pivot

5. Continue untill it's greater than given number

6. If 1~(9-digit) failed, then proceed with the next smallest distance digit (yet to find such example)

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

Dude Check out for the case
8999. palindrome should be 9009.. and in this case you have to play with a carry

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

whenenver u move to next smallest distance digit from the pivot and increase it, then you should make all the digits between the pivot and the current digit as 0

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

yaaa, with Algo Visa's change i think that carry problem is not coming.

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

Case of no 32124.

pivot = 1 in the middle.

copying left to right give 32123 < 32124

increasing the digits smallest distance from pivot

32124 -> 33134 (copying left to right gives 33133 which is palindrome but next palindrome should be 32223)

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

public void pali(int num){
int x = num;
while(true){
int rev = 0;
int n = x;
for (int i=0; i<=n; i++){
int r=n%10;
n=n/10;
rev=rev*10+r;
i=0;
}

if(x == rev){
System.out.print("Next palindrome number : " + rev);
break;
}

x++;
}
}

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

Did you test your code ?
Looks like the for() loop will never end .

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

LOL

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

1. For a input, e.g., 301, find its highHalf. In this case, it is 30.
2. Cal lowHalf based on highHalf. Since the len of 301 is odd, the lowHalf is 30 / 10 = 3 in our case. If the len of the input is even, e.g., the lengh of 12 is 2, then the lowHalf is the same as highHalf.
4. Calc highHalf * pow(10, halfLen) = lowHalf
5. repert 4. The first number which is greater or equal to the input is what we want.

The code:

``````unsigned int FindPalindrome(unsigned int input)
{
int temp = input;
int len = 0;
while(temp > 0)
{
temp /= 10;
++len;
}

if(len == 0 || len == 1)
return input;

int halfLen = len / 2;
int highHalf = input;
for(int i = 0; i < halfLen; ++i)
{
highHalf /= 10;
}

while(true)
{
int lowHalf = highHalf;
if(len % 2 == 1)
lowHalf /= 10;

unsigned int ret = highHalf;
for(int i = 0; i < halfLen; ++i)
{
ret *= 10;
}

ret += lowHalf;

if(ret >= input)
return ret;

++highHalf;
}
}``````

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

Calibration. How lowpart is caled should be changed a little bit since it should be a reverse of highHalf

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

If we take note that a palindrome must be mirrored, then we can deduce that the next largest palindrome would be one with its central most digit incremented. This can be derived from the fact that the next largest (not necessarily palindrome) number is one with its LSD (least significant digit) increased by 1, however since we need to retain it as a palindrome it also means the MSD will need to be increased also - which is far from optimal. You can observe from this that the most optimal strategy would be to increase the center digits due to the mirror-like property of palindromes. From the example above, if we incremented the first (and consequently last) digit then we yield 2552, however this isn't the most optimal step because you can modify the central digits to 1661 and retain palindrome status.
So we have a basic strategy but it isn't complete. What happens if the center digits happened to be 9's? You set the currently operating digits to be 0 and increment the next pair of digits as this yields the next smallest number. For example, given 1999 - you first mirror it to 1991, increment the center digits to yield 1001 and then increment the next set of digits to yield 2002 - which is the expected answer. This obviously needs to be looped via iteration or called recursively for multiple 9's.
So are we done yet? Not quite. There is still one minor case we need to cover, it's one that reaches to the MSD but still needs to "carry on" the increments or more simply "all 9's". A basic example would be 9999, if you do the algorithm above then you end up yielding 0000 and still need to increment 1 to the next set of digits (which don't exist as of yet). Covering this case is rather simple, add an extra digit '1' to the beginning of the number (i.e. 0000 -> 10000) and change the LSD to a 1 also (for obvious reasons).

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

Why are you making this complicated?

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

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

haha

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

The first sentence says "...we can deduce that the next largest palindrome would be one with its central most digit incremented". I admit I haven't read the whole paragraph enough times, but I wonder whether that statement is true already given numbers like 23123, where the next palindrome should be 23132, where the middle digit (1) didn't need to be incremented.

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

Here is my logic:
Start from the leftmost and rightmost digit. Consider them as locations as left and right.
Until both left and right either become equal or cross each other, do the following
1. Increment the left until it becomes equal to right
2. Move left to right and right to left.

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

this approach will give a palendrom but not the next palendrom
for Ex 103 when we increment left till it become equal to right. it becomes 303
bot ans should be 111

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

True.
I have changed the approach. I think comparing with its reversal is one of the best.
Here is the code:

``````// Find the next palindrome number which is greater than or equal to a given number
// For example, given number is 1235, then next palindrome number is 1331.
// Approach is if number - reverse of number == 0, then number is palindrom. Hence we will keep increasing the number till it meets the condition.

#include <iostream>
#include <math.h>

using namespace std;

int Reverse(int n)
{
if (n < 0)
{
throw exception();
}

int temp = 0;

// first calculate number of digits
int power = 0;
int num = pow(10, power);

while (n / num != 0)
{
power++;
num = (int)pow(10, power);
}

int rem = 0;
// now use modulo operator to reverse the number
for (int i = 0; i < power; i++)
{
temp += (n % 10) * (int)pow (10, power-i-1);
n = n / 10;
}

return temp;
}

int main()
{
int n = 3221;
while (n - Reverse(n) != 0)
{
cout << "Current number is: " << n << endl;
n++;
}

cout << n << endl;
n = 1235;
while (n - Reverse(n) != 0)
{
cout << "Current number is: " << n << endl;
n++;
}

cout << n << endl;
return 0;
}``````

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

This is same as brute force. If no other solution pops up, then u give this kinda solution in interview. next question will be to improve on it.

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

First compare most significant digit(MSD) and least significant digit(LSD) and recurse through the next set of MSD and LSD

``````compare lsd and msd
Accordingly replace lsd with msd or msd with lsd
recurse through by advancing to next msd and lsd by remembering whether a change was made before``````

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

Pseduo code -

``````Take two pointer A and B .
A points to MSB
B points to LSB

while(A and B are not crossed and are not equal)
{
if(Value(@A)>Value(@B))

replace value @B with value @A;
move B by 1 step towards MSB(towards Right) and move A by 1 step towards LSB(towards Left)
if(B is not pointing to A)
increment value @B by 1, and propagate the carry as normal ,but during propagation any
changes made to values pointing after A(i.e right side), should reflect the same values
pointing after B(i.e left  side)

else

replace value @B with value @A;
move B by 1 step towards MSB(towards Right) and move A by 1 step towards LSB(towards Left)

}

Eg: take 6989
A->6 and B->9
since A < B
replace value @B by a i.e 9 by 6. so now value ll be 6986.
move A and B by 1 step , so A -> 9 and B->8,
increment B by 1 (coz A>B before move was done)
so value ll be 6996.

now A->9 and B-> 9
since A==B,else part ll be executed
so replace Value @B by Value @A , move A and B by 1 step

now A and B are crossed so come out of the loop
so new value ll be the nearest palindrome.``````

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

<pre lang="" line="1" title="CodeMonkey43182" class="run-this">/* The class name doesn't have to be Main, as long as the class is not public. */
class Main
{
public static void main (String[] args) throws java.lang.Exception
{
num++;
while(isPalindrome(num)==false)
{
num++;
}
System.out.println(num);

}
public bool iSPalindrome(int num)
{
int rev=0;
while(num>0){
int cur= num%10;
rev= rev*10+cur;
num= num/10;
}
return num-rev==0;
}
}

</pre><pre title="CodeMonkey43182" input="yes">125</pre>

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

public class stringPalindrome
{
public static void main (String[] args) throws java.lang.Exception
{
int num=999;
num++;
while(isPalindrome(num)==false)
{
num++;
}
System.out.println(num);

}
public static boolean isPalindrome(int num)
{
int rev=0;
int oringalNum=num;
while(num>0){
int cur= num%10;
rev= rev*10+cur;
num= num/10;
}
return oringalNum-rev==0;
}
}

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

if digits odd
{
Place mirror of MSBs in LSB
If number < transformed number return
Increment pivot by 1 and place mirror of MSBs in LSB
}
else
{
Place mirror of MSBs in LSB
if number < transformed number return
Increment the least significant bit of MSBs by 1 and place mirror of MSBs in LSB
}

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

Consider a example:
Case 1: for odd number of digit:

a) 12345
ans a) Find the middle number. Iterate from beginning and put the digits on right

like: 12321
and increase the middle number by 1

so the next palindrome is 12421

Case ii:

Consider example if the number 123456

Leave the middle two numbers such as 3, 4 here
Iterate from beginning and put the number at the end such as:

123421

Now increase the first middle number by 1 and put the same number at the second middle number

so ans is: 124421

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

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

I think you should compare numbers after calculating..
And for 891.see below
891->191 so neglected
891->901 now find for 901 and compare it with 898.
now for 901 next palindrome will be 909 and 898 is smaller than 909 so 898 is the answer.

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

yeah there are basically 4 rules to find the next palindrome.
They can best be described using examples:

num -> next palindrome
35721 -> 35753 (mirror the upper half)
35762 -> 35853 (increment the middle digit if given)
35911 -> 36063 (increment and mirror the upper half)
99965 -> 100001 (special case)

hence, what we need to do is just to check all of them in the order they listed above. The code is as follows:

``````// finds a smallest palyndrome number x2 > x
int next_palyndrome(int x) {
int digits[12], n, x2 = x;
for(n = 0; x2 != 0; n++) {
digits[n] = x2 % 10;
x2 /= 10;
}
int n2 = n / 2, n2p1 = n2 + (n & 1);
// first try replacing the lower digits with rev upper digits
int rev_hi = digits[n2p1], exp = 10;
for(int i = 1; i < n2; i++) {
rev_hi = rev_hi * 10 + digits[n2p1 + i];
exp *= 10;
}
int hi = x / exp, lo = x % exp; // extract lower and upper halves
x2 = hi * exp + rev_hi;
if(x2 > x)     // CHECKING RULE 1
return x2;
hi += 1; // increment 'hi' and construct the number again
if(hi == exp) { // handle a special case when hi = '99...99'
if(n & 1) { // here we return: 100..001
x2 = hi * exp * 10 + 1;
} else {
x2 = hi * exp + 1;
}
return x2; // CHECKING RULE 4
}
int t = (n & 1) ? hi / 10 : hi; // divide out a middle digit if necessary
rev_hi = t % 10;
// calculate the reverse of 'hi' again
for(int i = 1; i < n2; i++) {
t /= 10;
rev_hi = rev_hi * 10 + (t % 10);
}
x2 = hi * exp + rev_hi;
return x2;  // RULE 2 and 3 (together)
}

int main() {
int x = 4992734;
while(1) {
printf("next: %d\n", x);
int x2 = next_palyndrome(x);
if(x2 <= x) {
printf("FATAL: %d %d\n", x2, x);
break;
}
x = x2;
}
return 1;
}``````

sample output:

next: 4992734
next: 4992994
next: 4993994
next: 4994994
next: 4995994
next: 4996994
next: 4997994
next: 4998994
next: 4999994
next: 5000005
next: 5001005
next: 5002005
next: 5003005
next: 5004005
next: 5005005
next: 5006005
next: 5007005
next: 5008005
next: 5009005
next: 5010105
next: 5011105
next: 5012105
next: 5013105
next: 5014105
next: 5015105
next: 5016105
next: 5017105
next: 5018105
next: 5019105
next: 5020205
next: 5021205
next: 5022205
next: 5023205
next: 5024205
next: 5025205

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

num -> next palindrome
35721 -> 35753 (mirror the upper half)
35762 -> 35853 (increment the middle digit if given)
35911 -> 36063 (increment and mirror the upper half) - wrong should be 35953
99965 -> 100001 (special case) - Wrong should 99999

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

you are right, sorry I've just chosen the wrong examples
but the rules are correct. It should be:

35721 -> 35753 (mirror the upper half)
35762 -> 35853 (increment the middle digit if given)
35972 -> 36063 (increment and mirror the upper half)
99999 -> 100001 (special case)

anyway it does not make the algorithm wrong

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

{{codechef.com/problems/PALIN}}
have a look on working codes.

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

``````public int next_Palindrom(int input){
char[] input_int = new Integer(input).toString().toCharArray();
boolean x = next_Pal(input_int,0,input_int.length-1);
if(x){
return new Integer(new String(input_int)).intValue();
}else{
// the case 99...99;
return new Integer(new String(input_int)+2).intValue();
}
}``````

There are two variances to generate next palindrom given input[bgn] and input[end]:
a) if input[bgn] > input[end] do input[end] = input[bgn]. -easy case
b) if input[bgn] <= input[end] (such as '1'22'3' or '1'2'1') we call next_Pal() on bgn+1,end-1. If sub-routine returns true this means that somewhere in the inner string carry the next palindrome (e.g. '1'33'1' or '1'3'1'). All you need now is to equalize left wing and right wing. If it returns false (e.g. '1'9'1' or 1'2'<null>'2'1 then we increments input[bgn] and set input[end] = input[bgn], then zeroOut all input[bgn+1,end-1] (e.g. 202 or 1331). Then return true if the next palindrome is generated within input[bgn,end] and false if otherwise.

``````protected boolean next_Pal(char[] input_str,int bgn,int end)
{
//base case
if(bgn > end)
return false;

//case #1
if(input_str[bgn] > input_str[end]){
input_str[end] = input_str[bgn];
return zeroOut(input_str,bgn+1,end-1);
}else{
//case #2
if(next_Pal(input_str,bgn+1,end-1)){
input_str[end] = input_str[bgn];
return true;
}else if(input_str[bgn] != '9'){
input_str[end] = input_str[bgn] = (char)(input_str[bgn] + 1);
return zeroOut(input_str,bgn+1,end-1);
}else
return false; //the case 99...9
}
}

private boolean zeroOut(char[] input_str, int bgn, int end) {
while(bgn < end){
input_str[bgn++] = input_str[end--] = '0';
}
return true;
}``````

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

Correction: Please change while(bgn < end) to while(bgn <= end) in zeroOut(). Thank you

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

A palindrome can be of odd length or even length.

So if the given number is odd:

ex: 98099

1. if the reverse of the first of the palindrome is > the second half then the next palindrome = first half + middle number + reverse(first half) where + means concatenation. Otherwise go to step 2. For 98099, 89 < 99 so move to step 2
2. If the middle number is not 9, then increment the middle by 1 to get the new new middle, and the second half is the reverse(first half). Otherwise go to step 3
For 98099 this becomes 98189 so you're done
3. If the middle number is 9, set the new middle to 0, increment first half by 1, and reverse the new first half by 1 to get the second half. concatenate them all and you're done.

The is for cases like 96997 => 97079

Even case is easily derivable from the odd case. I leave that as an exercise for the reader

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

I think if the number is first reversed and then thought for some solution,you can come at some better solution. I am currently trying to do so but yet didn't get any generalized result out of this. Guys please try to go this way also.

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

<pre lang="" line="1" title="CodeMonkey48795" class="run-this">/* The class name doesn't have to be Main, as long as the class is not public. */
class Main
{
public static void main (String[] args) throws java.lang.Exception
{
String s;
}
}

</pre><pre title="CodeMonkey48795" input="yes">
</pre>

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

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include "StdAfx.h"
#include<locale.h>
#include <iostream>
using namespace std;
int main()
{
char a[1000002];
int test,i,f,fp,l,mid;
scanf("%d\n",&test);
while(test--)
{
f=1;
gets(a);
l=strlen(a);
fp=0;
for(i=0;i<l;i++)
{
if(a[i]!='9')
{
f=0;
break;
}
}
if(f==1)
{
a[0]='1';
for(i=1;i<l;i++)
a[i]='0';
a[l]='1';
a[l+1]='\0';
fp=1;
}
f=0;
if(fp!=1)
{
for(i=0;i<l/2;i++)
{
if(a[i]<a[l-1-i])
f=-1;
else if(a[i]>a[l-1-i])
f=1;
a[l-1-i]=a[i];
}

if(l%2==0)
mid=l/2-1;
else mid=l/2;

if(f==0||f==-1)
{i=0;
while(a[mid-i]=='9')
{
a[mid-i]='0';
a[l-1-mid+i]='0';
i++;
}
a[mid-i]++;
a[l-1-mid+i]=a[mid-i];
}
}
printf("%s\n",a);
}
return 0;
}

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

How about a brute force method.
pseudo code

``````int RetPalindrome(int n)
{
while(1)
{
++n;
// check if n is a palindrome, if Yes, then return n
if (CheckNumber(n))
break;
}

return n;
}``````

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

the following code (in Java) works

``````public static boolean isPallindrome(int number){
int original = number;
int units=0;
int result=0;
while (number > 0){
units= number%10;
result = result * 10 + units;
number = number / 10;
}
return (original == result)? true : false;
}

public static int findNextPallindrome(int number){
int temp=0;
for(int i=1;i<2000;i++){
temp = number + i;
if(isPallindrome(temp)){
return temp;
}
}
return -1;
}``````

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

This has a time complexity of O(n). That can be done in O(log n) (to the base 10) by using the following logic
1. For even numbers make two halves lefthalf and righthalf
2. reverse left half reverseleft
3. if reverseleft<=righthalf
4. answer is lefthalf+1 +reverse of(left half+1)
5. else if reverseleft>right half answer is lefthalf+reverse of(left half)

for odd the above strategy will hold with only exception that middle digit will be included in both left and right half
And during answer also the middle digit will be merged

See complete java code here

See my below post for code link

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.