Amazon Interview Question for Software Engineer / Developers

Country: United States
Interview Type: In-Person

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

let us from an array which consists of digits of the given number as its element
for ex: number = 1234 then our array would be, arr[] = {1, 2, 3, 4}; and N = 4(length of array)

Then we do following steps to get the nextPermutation

1) find the highest index i such that arr[i] < arr[i+1];
2) next we find highest index j > i (found in step 1) , such that arr[j] > arr[i] , such j is sure to exist because we already have it as i+1 , we want the highest index
3)swap arr[i], arr[j].
4)reverse the array arr from index i+1 to N

and we get our next permutation

following code implements , the above algorithm
It takes as input the array arr and its length

bool nextPermutation(int arr[], int N)
     int i, pos, maxPos, t;
     pos = maxPos = -1;
     for (i=0; i < N-1; i++)
         if (arr[i] < arr[i+1])
            pos = i;
    // if there is no such i such that arr[i] < arr[i+1] then the given number has no next  permutatio                                                 if (pos == -1) 
        return false;

     for (i=pos+1; i < N; i++)
         if (arr[pos] < arr[i])
            maxPos = i;
//step3) swap
     t = arr[pos];
     arr[pos] = arr[maxPos];
     arr[maxPos] = t;
     // reverse arr[pos+1..N]
     for (i=pos+1; i < (N+pos+1)/2; i++)
         t = arr[i];
         arr[i] = arr[N-i+pos];
         arr[N-i+pos] = t;

     //for (i=0; i < N; i++)
          //printf("%d ", arr[i]);
     return true;

- Anurag Gupta April 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
of 0 vote

Does the question ask for the least number which is greater than the given number and is also the permutation of it?

I think it requires flipping the first instance of arr[i] < arr[i+1], starting from units position. The idea is to make the least significant two digits more than it's current value. (Comments?)

retNextPermute(char* num) //assuming the num to be string.
int len = strlen(num);
for(; len > 1; len--)
//compare the two digits
int x = num[len-1] - '0';
int y = num[len-2] - '0';
if(x > y)
//flip the digits if condition satisfy and break
char tmp = num[len-1];
num[len-1] = num[len-2];
num[len-2] = tmp;
//print the num

- Anonymous April 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
of 0 vote

Anonymous !
it requires to find the highest index i such that a[i]<a[i+1].
then make it
temp = a[i];
swap shift the elements from a[i+2] to N to left by one position and put a[i+1] at the end .

- newguytoalgos May 04, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
of 0 vote

sorry its following
temp = a[i];
sort the elements a[i+1] to N in ascending order and put the elements in the position a[i+1] to N.

- newguytoalgos May 04, 2012 | Flag Reply

Add a Comment

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.


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


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