Amazon Interview Question Software Engineer / Developers
That I don't think works.
What needs to happen is that iterate from the right to find the first two pairs of digits that are in descending order. Swap the two digits and starting from the number after the swapped higher number's current position, sort the rest of te numbers to the right in ascending order.
So 1743 would first be changed to 3741. Then starting from the digit after 3(the higher of the two swapped digits), the numbers are sorted in ascending order and the resulting number would be 3147.
The complexity is nlogn.
void nextHigherPermOp(int a[], int n)
{
int maxd = a[n - 1];
int i = n - 2;
while (a[i] >= maxd)
maxd = a[i--];
int piv = i;
while (a[++i] > a[piv]);
int tmp = a[piv];
a[piv] = a[--i];
a[i] = tmp;
i = piv+1;
while (i < (n - i)/2+i)
{
tmp = a[i];
a[i] = a[n-i+piv];
a[n-i+piv] = tmp;
i++;
}
}
O(n) time O(1) space
start reading digits from right(lsb) to left(msb)...until u find a smaller digit than the current one..for ex consider i/p = 17365432...start reading from 2->3->4->5->6->3...this is a dip..that we are looking for.
- Anonymous June 29, 2010now among the entries seen so far, select those that are greater than current val(3 in example)...so we have 4,5,6...and select the smallest one i.e. 4 in example...'4' takes place of '3' and then rest are just written out in ascending order...
so o/p is 17423356