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.

- kill February 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- Hitman February 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- Hitman February 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- kill February 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- kill February 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

thanks kill, i think this is correct 100%

- hitman February 07, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous February 11, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- sg March 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- sg March 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- kill March 06, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Mad Coder June 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Psycho September 04, 2012 | Flag
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.

- King@Work February 06, 2012 | Flag Reply
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."
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

- sobu86 February 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

the above algo works

- Anony February 07, 2012 | Flag
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

- kri February 06, 2012 | Flag Reply
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

- Madey February 06, 2012 | Flag Reply
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

- Madey February 06, 2012 | Flag Reply
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

- Mandar February 06, 2012 | Flag Reply
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

- Mandar February 06, 2012 | Flag Reply
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

- Mandar February 06, 2012 | Flag Reply
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
{
numbers.add(currentNum);
}

}
return actualNum;
}

- TechTycoon February 12, 2012 | Flag Reply
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

- Anonymous May 03, 2012 | Flag Reply
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.

- SKM June 12, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- joker June 19, 2012 | Flag Reply
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.

- Anonymous July 15, 2012 | Flag Reply
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;
			}
		}
	}

- Fresh_man December 20, 2012 | Flag Reply
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;
}

- Anonymous February 06, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- sobu86 February 06, 2012 | Flag


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More