## PJ Pvt Ltd Interview Question for Java Developers

Team: 10
Country: India
Interview Type: Written Test

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

Edit: Changed 02/07/2012 as per Hitman's suggestions

The 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.

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

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?

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

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?

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

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

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

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.

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

thanks kill, i think this is correct 100%

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

works for only positive numbers....you need to follow reverse logic for negative numbers..

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

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.

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

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.

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

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

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

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.

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

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.

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

start taking each digit and insert it in a max heap. we can then maek a number by reading those values.

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

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."
"- 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

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

the above algo works

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

import sys
some = []
for line in sys.stdin:
n_line = int(line)
n_line = n_line
while(n_line!=0):
some.append(n_line%10)
n_line = n_line/10
some.sort()
some.reverse()
some = map(str,some)
print "".join(some)

Works for positive ints only

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

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

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

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

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

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

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

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

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

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

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

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
{
}

}
return actualNum;
}

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

Use an array of 10 elements in which u can store the count of each digit of your given number.
Now traverse the array from end and those with (count > 0), pick and make a number out of them.
Eg:
number: 568 araay: 0 0 0 0 0 1 1 0 1 0
start from end and make the number = 8 6 5

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

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.

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

slice the number. then
use next_permutation() function of stl C++.

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

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.

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

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;
}
}
}

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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;
}

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

Fails for 15432. Answer as per algo above 52341. Correct answer 21345.

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.