Amazon Interview Question
Applications DevelopersCountry: India
//Assuming number is loaded into an array of characters with size num_digits. The same algo can be modified to not use additional array and extract the digits at a given position.
cur_max = num[num_digits-1];
cur_max_pos = num_digits-1;
for(i=num_digits-2; i>=0; i--) {
if (num[i] < cur_max) {
swap(num, i, cur_max_pos);
break;
}
if(num[i] > cur_max)
cur_max_pos = i;
}
if(i<0) {
//Digits sorted in decreasing order from beginning
printf("Sorry, no number greater than this possible");
}
sort_asending(num, i+1, num_digits);
Find the first digit starting from least significant digit that has a greater digit and with the smallest difference when compared with the other digits on the right. Swap these two. Then sort the remaining digits to its right in decreasing order.
//Assuming number is loaded into an array of characters with size num_digits. The same algo can be modified to not use additional array and extract the digits at a given position.
for(i=num_digits-2; i>=0; i--) {
min_diff = 10;
min_diff_pos = -1;
for(k=i+1; k<num_digits; k++) {
if(num[ k ] > num[ i ]) {
if(num[k] - num[i] < min_diff) {
min_diff = num[k] - num[i];
min_diff_pos = k;
}
}
}
if(min_diff_pos != -1) {
//Found a position to alter
break;
}
}
if(i<0) {
//Digits sorted in decreasing order from beginning
printf("Sorry, no number greater than this possible");
}
swap(num, i, k);
sort_asending(num, i+1, num_digits);
printf("%s", num);
Let the digits be stored in an array of size n.
for (j = n-1; j >=1; j--) {
for (i = j-1; i>=0; i--) {
if (A[j] >A[i]) {
swap(A[i], A[j]);
return;
}
}
print "Rearrangement of digits not possible, the given number has the highest value"
}
One thing to note is rearrangement as asked in the question is not always possible. For ex: in the digits are in non-increasing order as in 3321, no arrangement that can lead to next higher value is possible.
Otherwise, starting from the right-most end, we can keep comparing it with elements to it's left and swap them if the right side element is greater than the left side element. Repeat the process by starting again at the second right-most element and so on, until a swap could be performed or print out that such an arrangement is not possible
1. Traverse the whole number and store each digit in array
2. Start from last position to first position
i = n-1, j = n -2
while ( j >= 0)
if ( data[n - i] > data [i -2]
{
swap the value for (n - i) & (n-j). Print the same and break.
}
else
{
// Swap the value for (n - i) & (n-j).
}
i = j ;
--j;
1. Traverse the whole number and store each digit in array
2. Start from last position to first position
i = n-1, j = n -2
while ( j >= 0)
{
if ( data[n - i] > data [i -2]
{
swap the value for (n - i) & (n-j). Print the same and break.
}
else
{
// Swap the value for (n - i) & (n-j).
}
i = j ;
--j;
}
Starting from tenth place move to left.
1. Replace the current position digit with the digit greater then this in right.
2. Arrange the all right digits in ascending order.
2 5 6 7 5 4 3 2 1 <- Initial
^
2 5 7 6 5 4 3 2 1 <- Step 1
^ ^ 6<->7
2 5 7 1 2 3 4 5 6 <- Step 2
^-----------^ ascending order sort
Correct me if m wrong.
Find a digit smaller than digits behind, swap two digits,and sort the digits from that position
public static int[] getNextLargeNumber(int[] numbers) {
if (numbers == null || numbers.length <= 1)
return null;
boolean existLargerNumber = false;
int i = 0, j = 0;
//check if existing a digit is smaller than tailing digits
for (i = numbers.length - 1; i >= 0; i--) {
for (j = i - 1; j >= 0; j--) {
if (numbers[i] > numbers[j]) {
existLargerNumber = true;
break;
}
}
if (existLargerNumber) {
break;
}
}
if (existLargerNumber) {
int[] largerNum = numbers.clone();
swap(largerNum, i, j);
sort(largerNum, j);
return largerNum;
} else {
return null;
}
}
private static void sort(int[] largerNum, int start) {
for(int i= largerNum.length -1; i> start; i--){
for(int j=largerNum.length -1; j>i; j--){
if(largerNum[i] > largerNum[j]){
swap(largerNum, i, j);
}
}
}
}
private static void swap(int[] largerNum, int i, int j) {
int temp = largerNum[i];
largerNum[i] = largerNum[j];
largerNum[j] = temp;
}
#include <assert.h>
#include <algorithm>
#include <vector>
using std::vector;
using std::pair;
using std::sort;
using std::swap;
unsigned int RearrangeToNext(unsigned int x) {
if (x == 0) return 0;
vector<int> vec;
unsigned int xx = x;
while (xx > 0) {
vec.push_back(xx % 10);
xx = xx / 10;
}
int prev = 0;
auto it = vec.begin();
decltype(it) it_swap;
auto it_end = vec.end();
while (it != it_end) {
if (prev > *it) {
auto it2 = vec.begin();
it_swap = vec.end();
while (it2 != it) {
if (*it2 > *it) {
if (it_swap == vec.end() || *it_swap > *it2) {
it_swap = it2;
}
}
++it2;
}
if (it_swap != vec.end()) break;
}
prev = *it;
++it;
}
if (it == it_end) return x;
swap(*it, *it_swap);
sort(vec.begin(), it, [](int lhs, int rhs) { return (lhs > rhs); });
unsigned int rval = 0;
auto rit = vec.crbegin();
auto rit_end = vec.crend();
while (rit != rit_end) {
rval = rval * 10 + *rit;
++rit;
}
assert(rval > x);
return rval;
}
private static String getNextGreaterNumber(int num[]) {
final String orgNum = ""+num[0]+num[1]+num[2]+num[3];
boolean isDesc = false;
for(int j=num.length -1; j>=1; j--) {
if(num[j] > num[j-1]) {
System.out.println("first");
isDesc = false;
num[j] = num[j] + num[j-1];
num[j-1] = num[j] - num[j-1];
num[j] = num[j] - num[j-1];
break;
} else {
System.out.println("second");
isDesc = true;
num[j] = num[j] + num[j-1];
num[j-1] = num[j] - num[j-1];
num[j] = num[j] - num[j-1];
}
}
System.out.println(isDesc);
if(isDesc)
return orgNum;
return ""+num[0]+num[1]+num[2]+num[3];
}
private static String getNextGreaterNumber(int num[]) {
final String orgNum = ""+num[0]+num[1]+num[2]+num[3];
boolean isDesc = false;
for(int j=num.length -1; j>=1; j--) {
if(num[j] > num[j-1]) {
System.out.println("first");
isDesc = false;
num[j] = num[j] + num[j-1];
num[j-1] = num[j] - num[j-1];
num[j] = num[j] - num[j-1];
break;
} else {
System.out.println("second");
isDesc = true;
num[j] = num[j] + num[j-1];
num[j-1] = num[j] - num[j-1];
num[j] = num[j] - num[j-1];
}
}
System.out.println(isDesc);
if(isDesc)
return orgNum;
return ""+num[0]+num[1]+num[2]+num[3];
}
package com.test.utils;
import java.util.Arrays;
public class NextBigNumber {
public static void main(String aa[])
{
int givenNum = 3120;
int tempNum = givenNum;
int reminder = givenNum %10;
int numOfDig = String.valueOf(givenNum).length();
if(numOfDig<2)
{
return ;
}
int[] numarr = new int[numOfDig];
for(int i=0;i<numOfDig;i++)
{
reminder = givenNum %10;
numarr[i] = reminder;
givenNum/=10;
//System.out.println(i+"th element "+numarr[i]);
}
numarr = getSortedArray(numarr,1);
int[] resultArr = swapNum(numarr,1);
int resultNum = getBackNum(resultArr);
if(resultNum > tempNum)
{
System.out.println("Found the next big number of "+tempNum+" which is "+resultNum);
}
else
{
System.out.println("Could not find the next big number of "+tempNum);
}
}
private static int[] swapNum(int[] numArr, int index)
{
boolean numFound = false;
for(int i=index-1;i>=0;i--)
{
if(numArr[i]>numArr[index])
{
int temp = numArr[i];
numArr[i] = numArr[index];
numArr[index] = temp;
numFound = true;
break;
}
}
if(!numFound && index<numArr.length-1)
{
numArr = getSortedArray(numArr,index+1);
return swapNum(numArr, index+1);
}
numArr = getSortedArray(numArr,index);
return numArr;
}
private static int getBackNum(int[] numArr)
{
int result = 0;
for(int i=0;i<numArr.length;i++)
{
int factor = (int)Math.pow(10,i);
result+=(factor*numArr[i]);
}
return result;
}
private static int[] getSortedArray(int[] numArr, int index)
{
int[] sortArr = Arrays.copyOfRange(numArr,0,index);
Arrays.sort(sortArr);
for(int j=0,i=sortArr.length-1;j<sortArr.length;j++,i--)
{
numArr[i]=sortArr[j];
}
return numArr;
}
}
package com.test.utils;
import java.util.Arrays;
public class NextBigNumber {
public static void main(String aa[]) {
int givenNum = 3120;
int tempNum = givenNum;
int reminder = givenNum % 10;
int numOfDig = String.valueOf(givenNum).length();
if (numOfDig < 2) {
return;
}
int[] numarr = new int[numOfDig];
for (int i = 0; i < numOfDig; i++) {
reminder = givenNum % 10;
numarr[i] = reminder;
givenNum /= 10;
}
numarr = getSortedArray(numarr, 1);
int[] resultArr = swapNum(numarr, 1);
int resultNum = getBackNum(resultArr);
if (resultNum > tempNum) {
System.out.println("Found the next big number of " + tempNum + " which is " + resultNum);
} else {
System.out.println("Could not find the next big number of " + tempNum);
}
}
private static int[] swapNum(int[] numArr, int index) {
boolean numFound = false;
for (int i = index - 1; i >= 0; i--) {
if (numArr[i] > numArr[index]) {
int temp = numArr[i];
numArr[i] = numArr[index];
numArr[index] = temp;
numFound = true;
break;
}
}
if (!numFound && index < numArr.length - 1) {
numArr = getSortedArray(numArr, index + 1);
return swapNum(numArr, index + 1);
}
numArr = getSortedArray(numArr, index);
return numArr;
}
private static int getBackNum(int[] numArr) {
int result = 0;
for (int i = 0; i < numArr.length; i++) {
int factor = (int) Math.pow(10, i);
result += (factor * numArr[i]);
}
return result;
}
private static int[] getSortedArray(int[] numArr, int index) {
int[] sortArr = Arrays.copyOfRange(numArr, 0, index);
Arrays.sort(sortArr);
for (int j = 0, i = sortArr.length - 1; j < sortArr.length; j++, i--) {
numArr[i] = sortArr[j];
}
return numArr;
}
}
Algo:
1) Starting from the end of the number keep checking each digit and store max value till the following condition is met:
if(next digit > max)
Once you found max value which is bigger then next digit break.
2) Lets say first smaller digit n which is < max is located on position i.
3) Find the smallest digit which is bigger then n between number which has already been processed (i+1 - length of number) (max value doesn't have to be the smallest bigger digit).
4) Swap n[i] and the number found in 3
5) Sort number located after after i-th position in a ascending order
In your example 2576
1) Starting from the end 6 < 7, 7 > 5 - max is 7 - break;
2 - 3) Find the smallest bigger digit from 5 between 6-7 which is 6.
4) Swap 6 and 5 - 2675
5) Sort number located after 6 in ascending order 2657
What happen if we have 257654321
According to your algo 5 is the (next digit <= max) and we swap it with 1. After sort we have 21234557 which is wrong answer.
you dont need to sort the number you can just reverse the digits after the ith digit swapped
private static void next(int[] number) {
- Anonymous January 13, 2014PriorityQueue<Integer> queue = new PriorityQueue<Integer>();
LinkedList<Integer> list = new LinkedList<Integer>();
int index = -1;
for (int i = number.length - 1; i >= 1; i--) {
queue.add(number[i]);
if (number[i] > number[i - 1]) {
queue.add(number[i - 1]);
boolean done = false;
index = i;
while (!queue.isEmpty()) {
int v = queue.poll();
if (v > number[i - 1] && !done) {
number[i - 1] = v;
done = true;
} else {
list.add(v);
}
}
break;
}
}
if (index != -1) {
for (Integer v : list) {
number[index] = v;
index++;
}
System.out.println(Arrays.toString(number));
}
}