Amazon Interview Question for Software Engineer / Developers


Country: India




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

We can write a simple program for the following 4 cases, which will be answer for this question.

There are two main cases. 1. Number of digits is odd. 2. Number of digits is even.
In odd case, it has to be separated into three groups. 1. First half 2. Middle digit 3. Second half.
In even case, it has to be separated into two groups. 1. First half 2. Second half.
Now consider following different cases.
1. Case 1: Even number of digits and first half is less than second half.
123 456 124 421
Add 1 to first half, reverse first half and paste it at right side.

2. Case 2: Even number of digits and first half is greater than second half.
456 123  456 654
Just reverse it and paste it at right side.

3. Case 3: If odd number of digits and first half is less than second half.
123 1 234  123 2 321
Add 1 to combined first half and middle one (here 1231+1). Then separate middle one and reverse first half and paste it on right side
Another example: 123 9 234  124 0 421 (here 1239 +1= 1240).

4. Case 4: If odd number of digits and second half is less than second half.
445 9 123  445 9 544
Reverse first half and paste it on right side

- BVarghese January 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Superb explanation. I was actually stumped on this problem for sometime

- Anonymous January 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice explanation ..thanx

- Atul Bajpai January 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Good explanation.

- Murali January 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

your solution is wrong...
check for this one
126 1 521
3 0 1.....etc ...ur solution will always give the wrong answer..try to think lil bit more..if u wont get correct solution then i'll tell you.. :)

- shishirvicto January 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thanks @Shishivicto! I forget to add the following line. Thanks for pointing it.

For case 1 and 3( if first half is less than second half) reverse first half number and convert to a number, and then check whether it is bigger than second half. If bigger, then just reverse and paste it at right side and we don't need of adding 1 with it. Otherwise, for both cases add one and do as wrote above.
eg:
126 521==> we can just reverse first half and paste it at right side
126 1 521 ==> we can just reverse first half and paste at right side

- BVarghese January 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Another case needs to be addressed where first hal and second half are equal, like 747.

- Anon January 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Also
for 123 301 it gives 124 421 whereas expected is 123 321
for 856 714 it gives 856 658 whereas expected is 857 758
for 123 1 301 it gives 123 2 321 whereas expected is 123 1 321
for 856 1 714 it gives 856 1 658 whereas expected is 856 2 658


Crux is that you should compare the reverse of first half with secod half rather than comparing first half with second half..

- AmazingCode January 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Also put a precheck for
-all 9s if it's so just add 2 to number
-single digit : just add 1 to number

- AmazingCode January 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yea, we all realize that there are some mistakes in BVarghese's solution, but he is basically on the right track. Cut him slack and figure out the edge cases yourself.

- Anonymous January 10, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

one more conditions.

if all nines, just add 2 to it,
9999 --> 10001

- mrb January 12, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I feel BVargese need to correct just a bit. instead of comparing first half with second, we need to compare reverse of first half with second. If the reverse of first half is greater, we just have to paste it as such. Otherwise, if the reverse of first half is smaller, add one to the original, reverse and then paste.
eg:
4135: reverse(41) = 14 < 35. So, 41+1=42, reverse(42) = 24. So, 4224 is the answer.
41935: 419+1=420. So, 42024 is an answer.
I feel all cases are included now.

- cooldaa January 16, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

wrong solution..it will fail if number is 1234..according to you first half is less thn second now12 < 34 ..thn according to u add 1 it become 13 reverse make it 31 copy at right make number 1231..wrong

- Anonymous March 27, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

You have an array a and its length is b. (0,1,2,3,...b-1 ; b is even)

int k=b/2;
while((--k>=0)&&(a[k]==9));
if(k>=0){
a[k]++;
a[b-k-1]++;
}
else{
std::cout<<"1";
for(int i=0;i<b;i++)cout<<"0";
cout<<"1";
}

- AncientHero January 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void FindTheNextPalindrom(int n){
             while(true){
			n++;
			if(n>Integer.MAX_VALUE){
				System.out.println("the number is too large");
                                break;
			}
			if(isPalindrom(n)){
				System.out.println(n);
				break;
			}
		}
	}
	
	public static boolean isPalindrom(int n){
		ArrayList<Integer> digits=new ArrayList<Integer>();
		while(n!=0){
			digits.add(n%10);
			n=n/10;
		}
		for(int i=0;i<digits.size()/2;i++){
			if(digits.get(i)!=digits.get(digits.size()-1-i)){
				return false;
			}
		}
		return true;
	}

- zhouzhou January 09, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// I tested all examples above. worked for all XD

int main(void)
{
int n;
int count = 0;
int div;

int *str = new int[256];
int pad = 0;
cin >> n;
div = n;
while ( div > 0)
{
str[count++] = div%10;
div /= 10;
}

count --;
for (int i = 0; i < (count+1)/2; i++){
if ( (str[i] + pad) <= str[count - i]){
pad = 0;
}
else{
pad = 1;
}
str[i] = str[count-i];
}

if (count%2 == 0 && pad ==1){
if (str[count/2] < 9)
str[count/2] ++;
else{
str[count/2] = 0;
str[count/2+1] ++;
str[count/2-1] = str[count/2+1];
}
}
if (count%2 == 1 && pad == 1)
{
str[int(count/2) +1] ++;
str[int(count/2) ] = str[int(count/2) +1 ];
}

for (int j = 0; j <= count; j++)
cout << str[j];

cout << endl;
return 0;
}

- yvette January 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Could you please eloborate the logic of this

- Srishti January 16, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

www - ardendertat - com/2011/12/01/programming-interview-questions-19-find-next-palindrome-number/

- hello world January 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Code in JAVA

public int nextLargestPalindrome(int number)
	{
		int length = String.valueOf(number).length();
		boolean oddDigits = (length % 2) != 0;
		String leftHalf = getLeftHalf(number);
		String middle = getMiddle(number);
		int increment;
		int newNum;
		if(oddDigits)
		{
			increment = (int)Math.pow(10, length/2);
			newNum = Integer.parseInt(leftHalf + middle + reverseIt(leftHalf));
		}
		else
		{
			increment=(int)(1.1*Math.pow(10, length/2));
			newNum = Integer.parseInt(leftHalf + reverseIt(leftHalf));
		}
		if(newNum > number)
			return newNum;
		if(!middle.equals("9"))
		{
			return newNum + increment; 
		}
		else
		{
			return nextLargestPalindrome(roundUp(number));
		}
	}

	private int roundUp(int number) 
	{
		int length = String.valueOf(number).length();
		int increment = (int)Math.pow(10, length/2 + 1);
		return ((number/increment) + 1) * increment; 
	}

	private String getMiddle(int number) 
	{
		String str = String.valueOf(number);
		return Character.toString(str.charAt(str.length() / 2));
	}

	private String getLeftHalf(int number) 
	{
		String str = String.valueOf(number);
		return str.substring(0, str.length() / 2);
	}
	public static String reverseIt(String a) {
		 
		int length = a.length();
		StringBuilder reverse = new StringBuilder();
		for(int i = length; i > 0; --i) {
			char result = a.charAt(i-1);
			reverse.append(result);
		}
		return reverse.toString();
	}

- hello world January 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Update for getMiddle() method :

private String getMiddle(int number) 
	{
		String str = String.valueOf(number);
		if(str.length() % 2 != 0)
			return Character.toString(str.charAt(str.length() / 2));
		else
			return Character.toString(str.charAt((str.length() / 2) - 1));
	}

- hello world January 23, 2012 | Flag


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