## Amazon Interview Question for Software Engineer / Developers

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
2
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;

//step1)
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;

//step2)
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;

//step4)
// 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;
}``````

Comment hidden because of low score. Click to expand.
0
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;
break;
}
}
//print the num
}

Comment hidden because of low score. Click to expand.
0
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];
a[i]=a[i+1];
swap shift the elements from a[i+2] to N to left by one position and put a[i+1] at the end .

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

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

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.