Amazon Interview Question for Software Engineer / Developers


Country: India




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

The question need to be more specific. Does the interviewer wants the immediate greater number that can be formed or any greater number? for example if given 1234 then answer xan be 1243, 1324,1342 etc. the best way is to start with the right most digit and see if a digit on the left side is smaller than it and then switch their position.

- Algo Visa September 19, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Question mention that immediate bigger number ..

- Nitin September 19, 2011 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

can be done in o(num_of_digit) time.@Anonymous :no need to sort the number to get the answer.

- ari September 27, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

actually you have to sort the number and the it's the perfect example for counting sort

- Anonymous September 27, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

How would you avoid sorting the number?

- eugene.yarovoi October 02, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Resolve Ambiguity: Should each digit be used as many times as it appears in the number? Ex: In 7111, should 7 be used only once and 1, only thrice? If yes, there's no bigger number for this scenario of 'XYYY' where X > Y. Can be handled as a special case.

Sounds like BIT Shifting problem. However, here's one solution runs in constant O(no.of.digits forming the number) == O(c) time:
a) Divide no. by 10 and store each digit in array
eg: 7585 ->
- use a counter to count no of digits as you divide by 10, here 4
- again, store in array each digit with [index 0 == digit at unit place, index 1 == digit at 10th place etc] -> int[] digits = {5, 8, 5, 7}
b) Find digits forming bigger no.
//code:

boolean foundBigger = false;
  int length = digits.length;
  int j = length - 1, i = length - 2;
  while(!foundBigger){
        if(i == -1){
         //exception case of 7111. No bigger no. possible here. 
         break;
        }
       if((a[j] > a[i]) || (a[j] == a[i])){
         j--;
         i--
       } else if(a[j] < a[i]){
         //swap and found bigger no here
         temp = a[j];
         a[j] = a[i];
         a[i] = temp;
         foundBigger = true;
       } 
    }

c) From new array( Eg: [5, 5, 8, 7] ), since we know the digit value: multiple accordingly:

int sum = 0, j = 1;
   for (int i = 0; i<digits.length; i++){
      sum = sum + a[i] * j;
      j  = j * 10;
   }

- taojfew September 19, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Sorry .. Interviewer told me to use same digits with same number of time, coming in positive integer and if a small number is not possible then we have to return -1

- Nitin September 19, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Check your solution for 7856... I guess your code will return 8756 whereas the answer should be 7865

- SecretAgent September 20, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

how about

1. start from the right most digit ( ones position)
2. check if it is bigger than the immediate left..(tens position)
if yes then
swap them you got the answer
else
check the next left ( hundered postion)
if 10s is bigger than the 100s swap then you got the answer

This might give the right answer because if 1s position is bigger than the 10s then swaping them would give the immediate next bigger number and if it is not then this method will make sure it is smaller than all the subsequent digits traversing from left to right.

eg. 79 ( swap 1s position and 10s)
ans 97

eg 7585
1s(5) < 10s(8) hence do not swap
10s(8)> 100s(5) hence swap
ans 7855

eg. 7439
swap (9,3) ans 7493 ( next bigger no)

Please tell me any counter example in which case it will not work .

- cinderella September 19, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Cinderella ,
Take a example of 7684 ..!!
According to you it should be 7864 but the answer is 7846 !! :)
You are very close to the solution !!

- Nitin September 19, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

May be reverse the string from the position of swap till the last and concatenate with the rest of the number.

7864(reverse 64 => 46) so 7846

76843
78643(reverse 643 => 346)

78346

7558

7855 ( reverse 55 => 55)

796851

798651( reverse 651 => 156)

798156


this reverse might work because while traversing from right to left we have made sure that it is sorted.

Is there a better way ?

- cinderella September 19, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@cindrella:
your solution is almost complete..
but it fails for 24965..
as per your logic answer is 29564..
but the answer is 29456...

you should also find correct location for swapped num before sorting...

- Anonymous September 19, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

You meant : 25469 is the answer - right?

- Anshu September 20, 2011 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

I think the right solution would be like
1. start from right most digit as @cindrella said and find the digit bigger than immediate left
2. then swap both the digits and sort all the digits to the immediate right of the swapped digit in ascending order
3. in case of 7684, 8 is the swapped number and this will sort 64 to 46 which gives 7846
@nithin tell me if iam wrong

- SecretAgent September 20, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

7264 -> ur algo will give 7624 but 7426 is also there.. u are only comparing the immediate ones.. but ones and hundreds can also be compared..

- Anonymous September 19, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{{public static void main(String[] args) {

String str1 = "12342342355555575753453453421";

assert (str1 != null && str1.length() > 0);


int[] intArray = new int[str1.length()];

for (int i = 0; i < str1.length(); i++) {
intArray[i] = Character.digit(str1.charAt(i), 10);
}
determineNextHighest(intArray);

System.out.printf("Final Value =>" + Arrays.toString(intArray));
}

public static void determineNextHighest(int[] array) {

int len = array.length - 1;
int index = 0;
int j = len;

for (; j > 0; j--) { // iterate till n-1 < n and determine the index where swap happens
if ((array[j - 1] < array[j])) {
index = j - 1;
break;
}
}

if (index == 0) { // no solution here.. for digits in descending order 7654321 etc..
return;
}

findImmediateGreaterAndSort(array, j - 1, len);

}

// the next highest int to be swapped with
private static void findImmediateGreaterAndSort(int[] array, int i, int len) {
int noToSwap = array[i];
for (int j = len; j > i; j--) {
if (noToSwap < array[j]) {
swap(array, i, j); // swap
break;
}
}

// System.out.printf("1st Value =>" + Arrays.toString(array));

//reverse found subarray .. the subarray from i + 1 to len is already in desc order. just reverseing will sort it in asc order
i = i + 1;
for (int x = 0; x <= (len - i) / 2; x++) {
swap(array, i + x, len - x);
}
}

private static void swap(int x[], int a, int b) {
int t = x[a];
x[a] = x[b];
x[b] = t;
}

}}

- aj September 19, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Take the integer as string arg, decimals; scan right to left, compare sequentially (right to left) everything on the left with current, if current is larger - swap; ascending sort for the digits on the right side of the swap; otherwise make current the one to the left of the previous current, repeat.

- aaa September 19, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Y sort. U already know that all numbers to the rt are in non-increasing order. Shouldn't digit reversal be enough?

- bbb September 21, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

i have written this code for this task.
it take d two input number
as a output it return least greater number and max lowest num.

- psan September 19, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can solve it in another way, hopefully it would work for all the cases.
I am explaining using 2 examples:
1. 7684 - what is the next larger number - (ans : 7846)

Sort the numbers :
4 - a
6 - b
7 - c
8 - d

So, given number 7684 = cbda
Next larger number : check "d" and "a", since d > a the swapping wouldn't help
check : "b", "d" and "a"
For the 1st position - fill "d" as a<b (as we are looking for next greater no.)
For all the rest nos. we just select the least, to make it as small as possible.
For the 2nd position - "a"
For the 3rd position - "b"

So, the answer is : cdab - Using the table shown above = 7846

Example 2 : 24965 - What is the next larger number (ans : 25469)

2 - a
4 - b
5 - c
6 - d
9 - e

24965 = abedc

Since d > c (swapping c to d not helpful) and (e > c and e > d - so swapping of "c", "d" and "e" is not helpful either), so lets take a look at next possibility : "b""e""d""c"

Since b < c, it is definitely going to help find next larger number :
so, swapping "bedc" to "c???" (for ? find the smallest of the remaining) to "cb??" to "cbde" gives us the answer :

acbde = 25469.

- Anshu September 20, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Look at what std::next_permutation does.

Also search the web for Narayana Pandita's algorithm (which is the same as std::next_permutation I believe).

- Anonymous September 20, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

say the number is 9888 the next highest number will be what.. according to the question...since using the existing digits we cannot get next higest number...

- DNS September 20, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

For numbers like 9888, print -1..
I think Insertion Sort will work the best.

Letz take 126975
Start from the right and start inserting

Next number -> Sorted Array
5 -> 5
7 -> 57
9 -> 579
(Till now we were inserting only on one side i.e right side - No shifts were required)

6 -> Now we need shifts, instead what we will do is pop the number which is taking the 6's place i.e 7 and bring it to front. Place 6 at its position and we are done

Now we have 7569...Add digits in front which are not yet processed i.e 12

So, final ans will be 127569..

- Nisarg September 20, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

<pre lang="" line="1" title="CodeMonkey60315" class="run-this">int getLargerNum(int dnum)
{
int num[32];
int size = 31;
int cnum = dnum;
while (cnum && size)
{
num[size--] = cnum%10;
cnum /= 10;
}
for (int i = 31;i > size+1;i--)
{
if (num[i] > num[i-1])
{
for (int j = i;j < 31;j++)
{
if (num[j] < num[i] && num[j] > num[i-1])
swap(num+i,num+j);
}
swap(num+i,num+i-1);
for (int j = 31;j > i-1;j--)
{
for (int m = i;m < j;m++)
{
if (num[m] > num[m+1])
swap(num+m,num+m+1);
}
}
break;
}
}

int ret = 0;
for (int j = size+1;j < 32;j++)
{
ret = ret*10+num[j];
}
return ret;
}
</pre><pre title="CodeMonkey60315" input="yes">
</pre>

- Anonymous September 20, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice solution .
But Complexity will be more in this case .

- Nitin September 20, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

using System;
using System.Collections.Generic;
using System.Text;


namespace Digits
{
    class Program
    {
     
       //Simply find the max of the digits starting from the second position. 
       //So, if your number is 7585. 
       //Split the number into digits {7,5,8,5} and find the maximum of the set 
       //{5,8,5}. of course, it can be generalized to any number.

        static void Main()
        {
            int num = 7585;
            int[] digits = new int[4];
            int index = 4;
            int maxIndex = 0;
            int max = -1;

            while (num != 0)
            {
                int rem = (num % 10);
                num /= 10;

                digits[--index] = rem;
                if (index != 0 && rem > max)
                {
                    maxIndex = index;
                    max = rem;
                }
            }

            //Reconstruction
            int newNum = digits[0]*10 + digits[maxIndex]; 

            for (int i = 1; i < digits.Length; i++)
              if(i != maxIndex)
                newNum = (newNum * 10) + digits[i];


            Console.WriteLine(newNum);

            

        }
    }
}

- Ayad September 20, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

go from right to left and add digits one by one.
eg.
let's say num is 76354-
5 > 4 so nothing can be done nd we have to go one more left.
3<5 and 3 < 4 so swap 3 with rightmost digit i.e. 4 and sort rest digits
rest of the left digits would be same.

so ans is - 76435

- Anurag September 20, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Taking the example 7465

start from the right

Traverse till you find a digit bigger than the immediate left.( 4 is less than 6)

Exchange it with the next largest digits from the right of the array(since 5 is less than 6, exchange 4 with 5)

Now arrange the remaining digits in ascending order(46)

The number generated will be 7546

- Aztec September 21, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

wt abt 73741 ??

- Nitin September 21, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Nitin: ask ur brain to work on. You like spoon-feeding...

73741-> swap(3,4) -> 74731 -> reverse(731) -> 74137.

Got, you dumb stupid?

- anonymous2 September 21, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Aztec can you test your solution with number 1992 ?

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

Here is slightly modified version of cinderella.
1. Go from right to left till the current number is less than immediate left. (Store all the left numbers in array call leftArr and note they are already sorted.)
2. Find the number in leftArr thats immediate bigger than current number and swap with current number. Note that our new leftArr is still sorted.
3. starting to right of new current number, moving towards right end, replace all the numbers with leftArr in increasing order.
Step 2 will be order O(log(n)) so overall order will be O(nlog(n)).

I have yet to code it down. :) But i think it will work for any size.

- Anonymous September 21, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//Don't know if my code works for any case. It works so far.
//Performance might be boosted by using quick sort instead of bubble sort.
public class NextLarge {

public static void main(String[] args){

int[] data = {8,1,8,9,5,3,2};

int[] nextlarge = mynextlarge(data);

for(int i=0;i<nextlarge.length;i++){
System.out.print(String.valueOf(nextlarge[i])+' ');
}
}

public static int[] mynextlarge(int[] data){


int current = data.length-1;
while(true){
int pos = maxpos(data,current);
if(pos==current){
current--;
}else{
int tmp = data[current];
data[current] = data[pos];
data[pos] = tmp;
data = asendright(data,current);

break;
}
if(current<0)
break;
}
return data;
}

public static int[] asendright(int[] data,int current){
for(int i=current+1;i<=data.length-1;i++){
for(int j=i+1;j<=data.length-1;j++){
if(data[i]>data[j]){
int tmp = data[i];
data[i] = data[j];
data[j] = tmp;
}
}
}
return data;
}
public static int maxpos(int[] data,int current){

if(current == data.length-1){
return current;
}else{
int max = -9999;
int pos = current;
for(int i=current;i<data.length-1;i++){
if(data[i]>max){
max = data[i];
pos = i;
}
}
return pos;
}

}

}

- Tony September 22, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

Following steps should lead to solution:
1. sort the nos
2. In the original no, starting from the 2nd right most position find a position where the no at a position has next higher value than the nos which are right of the no at that position.

3. Now swap the highest no which is found at the right side of that no with that no.

4. starting from the next right position start filling the positions with the nos such that the nos are not in left of the position found in step 2.

ex- Given no is 24965

step 1. 24569

step 2. in the original no ie 24965, starting from 6 we check whether we have any value which is higher than it on its right.. no value found (since 5 is smaller than 6)
next get the 9 and start checking to its right again no value higher than itself.
next check 4, since we have next highest value on it right which is 5.

step 3: swap 4 and 5 so our valid no till now would be 25

step 4: Now chk the sort value found in step 1 fetch one value at a time...and append the values if they are not in the no found in the step 3....
so the no will become

25469

I hope this would be somewhat clear to you...here is a program for it ....let me know if it needs any corrections.

/******** Find the next higher value for a given no *******/

#include<stdio.h>
#include<string.h>

void
   get_sorted(int a, int arr_no[], int sort[], int n){
      
      int i, j, tmp;
      
      for(i=0; i<n; i++) {
         arr_no[n-i-1]=a%10;
         a=a/10;
      }

      memcpy(sort, arr_no, n*sizeof(int) );
      
      for(i=1; i<n; i++)
      {
         j=i-1;
         while(j>=0)
         {
            if(sort[j] > sort[j+1])
            {
               tmp=sort[j];
               sort[j]= sort[j+1];
               sort[j+1] = tmp;
            }
            
            j--;
         }
      }
      
      for(j=0; j<n; j++)
      printf("%d -- %d\n",arr_no[j], sort[j]);
      
      
      printf("\n");   
   }
 
 
int
 nxt_higher_value(int x, int a[], int n) {
 
   int i;
   int large=x;
   
   for(i=x+1; i<n; i++)
   {
      if(a[i] > a[large])
         large=i;
   }

   printf("%d %d\n", large, a[large]);
    
   if(large == x)
      return -1;
      
   else
      return large;
 }   
  
   
int
 main()
 {
   int a=7585;
   int n=4;

   int sort[n];
   int arr_no[n];
   int val, i, j, k;
   
   get_sorted(a, arr_no, sort, n);

   for(i=n-2; i>=0; i--)
   {
      val=nxt_higher_value(i, arr_no, n);
      if(val >= 0)
      {
         arr_no[i]= arr_no[val];
         break;
      }
   
   }

   int flag_continue;
   
   
   for(k=0; k<n; k++)
   {
      flag_continue=0;
      for(j=0; j<=i; j++)
      {
         if(sort[k] == arr_no[j])
         {
            flag_continue=1;
            break;
         }
      }
   
      if(flag_continue)
      continue;
      
      arr_no[i+1]=sort[k];
      i++;   
   }
   
   
   for(i=0; i<n; i++)
      printf(" %d", arr_no[i]);
      
      
   printf("\n");       
   return 0;
 }

- raja September 23, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think your approach is not correct for each case
you can take the case of 24965. on this input your solution will give output as 29456 while the correct solution is 25469. So look at your code again.

- jar September 27, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think the simplest solution for this would be to simply extract the digits, store them in an array and sort it in descending order. If the array is already sorted, return -1 else return the sorted array. The question asks to find "a" number which is larger, not the immediately larger number. Can anyone tell me if there is a problem with this solution?

- Neha September 23, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

However, if the immediately larger number is to be found.. I believe this solution should work:

1. Extract the numbers and save them in an array.
2. Starting from the right, start scanning the array such that you find a location where the array stops being sorted in an ascending order. ( asc from right )
3. At that position, find the difference between all the digits and the digit in question. Swap it with the digit which has the smallest difference.
4. For all the digits to the right of the digits in question, sort them in descending order.

e.g. lets say 126975
starting from left, 75 is sorted, 975 is sorted, 6975 is not.
x = 6
6-5 = 1
6-7 = -1
6-9 = -3

Since smallest negative difference is with 7, swap the digits 6 and 7, we get.. 127965
Beginning from the right of 7, i.e. position x, sort all the digits in asc order, i.e. smallest first.. we get.. 127569.

- NS September 23, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
#include<string.h>

void reverse(char s[])
{
printf("entring reverse\n");
int c, i, j;
for (i = 0, j = strlen(s)-1; i < j; i++, j--)
{
c = s[i];
s[i] = s[j];
s[j] = c;
}
printf("exit reverse\n");
}

int atoi(char s[])
{
printf("entring atoi s=%s\n",s);
int i, n, sign;
for (i = 0; (s[i] == ' '); i++) /* skip white space */
;
sign = (s[i] == '-') ? -1 : 1;
if (s[i] == '+' || s[i] == '-') /* skip sign */
i++;
for (n = 0; (s[i] >='0' && s[i] <= '9'); i++)
n = 10 * n + (s[i] - '0');
printf("exit atoi\n");
return sign * n;
}

void itoa(int n , char s[])
{
printf("entring itoa\n");
int i, sign;
if ((sign = n) < 0) /* record sign */
n = -n; /* make n positive */
#include<stdio.h>
#include<string.h>

void reverse(char s[])
{
printf("entring reverse\n");
int c, i, j;
for (i = 0, j = strlen(s)-1; i < j; i++, j--)
{
c = s[i];
s[i] = s[j];
s[j] = c;
}
printf("exit reverse\n");
}

int atoi(char s[])
{
printf("entring atoi s=%s\n",s);
int i, n, sign;
for (i = 0; (s[i] == ' '); i++) /* skip white space */
;
sign = (s[i] == '-') ? -1 : 1;
if (s[i] == '+' || s[i] == '-') /* skip sign */
i++;
for (n = 0; (s[i] >='0' && s[i] <= '9'); i++)
n = 10 * n + (s[i] - '0');
printf("exit atoi\n");
return sign * n;
}

void itoa(int n , char s[])
{
printf("entring itoa\n");
int i, sign;
if ((sign = n) < 0) /* record sign */
n = -n; /* make n positive */
i = 0;
do
{ /* generate digits in reverse order */
s[i++] = n % 10 + '0'; /* get next digit */
} while ((n /= 10) > 0); /* delete it */
if (sign < 0)
s[i++] = '-';
s[i] = '\0';
reverse(s);
printf("exit itoa\n");
}

int find_bigger(int num)
{
printf("inside find_bigger\n");
char str[20]= "\0";

char temp;
int i,j;
itoa(num,str);
printf("str=%s\n",str);


i = strlen(str)-1;
j = strlen(str)-2;

while(j >= 0)
{
if(str[j] < str[i])
{
temp = str[j];
str[j] = str[i];
str[i] = temp;
break;
}
else
{
i--;
j--;
}
}
printf("returning from find_bigger\n");
return atoi(str);
}

int main()
{
int num;
num = find_bigger(4555);
printf("num = %d\n", num);
return 0;

}

- shivam September 23, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I am not sure if any body has already posted this solution:
found = false;

- for(i = n - 1; !found && i > 0; i --)
  {
     if(numStr[i-1] < numStr[i])
     {
        found = true;
     }
  }
  if(found)
  {
     a[i];
     // do a insertion sort
     for(j = i+1; j < n && a[j] > a[i]; j++)
       ;
     swap(a[i], a[j-1]);
     reverse(a , i+1, n-1);
     // at this point a[] has the next number than what was originally 
     // present in a[]     
     return 1;
  }
  else
      return -1;

- Anonymous September 24, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

sry for first example output : 8765

- sekhar740 September 27, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi... i think the output is 5687

- SecretAgent September 27, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Sort the number

- Anonymous September 27, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Just do selection sort, instead of calculating min at each iteration calculate max and replace with the first element.

- Nascent Coder September 27, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class NextHighest
{
	public void sort(int[] num, int i, int length)
	{
		// sorting algorithm
	}
	
	public static void main(String[] args)
	{
		int[] num = new int[]{7,5,8,6};
		int temp = num.length-1;
		int i;
		for(i=num.length-1;i>1;i--)
		{
			if(num[i] > num[i-1])
			{
				int swap = num[i-1];
				num[i-1] = num[temp];
				num[temp] = swap;
				break;
			}
			else
			{
				if(a[temp] > num[i])
					temp = i;
			}
		}
		sort(num,i,num.length);
	}
}

Hi all....

I don't know how much right my solution is...
Give your review...
I have taken an example in the code. Replace that with your input and try.

Thanks...... All the best

- Sunil September 27, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hey.... it is not working. I checked it myself... Will be back with a right solution :)

- Sunil September 27, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

<pre lang="" line="1" title="CodeMonkey92592" class="run-this">int FindNextGreater(int num)
{
int previousDigit = -1;
int numOfDigits = NumOfDigits(num);
if(numOfDigits==1)
return -1;
int indexOfPreviousDigit = numOfDigits;
while(num>0)
{
int digit = num%10;
if(digit>previousDigit)
{
previousDigit = digit;
indexOfPreviousDigit--;
continue;
}
return Swap(num, indexOfPreviousDigit, indexOfPreviousDigit-1);
}
return -1;
}</pre><pre title="CodeMonkey92592" input="yes">
</pre>

- Anonymous September 27, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

i tried this, but its giving me error,
1) NumOfDigits not defined in this scope


any idea how to get rid of this err

- maverick October 01, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

i tried this, but its giving me error,
1) NumOfDigits not defined in this scope


any idea how to get rid of this err

- maverick October 01, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

i tried this, but its giving me error,
1) NumOfDigits not defined in this scope


any idea how to get rid of this err

- maverick October 01, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

1.Start from right to left reading each digit
2.If the entire number is read in ascending order then return -1
3.Else stop when it is decreased, swap the decreased digit with the digit immediately bigger than the decreased digit from the set of surpassed digits
4. Sort the remaining digits to the right of the swapped digit

Ex: 1092
1.come from right, the digit decreased from 9 to 0
2. the surpassed digits are 2,9 so swap 0 with immediate bigger digit i.e, 2 (results in 1290)
3. sort remaining digits (1209)

- SecretAgent September 27, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Here is the solution written in C# (Input taken as string to support larger numbers also)

private static string GetNextHighest(string num)
        {
            StringBuilder number = new StringBuilder(num);
            bool flag = false;
            int index;
            int[] numberCount = new int[10];
            if (number.Length == 1)
            {
                return number.ToString();
            }
            numberCount[Convert.ToInt32(char.ConvertFromUtf32(number[number.Length - 1]))]++;
            for (index = number.Length - 2; index >= 0; index--)
            {
                if (number[index] < number[index + 1])
                {
                    flag = true;
                    int swapNumber = Convert.ToInt32(char.ConvertFromUtf32(number[index]));
                    numberCount[swapNumber]++;
                    for (int iter = swapNumber + 1; iter < 10; iter++)
                    {
                        if (numberCount[iter] > 0)
                        {
                            numberCount[iter]--;
                            number[index++] = Convert.ToChar(iter+48);
                            break;
                        }
                    }
                    break;
                }
                numberCount[Convert.ToInt32(char.ConvertFromUtf32(number[index]))]++;
            }
            if (flag)
            {
                for (int iterator = 0; iterator < 10; iterator++)
                {
                    for (int iter = 0; iter < numberCount[iterator]; iter++)
                    {
                        number[index++] = Convert.ToChar(iterator + 48);
                    }
                }

                return number.ToString();
            }
            else
            {
                return "-1";
            }

}

- SecretAgent September 27, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

this algo will fail if number = 1050 or 1171

- addi October 18, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

sorry it working....ignore above comment

- addi October 18, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think we're asked for the largest number, in which case we're looking for 9210.

- akasaka December 01, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

surely, neha you are the dumbest person i have ever witnessed posting on forums things that are so obvious.
if it is true what you are saying, its a question even new born baby can solve! if you dont understand question please get out of here (go join nursery school)

- vik September 28, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
using namespace std;
int main(){
    char str[1000];
    while(cin>>str){
                    if(!next_permutation(str,str+strlen(str)))
                    cout<<"-1\n";
                    else
                    cout<<str<<"\n";
                    }
                    }

- shashank.neo September 28, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can also use the linked list approach
1. Get the last digit from the no and add it to linked list in increasing order.
2. Convert it to no from the sorted linked list.

int BiggestPossibleNo(int n) {
  while( n > o) {
	rem = n % 10;
	n = n / 10;
	head = insertSortList(rem); // adds to list in increasing order
	no = convertListNo(head);
  }
  retutn no;
}

int convertListNo(Node head) {
  int power = 1;
  int no = 0;
  while(head) {
	no = power * (head->no) + no;
	head = head->next;	
	power *= 10;
  }

  return no;
}

- Mustafa October 01, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Sorry guys the convertListNo(head) should be called outside the while loop in BiggestPossibleNo().

int BiggestPossibleNo(int n) {
  while( n > o) {
	rem = n % 10;
	n = n / 10;
	head = insertSortList(rem); // adds to list in increasing order
  }
  	no = convertListNo(head);
  retutn no;
}

- Mustafa October 01, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

why am i doing this when i can directly sort and put the elements in a stack, pop it and get the max val. Sort in asc and push in stack

- Anonymous October 02, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Use bucket sort to sort the digits and also count their frequencies and then print them in descending order with each digit occurring according to its frequency.

- Avinash October 02, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Use bucket sort to sort the digits and also count their frequencies and then print them in descending order with each digit occurring according to its frequency.

- Avinash October 02, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Check code at : http: // ideone.com / fKenf

- ajit.it.engg October 03, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

<pre lang="" line="1" title="CodeMonkey7194" class="run-this">//No need of any data structures
int main()
{
int n=9768;
int num=n;
int reverse=0;
int digit,right;
while(num){
digit=num%10;
num/=10;
right=0;
int p=1;
while(reverse && (reverse%10) < digit){
right=(reverse%10)*p+right;
p*=10;
reverse/=10;
}
reverse=(((reverse*10)+digit)*p)+right;
}
if(n!=reverse) cout<<reverse; else cout<<-1;

cin.ignore(2);
return 0;
}</pre><pre title="CodeMonkey7194" input="yes">
</pre>

- Anonymous October 14, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

care to explain ??
what you are trying to achieve here...

- Anonymous October 15, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

gr8 man.. it s working fine

- mgr October 16, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

int findBigger(int input)
{
   int dig = 0;
   int digPre = 0;
   int i = 0;
   int temp = input;

   if (temp <= 0)
   {
      return -1;
   }

   while (temp != 0)
   {
      digPre = dig;
      dig = temp % 10;
      temp = temp / 10;
      if (dig < digPre)
      {
         break;
      }
      i++;
   }

   return input + 9 * 10^(i-1) * (digPre - dig);
}

- Anonymous October 17, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int findBigger(int input)
{
int dig = 0;
int digPre = 0;
int i = 0;
int temp = input;

if (temp <= 0)
{
return -1;
}

while (temp != 0)
{
digPre = dig;
dig = temp % 10;
temp = temp / 10;
if (dig < digPre)
{
break;
}
if (temp==0)
{
return -1;
}
i++;
}

return input + 9 * 10^(i-1) * (digPre - dig);
}

- Anonymous October 17, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

time complexity: O(k^2)
code works.
int method(string s)
{
vector<int> v;
int i,j;
int flag=0;
for(i=s.size()-1;i>=0 && !flag;i--)
{
for(j=i-1;j>=0 ;j--)
if(s[j] < s[i])
{
flag=1;
cout<<s[i]<<" "<<s[j]<<" "<<i<<" "<<j<<"\n";
break;
}
if(j<0)
v.push_back(s[i]-'0');

}
if(flag==1)
{
v.push_back(s[j]-'0');
s[j]=s[i+1];
sort(v.begin(),v.end());
for(int i=j+1,k=0;i<s.size();i++,k++)
s[i]=v[k]+'0';
}
cout<<s;
}

- Anonymous October 25, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

<pre lang="" line="1" title="CodeMonkey67436" class="run-this">class BiggestNumber {

int biggestNumber(int n) {
int originalNumber = n;
int[] digitFrequencies = new int[10];
boolean isNegative = n < 0;
if (isNegative) {
n *= -1;
}
while (n != 0) {
++digitFrequencies[n % 10];
n /= 10;
}
n = 0;
if (isNegative) {
for (int i = 1; i < 10; ++i) {
while (digitFrequencies[i] != 0) {
n = n * 10 + i;
digitFrequencies[i] = digitFrequencies[i] - 1;
}
while (digitFrequencies[0] != 0) {
n *= 10;
digitFrequencies[0] = digitFrequencies[0] - 1;
}
}
n *= -1;
} else {
for (int i = 9; i > -1; --i) {
while (digitFrequencies[i] != 0) {
n = n * 10 + i;
digitFrequencies[i] = digitFrequencies[i] - 1;
}
}
}
return n == originalNumber ? -1 : n;
}

public static void main(String[] args) {
BiggestNumber instance = new BiggestNumber();
System.out.println(instance.biggestNumber(0));
System.out.println(instance.biggestNumber(1230));
System.out.println(instance.biggestNumber(-2130));
System.out.println(instance.biggestNumber(3210));
System.out.println(instance.biggestNumber(-1023));
}
}
</pre><pre title="CodeMonkey67436" input="yes">
</pre>

- smffap November 25, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Please ignore this. See the corrected one below.

- smffap November 25, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

<pre lang="" line="1" title="CodeMonkey69754" class="run-this">class BiggestNumber {

int biggestNumber(int n) {
int originalNumber = n;
int[] digitFrequencies = new int[10];
boolean isNegative = n < 0;
if (isNegative) {
n *= -1;
}
while (n != 0) {
++digitFrequencies[n % 10];
n /= 10;
}
n = 0;
if (isNegative) {
boolean isZeroThere = digitFrequencies[0] != 0;
if(isZeroThere) {
for(int i = 1; i < 10; ++i) {
if(digitFrequencies[i] != 0) {
n = n * 10 + i;
digitFrequencies[i] = digitFrequencies[i] - 1;
break;
}
}
while (digitFrequencies[0] != 0) {
n *= 10;
digitFrequencies[0] = digitFrequencies[0] - 1;
}
}
for (int i = 1; i < 10; ++i) {
while (digitFrequencies[i] != 0) {
n = n * 10 + i;
digitFrequencies[i] = digitFrequencies[i] - 1;
}
}
n *= -1;
} else {
for (int i = 9; i > -1; --i) {
while (digitFrequencies[i] != 0) {
n = n * 10 + i;
digitFrequencies[i] = digitFrequencies[i] - 1;
}
}
}
return n == originalNumber ? -1 : n;
}

public static void main(String[] args) {
BiggestNumber instance = new BiggestNumber();
System.out.println(instance.biggestNumber(0));
System.out.println(instance.biggestNumber(1230));
System.out.println(instance.biggestNumber(-2130));
System.out.println(instance.biggestNumber(3210));
System.out.println(instance.biggestNumber(-1023));
}
}

</pre><pre title="CodeMonkey69754" input="yes">
</pre>

- smffap November 25, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

some people think they are over smart. we are here to study so please behave like a student not like a rascal.

here is my java code. please check it and notify if there is any problem. all constructive comments are welcome.

int given = 73741;
String s = Integer.toString(given);
int [] arr = new int[s.length()];
for(int i=0; i<s.length(); i++){
	arr[s.length()-1-i] = given%10;
	given = given/10;
}
boolean flag = true;
int k = 0;
int ii = (arr.length-1);
while(ii>=0 && flag==true){
	for(k=ii-1; k>=0; k--){
		if(arr[k] < arr[ii]){
			int temp = arr[ii];
			arr[ii] = arr[k];
			arr[k] = temp;
			flag = false;
			break;
		}
	}
	ii--;
}
quicksort(arr, k+1, arr.length-1);
System.out.println("\n");
for(int i=0; i<arr.length; i++){
	System.out.print(arr[i]);
}

- CAFEBABE December 30, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Take a example of 13283
Your code will 13382 but the answer is 13328 .

- Nitin January 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

int a;
	cin>>a;
	int b=a;

	int c[10];

	for(int i=0;i<10;i++)
		c[i]=0;

	int x=-1,y=-1;
	i=0; 

	while(b!=0)
	{
		i++;
		x=b%10;
		c[x]++; 
      b/=10;
		if(y>x)
			break;
		y=x;
	}

	if(x==y)
		cout<<"No. is largest";
	else
	{

	for(int j=++x;j<10;j++)
		if(c[j]>0)
		{
			b=b*10+j;
			c[j]--;
			i--;
			break;
		}

	int k=0;
	for(j=0;j<i && k<10;)
	{
		if(c[k]>0)
		{
			b=b*10+k;
			c[k]--;
			j++;
		}
		else
			k++;
	}

	cout<<b;
   }

- Puneet A August 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I have used here the counting sort to store all the digits till I get the two digits in descending order from right to left.

- Puneet A August 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

My approach:

public int immediateGreater(int num) {
		char[] string = String.valueOf(num).toCharArray();
		int length = string.length;
		if(length<=1)
			return -1;
		int[] temp = new int[length];
		for(int i=0; i<temp.length; i++) {
			temp[i] = 10;
		}
		int realLength = 1;
		temp[0] = string[length-1]-'0';
		for(int i=length-2; i>=0; i--) {
			if(string[i]>=string[i+1]) {
				temp[realLength] = string[i]-'0';
				realLength++;
			}else {
				int min = string[i+1]-'0';
				int pos = i+1;
				for(int j=0; j<realLength; j++) {
					if(temp[j]<min&&temp[j]>(string[i]-'0')) {
						min = temp[j];
						pos = j;
					}
				}
				int y = string[i] - '0';
				string[i] = (char)(min+48);
				temp[pos] = y;
				java.util.Arrays.sort(temp);
				pos = 0;
				for(int j=realLength; j>0; j--) {
					string[string.length-j] = (char) (temp[pos++]+48);  
				}
				return Integer.parseInt(new String(string));
			}
		}
		return -1;
	}

- sz2376@columbia.edu November 21, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 vote

Extract all d digits of a given,store it in an array sort d array in desc orer .

- hasinamjanu September 19, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It will no be over .. :)
Ex :- 102
Answer should be 120 but if u will sort it will result in 210 ;)
Complexity will be increase if you will take larger digits !!

- Nitin September 19, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The question doesnt say to give the immediately larger number. It asks you to find "a" larger number. The complexity argument would actually come into picture if we are literally talking about n to be so significant that it would take too much time. I think hasinamjanu's solution is correct.

- Neha September 23, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

If qus is not specific about largest OR larger...!
sorting is quite lengthy... below i am trying to optimize it....!

if number given is ABCD then :
pick A.. match with remaining digits... if found greater then A... swap digits....
else pick B compare with remaining if found greater then B.. swap digits...
else pick C .... and so on...!

- PKT September 27, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

surely, neha you are the dumbest person i have ever witnessed posting on forums things that are so obvious.
if it is true what you are saying, its a question even new born baby can solve! if you dont understand question please get out of here (go join nursery school)

- victor September 28, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hey vector.. dats not the way to treat ppl.

- vector October 18, 2011 | 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