PJ Pvt Ltd Interview Question
Java DevelopersTeam: 10
Country: India
Interview Type: Written Test
i think there is something wrong,
for this case: 12342 the above algo will give 21234 but i think the correct answer is 12432
what do u think?
i think there is something wrong,
for this case: 12342 the above algo will give 21234 but i think the correct answer is 12432
what do u think?
Hmmm hitman, you are correct. The algorithm earlier is WRONG, my apologies.
The number(ptr) to be swapped is the number that BREAKS the increasing trend when working from the last digit to the first digit. Let me suggest a change:
"Start from the last digit and work your way backwards keeping a running min of digits encountered.
When you encounter a digit < previous digit, stop and replace with the min digit > ptr. Sort the rest of the digits."
This should work.
Eg 1: 121832
ptr=2;
ptr=3;
ptr=8;
ptr=1 < 8
swap(ptr,min_digit > 1 from (8,3,2)) = swap(ptr,2);
Number = 122831
ptr now points to the third digit where we swapped 1 with 2.
Sort the rest of the number from the swapped ptr to the units place.
Numbers to sort here is 831 => sorted order 138
hence result => 122138
Eg2: 12342
ptr = 2;
ptr = 4;
ptr = 3 < 4;
swap(3, min >3(4,2))
Number = 12432
ptr now points to the third digit where we swapped 3 with 4.
Sort the rest of the number from the swapped ptr to the units place.
Number = 12423
Keep in mind there is no answer for numbers that do not break the increasing trend.
For eg: 6520 => No ans
4321 => No ans
9531 => No ans, etc.
works for only positive numbers....you need to follow reverse logic for negative numbers..
I guess it doesn't work for some numbers that break in increasing order too. Like 3521. It will replace 1 with 3 and give 1235 as result.
I guess it doesn't work for some numbers that break in increasing order too. Like 3521. It will replace 1 with 3 and give 1235 as result.
3521
ptr = 1
ptr = 2
ptr = 5
ptr = 3 < 5
swap(ptr, min_digit > 3 ) = swap (ptr, 5)
Number = 5321
Sort the rest => 5123
5123 is the number
To further optimize it, after swapping with minimum number greater than ptr, to sort just reverse the order of numbers to be sorted as they are already sorted in reverse order.
You dont have to sort it. For sorting part you just reverse it. It will remove the cost of sorting.
kill's option :
3521
ptr = 1
ptr = 2
ptr = 5
ptr = 3 < 5
swap(ptr, min_digit > 3 ) = swap (ptr, 5)
Number = 5321
Sort the rest => 5123
5123 is the number
here you dont need to sort! Just reverse it.
The above algorithm would fail for 15432. Result 52341. Expected 21345.
The following step is invalid in algorithm above.
"- Swap the digit on the left of the 'hotspot' with the last digit of the new number."
Instead use,
"- Swap the digit on the left of the 'hotspot' with the first digit right to itself that is greater than itself"
E.g.,
after sorting the initial number 15432, you would get 12345.
Now replace 1 with first digit right to itself that is larger than itself, i.e. 2.
which gives 21345
I would like to modify the above Algo a little bit :
1. Find the hotspot position (as stated above)
2. Sort all the numbers from the hotspot position to the end
3. Let us say the digit to the left of hotspot position is 'a'. Now swap 'a' with other digit 'b' such that b-a > 0 and minimum. Also this b is to be picked up from the digits starting from the hotspot position to the end of the array.
Eg:
15432
1. hotspot: 5
2. 12345
3.
Case 1: a = 1, b = 5 ... b-a= 4
Case 2: a = 1, b = 4 ... b-a= 3
Case 3: a = 1, b = 3 ... b-a= 2
Case 4: a = 1, b = 2 ... b-a= 1
Case 5: a = 1, b = 1 ... b-a= 0 (Invalid)
So we select b=2 and swap a and b to get 21345
I would like to modify the above Algo a little bit :
1. Find the hotspot position (as stated above)
2. Sort all the numbers from the hotspot position to the end
3. Let us say the digit to the left of hotspot position is 'a'. Now swap 'a' with other digit 'b' such that b-a > 0 and minimum. Also this b is to be picked up from the digits starting from the hotspot position to the end of the array.
Eg:
15432
1. hotspot: 5
2. 12345
3.
Case 1: a = 1, b = 5 ... b-a= 4
Case 2: a = 1, b = 4 ... b-a= 3
Case 3: a = 1, b = 3 ... b-a= 2
Case 4: a = 1, b = 2 ... b-a= 1
Case 5: a = 1, b = 1 ... b-a= 0 (Invalid)
So we select b=2 and swap a and b to get 21345
I would like to modify the above Algo a little bit :
1. Find the hotspot position (as stated above)
2. Sort all the numbers from the hotspot position to the end
3. Let us say the digit to the left of hotspot position is 'a'. Now swap 'a' with other digit 'b' such that b-a > 0 and minimum. Also this b is to be picked up from the digits starting from the hotspot position to the end of the array.
Eg:
15432
1. hotspot: 5
2. 12345
3.
Case 1: a = 1, b = 5 ... b-a= 4
Case 2: a = 1, b = 4 ... b-a= 3
Case 3: a = 1, b = 3 ... b-a= 2
Case 4: a = 1, b = 2 ... b-a= 1
Case 5: a = 1, b = 1 ... b-a= 0 (Invalid)
So we select b=2 and swap a and b to get 21345
I would like to modify the above Algo a little bit :
1. Find the hotspot position (as stated above)
2. Sort all the numbers from the hotspot position to the end
3. Let us say the digit to the left of hotspot position is 'a'. Now swap 'a' with other digit 'b' such that b-a > 0 and minimum. Also this b is to be picked up from the digits starting from the hotspot position to the end of the array.
Eg:
15432
1. hotspot: 5
2. 12345
3.
Case 1: a = 1, b = 5 ... b-a= 4
Case 2: a = 1, b = 4 ... b-a= 3
Case 3: a = 1, b = 3 ... b-a= 2
Case 4: a = 1, b = 2 ... b-a= 1
Case 5: a = 1, b = 1 ... b-a= 0 (Invalid)
So we select b=2 and swap a and b to get 21345
I would like to modify the above Algo a little bit :
1. Find the hotspot position (as stated above)
2. Sort all the numbers from the hotspot position to the end
3. Let us say the digit to the left of hotspot position is 'a'. Now swap 'a' with other digit 'b' such that b-a > 0 and minimum. Also this b is to be picked up from the digits starting from the hotspot position to the end of the array.
Eg:
15432
1. hotspot: 5
2. 12345
3.
Case 1: a = 1, b = 5 ... b-a= 4
Case 2: a = 1, b = 4 ... b-a= 3
Case 3: a = 1, b = 3 ... b-a= 2
Case 4: a = 1, b = 2 ... b-a= 1
Case 5: a = 1, b = 1 ... b-a= 0 (Invalid)
So we select b=2 and swap a and b to get 21345
Hi friends,
I have implemented the above in different logic using java
Let us take the number 15432 for which expected output is 21345
so, here the logic is first we need to identify the smaller number comparing with the prev number beginning from the end
for number 15432
1st comp: currNum=2 prevNum=-1(at the beginnin) cond= is curNum<prevNum
if cond failed then store the currNum to Array: 2
2nd comp: currNum=3 preNum=2, here also cond fails and stores the value to array: 2,3
Note: array here will be by default in sort order
.
.
5th comp: curNum=1 preNum=5, here cond satisfies and our logic will start,
now we found the number or hotspot, now start comparing the values in array with the hotspot number
is 1 < firstElment in Array (1<2) if yes replace the number 1 with 2 and 2 to 1 in array
and start adding all the array values to one's position of obtained digit one by one
After Swap num: 2 and in Array 1,3,4,5
After adding values of array: 21345
Output : 21345 is achieved :)
code:
******************
public int findNumber(int num)
{
int currentNum=-1;
int prevNum;
ArrayList numbers=new ArrayList();
int actualNum=num;
while(num>0)
{
prevNum=currentNum;
currentNum=num%10;
num=num/10;
if(currentNum<prevNum)
{
for(int i=0;i<numbers.size();i++)
{
int tempNum=(Integer) numbers.get(i);
if(currentNum<tempNum)
{
num=(num*10)+tempNum;
numbers.set(i, currentNum);
for(int j=0;j<numbers.size();j++)
{
int tempNum2=(Integer)numbers.get(j);
num=(num*10)+tempNum2;
}
return num;
}
}
}
else
{
numbers.add(currentNum);
}
}
return actualNum;
}
Simple Algo (not optimized) would be
1. Break the number into digits.
2. Find all possible combinations of these digits.
3. Sort these combinations.
4. Find number next to the original number in sorted array.
Now optimize Step 2, while forming numbers from digits, discard all number who are less than original number.
1.Continue until we have the right to left increasing sequence going, starting from right end that is.
2.Let's call the point here the sequence breaks, the pivot point.
3.Swap the digit at the pivot point with a number to its right which is greater than itself by a minimum amount .
4.Sort the digits after the pivot point in ascending order.
Here is the code i came up with
static void findNextBiggerNumber(int num) {
int a[] = getAsArray(num);
int length = a.length - 1;
// use sentinel if your number contains 0
int temp[] = new int[length + 1];
int counter = 0;
for (int index = length; index >= 0; index--) {
if (index - 1 >= 0 && a[index - 1] > a[index]) {
temp[counter++] = a[index];
} else {
if (index > 0) {
temp[counter++] = a[index];
BubbleSort.sort(temp);
swapDigit(a, temp, index);
// put the numbers back into original array
for (int j : temp) {
// Need to check, coz int values are 0 by default
// insert sentinel if you want to have 0 in your number
if (j > 0) {
a[index++] = j;
}
}
}
break;
}
}
print(a);
}
private static void swapDigit(int[] a, int[] temp, int i) {
int digitToBeSwapped = a[i - 1];
for (int smallest = 0; smallest < temp.length; smallest++) {
if (temp[smallest] > digitToBeSwapped) {
a[i - 1] = temp[smallest];
temp[smallest] = digitToBeSwapped;
break;
}
}
}
Algorithm:
- Move from right -> left and stop when the current digit is greater than the next one, let's call this point, 'hotspot'.
- Sort all the digits from hotspot till the end of the number in increasing order.
- Swap the digit on the left of the 'hotspot' with the last digit of the new number.
e.g.
5784321
hotspot: 8
after sorting: 5712348
after swapping: 5812347
Here is the code,
void nextLarge(char* num)
{
int len = strlen(num);
int i;
//decrement i till digits are increasing from right to left
for(i=len-1; num[i] < num[i-1]; i--)
{
//return if the digits are sorted in decreasing
//order, number is already the largest.
if(i == 1)
return;
}
//sort everything from hotspot till the end
sort(num, i, len-1);
//swap digit before hotspot with the last one
swap(&(num[i-1]), &(num[len-1]));
}
int main()
{
char num[20] = {0, };
sprintf(num, "%s", "5417962");
nextLarge(num);
printf("%s\n", num);
return 0;
}
Edit: Changed 02/07/2012 as per Hitman's suggestions
- kill February 07, 2012The number(ptr) to be swapped is the number that BREAKS the increasing trend when working from the last digit to the first digit.
"Start from the last digit and work your way backwards.
When you encounter a digit < previous digit, stop and replace with the min digit > ptr. Sort the rest of the digits."
This should work.
Eg 1: 121832
ptr=2;
ptr=3;
ptr=8;
ptr=1 < 8
swap(ptr,min_digit > 1 from (8,3,2)) = swap(ptr,2);
Number = 122831
ptr now points to the third digit where we swapped 1 with 2.
Sort the rest of the number from the swapped ptr to the units place.
Numbers to sort here is 831 => sorted order 138
hence result => 122138
Eg2: 12342
ptr = 2;
ptr = 4;
ptr = 3 < 4;
swap(3, min >3(4,2))
Number = 12432
ptr now points to the third digit where we swapped 3 with 4.
Sort the rest of the number from the swapped ptr to the units place.
Number = 12423
Keep in mind there is no answer for numbers that do not break the increasing trend.
For eg: 6520 => No ans
4321 => No ans
9531 => No ans, etc.