Amazon Interview Question
Software Engineer / DevelopersExample - For 1243
You should 2 and 3. You get 1342.
Now sort the portion after where the swap happened. So sor the portion "43". You get 34. So finally you get 1324.
My algorithm works for all the above mentioned cases.
Store the number in a character array (num) and traverse back from the last. As soon as it is found that the digit at the current index (i) is less compared to the element to its right,we have to find the smallest number in the right part starting from i+1 which just exceeds num[i]. Swap that number with num[i] and sort the right array in ascending order.
e.g. For 1342
i = 1 since it is less than its next element to the right (which is 4)
We find the nearest digit in the right array starting from index 2
and in this case the number is 4.
Swap them
So now the number is 1432
Then we sort the right part to get
1423
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
using namespace std;
int searchJustBig(const char* num, char c, int lpos, int rpos);
int comp(const void* a, const void* b)
{
char p = *(char*)a;
char q = *(char*)b;
if(p<q)
return -1;
else if(p>q)
return 1;
else
return 0;
}
int main()
{
cout<<"Enter the number ";
char num[1024];
scanf("%s", num);
unsigned len = strlen(num);
int i = len-2;
char tmp = num[len-1];
for(; i>=0; i--)
{
if(num[i] < tmp)
{
int val = searchJustBig(num, num[i], i+1, strlen(num)-1);
swap(num[val], num[i]);
qsort(num+i+1, strlen(num)-i-1, sizeof(char), comp);
break;
}
else
{
tmp = num[i];
}
}
if(i == -1)
printf("NONE\n");
else
printf("%s\n", num);
}
int searchJustBig(const char* num, char c, int lpos, int rpos)
{
if(lpos<rpos)
{
int mid = (lpos + rpos)/2;
if(num[mid] <= c)
return searchJustBig(num, c, lpos, mid);
else
return searchJustBig(num, c, mid+1, rpos);
}
else
{
if(num[lpos] > c)
return lpos;
return lpos-1;
}
}
you don't need to sort the the right array in ascending order. Since you have traversed from the back, and found the "JustBig" number, the right array must be in desecending order, so you just need to reverse the right array.
if i am wrong, please correct me.
Hi Saumya, I don't think you understood kishore's solution. His algorithm will yield correct answer as 1324.
Note that he is not swapping digits[i] with digits[i+1], he's swapping digits[i] with the smallest digit after i that is greater than digits[i].
Assume an array a[1,…,n].
1) Start from back, try to find an element a[k], where there is at least one element among a[k+1,…n] is larger than a[k].
2) Find the element a[h] among a[k+1,…n], which is the smallest element larger than a[k], then swap a[k] and a[h].
3) sort the new sub array a[k+1,…,n] in ascending order.
int nextNumberWithSameDigits(int aNum)
{
if(aNum < 0)
throw new exception("Negative not implemented.");
if(aNum < 9)
return aNum;
CQueue<int> _q;
CStack<int> _s;
int aMod = 0;
int aTemp = aNum;
while(aTemp > 0)
{
aMod = aTemp % 10;
aTemp = aTemp / 10;
if(_q.empty() || aMod > _q.front())
{
_q.push(aMod);
}
else
{
_s.push(aMod);
break;
}
}
if(_s.empty())
return aNum;
while(!_q.empty())
{
if(_q.back() < aMod)
_s.push(_q.pop());
else
break;
}
aTemp = (aTemp * 10) + _q.pop();
while(!_q.empty() || !_s.empty())
{
int a;
if(!_q.empty() && !_s.empty())
a = _q.front() < _s.top()?_q.pop():_s.pop();
else if (_q.empty())
a = _s.pop();
else if(_s.empty())
a = _q.pop();
aTemp = (aTemp * 10) + a;
}
return aTemp;
}
Working Python solution
def nextFromDigits(X):
L = list(str(X))
prev = '0'
for i in reversed(range(len(L))):
if L[i] < prev:
G = (j for j in xrange(i+1,len(L)) if L[j]>L[i]) # generator with suffix indices to elements larger than L[i]
k = min(G, key = L.__getitem__ )
L[i], L[k] = L[k], L[i] #swap
L[i+1:] = sorted(L[i+1:])
return int(''.join(L))
prev = L[i]
return -1 #does not exist
print nextFromDigits(1234)
print nextFromDigits(1243)
print nextFromDigits(4321)
Check also at: ideone.com/un873
Algo
Start from last element and keep a track of big element
If a small element is found update big and small and sort rest
else if big is found update big and continue search
char[] str1=str.toCharArray();
char temp=str1[l-1];
boolean dobreak=true;
System.out.println(temp);
int i=l-1;
for(int j=l-2;j>=0&& dobreak==true;j--)
{
if(temp<str1[j]){
temp=str1[j];
}
if(str1[j]<temp)
{
char temp2=str1[j];
str1[j]=str1[i];
str1[i]=temp2;
dobreak=false;
for(int x=j+1;x<=l-2;x++)
{
for(int y=x+1;y<=l-1;y++)
{
if(str1[x]>str1[y])
{
char temp3=str1[x];
str1[x]=str1[y];
str1[y]=temp3;
}
}
}
}
}
System.out.println(str1);
Correct me if I am mistaken here:
- Vinod July 20, 2011Take the last digit - keep comparing this with digits from the back (one by one) till you reach a digit that is lesser than the last digit. Now swap these two.
Now just sort the numbers in the portion that was compared (after the digit where the swap compared).
You have the next biggest number. This is O(N)+)(NLogN) = O(NLogN).