Amazon Interview Question for Software Engineer / Developers


Country: India
Interview Type: In-Person




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

Here:
Careercup question?id=11543949

- Varun February 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

this is about generating permutations in lexicographical order:

use std::next_permutation() for that ))

- Anonymous October 20, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I solved it in a different way. If I remember correctly the space complexity blows up if we try to compute the permutations.

* The number is actually provided as an array of chars.
* Take an array of length 10. to hash the rightmost occurance of each digit (0-9).
* Process the array from right to left.
* If you encounter a digit for which there is a higher digit to its right, Find the rightmost occurance of it (from the hash table) and swap the elements.
* Sort the numbers to the right of the element you just swapped.

- msramachandran October 20, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I guess you can save some time by avoiding sorting and rather reversing the list to the right of swap. The only element that could be out of place after reversing is the first element which you can move to its rightful place.

- KM October 22, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int getNextNumberWithSameDigits(int n){
		
		char[] digits = Integer.toString(n).toCharArray();
		
		for (int i = digits.length-1; i>0; i--){
			
			for(int j = i-1; j>=0; j--){
				if (digits[i] < digits[j]){
					// swap and return
					
					char tmp = digits[i];
					digits[i] = digits[j];
					digits[j] = tmp;
					return Integer.parseInt(new String(digits));
					
				}
			}
			
			
		}
		
		return -1;
	}

- Xiaochao October 20, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This doesn't work in all cases, take for example 2531. With your code it would return 3521, where correct would be 3125. The correct solution would rotate subarray [i..j] left until a[i] moved to a[j] position:

for (int i = digits.length-1; i>0; --i) {
	for (int j = i-1; j>=0; --j) {
		if (digits[i] > digits[j]) {
			// rotate subarray [j..digits.length-1] right					
			// digits.length - i times
			for (int k = 0; k < digits.length - i; ++k) {
				char t = digits[digits.length-1];
				for (int l = digits.length-1; l > j; --l) {
					digits[l] = digits[l-1];
				}
				digits[j] = t;
			}
			return Integer.parseInt(new String(digits));
		}
	}			
}

- A October 21, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Some diff idea,
Firstly, we need use Xiaochao's way to swap the data.
then, I think we need to sort the digits behind swap index.
e.g. original digital is 34951,
1. from right to left, scan the digital,
a. 1 is less all digits
b. 5 is less 9, but greater than 4, so current the i is 3, and j is 1
c. swap digits[i] and digits[j], not the digits is 35941,
2. sort from the digits[i+1] to digits[length - 1], here it is 941
So, the answer is 35149

- Yaya October 21, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@yaya your idea is correct: this algorithm just generates the permutations in lexicographical order. But we also have to take care of duplicate digits. The code is below:

// lexicographically permutes an array of n elements
bool next(int *x, int n) {
    // find the rightmost x[i] which is smaller then x[i+1]
    int i = n - 1;
    do { i--; } while(x[i] >= x[i+1]);
    if(i < 0)
        return false; // all permutations enumerated
    // now we have:
    // x[i] < x[i+1] > x[i+2] > ... > x[n-2] > x[n-1]
    // find rightmost j such that x[i] < x[j]
    int j = n - 1;
    while(x[i] >= x[j]) j--;
    // we have: x[i] < x[j] where j = i+1 .. n-1
    swap(x[i], x[j]);
    // now elements x[i+1].. x[n-1] form a falling sequence => reverse it
    int r = n - 1, s = i + 1;
    while(s < r) {
        swap(x[s], x[r]);
        s++, r--;
    }
    return true;
}

// computes the next number after 'N' formed from the same digits
int next_number(int N, int *x, int n_digits) {
    int i;
    for(i = n_digits - 1; N != 0; i--) {
        x[i] = N % 10, N /= 10; // convert the number to an array of digits
    }
    if(!next(x, n_digits)) // compute the next permutation
        return 0; // all numbers enumerated
    for(i = 0, N = 0; i < n_digits; i++) { // convert back to a number
        N = N*10 + x[i];
    }
    return N;
}

int main() {
    int n = 10; // max no of digits
    int *x = new int[n+1], *y = x + 1;
    x[0] = n+1; // sentinel
    int N = 11553, n_digits = 5;
    while(1) {
        printf("next: %d\n", N);
        N = next_number(N, x, n_digits);
        if(N == 0) break;
    }
    delete []x;
    return 1;
}

output:
next: 11553
next: 13155
next: 13515
next: 13551
next: 15135
next: 15153
next: 15315
next: 15351
next: 15513
next: 15531
next: 31155
next: 31515
next: 31551
next: 35115
next: 35151
next: 35511
next: 51135
next: 51153
next: 51315
next: 51351
next: 51513
next: 51531
next: 53115
next: 53151
next: 53511
next: 55113
next: 55131
next: 55311

- Anonymous October 21, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Start moving pointer from right to left until the sequence traversal is decreasing.
Eg. N=142521, pointer stops at '2'521.
2. Swap the digit so found with LUB-digit(least upper bound digit) among right digits.
Eg. SWAP '2'521-->'5'221
3. Sort the digits which are to pointer's right
Eg. '5'221-->'5'122

- novice October 21, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Store the digits in the given number in an array. unit's place digit goes to 
   arr[0], ten's place digit goes to arr[1] so on... set a flag bool possible =0.

2. Scan the array from arr[0] till end
   a. if (arr[i]>arr[i+1]) swap arr[i] and arr[i+1]; possible =1; break the loop

3. if (possible == 0) print ("Given number is the maximum number") 
   return (same number)
   else
   {
     sort the array in descending order from arr[0] to arr[i];
     reconstruct the number from the modified array like 1*arr[0]+10*arr[1]+..so on;
     return (new number);
   }

- Tiscaao! October 21, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I read through all these steps . its interesting. Any idea on the below method ?

1)Convert the number to character array

2) Increment the given number by 1

3) Convert the incremented number to character array and compare each and every character with the given number which is in character array. If all the numbers are present . return that number .

I may be wrong, just a thought. suggestions are most welcome

- Somu October 27, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In the above step we can check if the size of the int is same after incrementing . If not we can print the same number saying its the maximum

- smuthaiah@buzzient.com October 27, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Find the permutation of all the digits given and then sort you can find next greatest number.

- Beginner December 20, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Step 1:- store the first digit in variable
Step 2:- sort the character of array
Step 3:- compare with variable from array and find first Greater-then then remove and store
Step 4:- simple append all the remaining characters

- Anonymous February 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Find the first digit towards the left (say at position i) that is greater than the digit in the units place. Swap these two. Now sort all digits towards the right of position i.

- Anonymous February 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

for each digit from right to left of the number
	find the first digit towards left smaller than the current digit
        if not found
                continue
        if found
                 swap it with current digit
                 sort the digits towards right of the smaller digit found above
                 break
end

- Anonymous February 14, 2013 | 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