Amazon Interview Question Software Engineer / Developers
Country: United States
Interview Type: Phone Interview
O(n) based solution
123456784987654321
start with a number
123456784 987654321
^Starting from right find the first place where the left-digit is less-than the right-digit is here. Digit "x" is 4
123456784 987654321
^find the smallest digit larger than 4 to the right
123456785 4 98764321
^place it to the left of 4
123456785 4 12346789
123456785123446789
^sort the digits to the right of 5. Since all of them except the '4' were already in descending order, all we need to do is reverse their order, and find the correct place for the '4'
Example 5,6,7,4
from right first place where left < right is 6
smallest digit larger than 6 is 7 move it to left of 6
so now the no is
5764
sort the no post 7
5746 as expected
This works for the number you give, but only because it's the special case where everything after the number is already sorted.
What if you want the next number from the number 5, 6, 7, 4? You move the 7 to the front of the 6, leaving 5,7,6,4, but the (6,4) are not sorted... the result should be 5,7,4,6.
In your example, how wold you get the next number? Your current number is now 123456785123446789, so you want to grab the 6 and swap it with the 5, but then you're left with 123456786123445789 which is not the next-largest.
you rightly pointed out a use case i missed on , i have tried modifying the algo which explains the test case you pointed out as well.And no are not sorted , you got to sort them post fixing your number
Have edited the original Algo posted by me , do let me know if it still doesn't work for a test case you can think of.
We just need to find the right position to swap and reverse. The time complexity is O(n) and space is O(1).
Please refer to STL's next_permutation implementation:
stackoverflow.com/questions/11483060/stdnext-permutation-implementation-explanation
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
int getNextNumber(int number) {
vector<int> digits;
while (number > 0) {
digits.push_back(number % 10);
number /= 10;
}
int i = 0, ii = 1;
while (ii < digits.size() && digits[ii] > digits[i]) {
ii++;
i++;
}
if (ii != digits.size()) {
for (int i = 0; i < ii; ++i) {
if (digits[i] > digits[ii]) {
std::swap(digits[i], digits[ii]);
std::reverse(digits.begin(), digits.begin() + ii);
break;
}
}
} else {
return -1;
}
int next = 0;
for (vector<int>::reverse_iterator it = digits.rbegin(); it != digits.rend();
++it) {
next *= 10;
next += *it;
}
return next;
}
int main() {
cout << getNextNumber(4765) << endl;
}
Time Complexity = O(d lgd), d = number of digits
eg: 4765
Step 1: Scan from right and insert all numbers into priorityqueue(min heap) which are in
increasing order i.e. 5, 6, and 7
Step2: As our pointer is at '7' start de queue and insert elements starting with location of '7' till we get number just greater than 4. As it is min heap, we will get numbers starting from lower most and hence filling them we ensure we are maitaining the shortest possible number.
step 3: as soon as we get a number just greater than 4, place it at location of '4' and place '4' at location where we were while filling the entries starting from '7',
step:4 fill all the entries remaining in the queue from the location where we placed '4'.
Complexity = O(d) for numbers scanning and lg(d) for heapify operation, hence worst is O(d lgd).
code:
public int getNextLargestNumber(int[] numbers){
int lastIndex = numbers.length -1;
PriorityQueue priorityQueue = new PriorityQueue();
while (lastIndex>0 && (numbers[lastIndex-1] >= numbers[lastIndex])){
priorityQueue.add(numbers[lastIndex]);
lastIndex--;
}
priorityQueue.add(numbers[lastIndex]);
if(priorityQueue.size() == numbers.length){
return getInt(numbers);
}
int justGreater = (Integer)priorityQueue.peek();
priorityQueue.remove(priorityQueue.peek());
int start = lastIndex;
while (justGreater < numbers[lastIndex-1]){
numbers[start++] = justGreater;
justGreater = (Integer)priorityQueue.peek();
priorityQueue.remove(priorityQueue.peek());
}
numbers[start++] = numbers[lastIndex-1];
numbers[lastIndex-1] = justGreater;
while (!priorityQueue.isEmpty()){
numbers[start++] = (Integer)priorityQueue.peek();
priorityQueue.remove(priorityQueue.peek());
}
return getInt(numbers);
}
private int getInt(int[] nums){
int number = 0;
for (int i=0; i<nums.length; i++){
number = number*10 + nums[i];
}
return number;
}
Messy solution ahead!
1) Go through the number from the least-significant digit, searching whether there is any digit in a less-significant position that is larger. If there are multiple such digits, choose the smallest.
2) Swap the digit you are at with the minimally larger digit preceding it, then sort all the digits preceding the current digit. So for example if we have 132, we move the 2 to the front and sort the 1 and the 3 to get 213. And then we're done.
3) If we can't find a larger digit preceding any digit, then we're already at the largest number.
Note: I found it a pain to use % and / operators to get digits, so I did the lazy thing and put the digits into an array, least-significant at position 0 and most-significant at n.
import java.util.Arrays;
import java.util.Vector;
public class FindNextNumber {
/**
* @param args
*/
public static void main(String[] args) {
int nr = 123;
int [] nrA = convertNrToArray(nr);
System.out.println(arrToString(nrA));
while(true)
{
nrA = findNextNumber(nrA);
if(nrA == null)
{
System.out.println("Have null");
break;
}
System.out.println(arrToString(nrA));
}
nr = 4567;
nrA = convertNrToArray(nr);
System.out.println(arrToString(nrA));
while(true)
{
nrA = findNextNumber(nrA);
if(nrA == null)
{
System.out.println("Have null");
break;
}
System.out.println(arrToString(nrA));
}
// System.out.println(arrToString(nrA));
// nrA = findNextNumber(nrA);
// System.out.println(arrToString(nrA));
}
private static String arrToString(int[] nrA)
{
StringBuffer buf = new StringBuffer();
for(int i = nrA.length-1; i >= 0; i--)
buf.append(nrA[i] + ", ");
return new String(buf);
}
public static int [] convertNrToArray(int nr)
{
Vector <Integer> v = new Vector();
while(nr > 0)
{
v.add(nr % 10);
nr /= 10;
}
return vecToArr(v);
// Integer [] arr = new [v.size()];
// v.toArray(arr);
// return arr;
}
private static int[] vecToArr(Vector<Integer> v) {
int [] arr = new int[v.size()];
for(int i = 0; i < v.size(); i++)
{
arr[i] = v.get(i);
}
return arr;
}
public static int[] findNextNumber(int [] nr)
{
int powTenAt = 1;
while(powTenAt < nr.length)
{
//System.out.println("At position " + powTenAt);
// int getMinLarger = -1;
int minLargerIndex = -1;
int minPowTenAt = 0;
int curNr = nr[powTenAt];
while(minPowTenAt + 1 <= powTenAt)
{
//System.out.println("Testing " + minPowTenAt + ", " + nr[minPowTenAt]);
int curSmallerNr = nr[minPowTenAt];
if((curSmallerNr > curNr) && (minLargerIndex == -1 || curSmallerNr < nr[minLargerIndex]))
{
//getMinLarger = curSmallerNr;
minLargerIndex = minPowTenAt;
}
minPowTenAt++;
}
if(minLargerIndex != -1)
{
nr[powTenAt] = nr[minLargerIndex];
nr[minLargerIndex] = curNr;
sortTo(nr, powTenAt-1);
return nr;
}
powTenAt++;
}
return null;
}
private static void sortTo(int[] nr, int to)
{
//System.out.println(" Pre-sort: " + arrToString(nr));
int [] temp = new int[to+1];
for(int i = 0; i <= to; i++)
{
temp[i] = nr[i];
}
//System.out.println(" To-sort: " + arrToString(temp));
Arrays.sort(temp);
//System.out.println(" To-sort sorted: " + arrToString(temp));
for(int i = temp.length-1; i >= 0; i--)
{
nr[temp.length-1-i] = temp[i];
}
//System.out.println(" Post-sort: " + arrToString(nr));
}
}
This is O(N^2), if you wanted you could keep track of the previous digits in a priority queue, inserting at every step would be O(logN) so that would be O(N*log(N)) using the priority queue.
Of course there's also the sort, but again you could use the same priority queue to read the sorted digits out without having to resort.
Here is Neat and clean code:
#include <math.h>
#include <cstdlib>
#include <iostream>
int numberOfDigits(int a){
int count = 0;
while( a > 0){
a = a/10;
count++;
}
return count;
}
int nth_digit(int num, int pos){
return (int)(num / (int)pow(10.0, pos-1)) % 10;
}
bool ascending(int a, int b){
return (a < b);
}
bool decending(int a, int b){
return (a > b);
}
void insertion_sort(int *arr, int length, bool(*pf)(int, int)){
for(int range = 1; range < length; range++){
int x = range;
while(x > 0 && pf(arr[x],arr[x-1])){
int t = arr[x];
arr[x] = arr[x-1];
arr[x-1] = t;
--x;
}
}
}
inline void swap(int *arr, int x, int y){
int t = arr[x];
arr[x] = arr[y];
arr[y] = t;
}
int nextGreatest(int num){
int a = num;
// get length of number
int length = numberOfDigits(a);
int *arr = new int[length];
//separate digits and store into array
for(int i = length; i >= 1; i--){
arr[length - i] = nth_digit(a, i);
}
// check the pattern of digits following first digit, not including first digit
bool flag = true;
for(int i = 1; i < length-1; i++){
if(arr[i] < arr[i+1]){
flag = false;
break;
}
}
int beg;
int l;
if(flag){
/* if the pattern following the first digit is in decending order
convert to ascending order
for example 5 7 6 4 -----> 7 6 4 already in descending order following first digit 5
*/
insertion_sort(&arr[1], length-1, ascending);
beg = 0;
l = beg + 1;
while(arr[beg] > arr[l])
++l;
} else{
/* if the pattern following the first digit is not in decending order
convert the pattern following the second digit into descending order
for example 5 6 7 4 -------> since 6 7 4 not in descending order covert 7 4 in descending order
*/
insertion_sort(&arr[2], length-2, decending);
beg = 1;
l = beg;
while(arr[beg] < arr[l+1])
++l;
}
swap(arr, beg, l);
int result = 0;
for(int i = 0; i < length; i++){
result += arr[i] * (int)pow(10.0, length-i-1);
}
return result;
}
int main(){
int a = 5674;
std::cout << "Number of digits in " << a << " is " << numberOfDigits(a);
std::cout << "Next Greatest Number of 5764 " << nextGreatest(5764) << std::endl;
std::cout << "Next Greatest Number of 5674 " << nextGreatest(5674) << std::endl;
}
Division is costly.
/**
* @author hissar
*/
public class NextGreatest {
public String nextGreatestLinear (String str) {
if (str == null) return null;
char[] arr = str.toCharArray();
int k = -1;
for (int i = arr.length - 2; i >= 0; i--) {
if (arr[i] < arr[i+1]) {
k = i;
break;
}
}
if (k == -1) return null;
int l = -1;
for (int i = arr.length - 1; i > k; i--) {
if (arr[i] > arr[k]) {
l = i;
break;
}
}
if (l == -1) return null;
// Swap the required characters.
char tmp = arr[k];
arr[k] = arr[l];
arr[l] = tmp;
// reverse the remaining string.
int limit = (l-k) >> 1;
for (int i = 0; i < limit; i++) {
tmp = arr[k+i+1];
arr[k+i+1] = arr[l-i];
arr[l-i] = tmp;
}
return new String(arr);
}
public static void main(String[] args) {
String result = new NextGreatest ().nextGreatestLinear ("144765");
System.out.println(result == null ? "Not Possible" : result);
}
}
import java.util.Stack;
public class NextHigher {
public static void swap(int[] a, int m, int n) {
if (a[m] != a[n]) {
a[m] ^= a[n];
a[n] ^= a[m];
a[m] ^= a[n];
}
}
public static void findNextHigher(int[] a) {
if (a.length == 1) {
System.out.println("No next higher number");
return;
}
int smallest = Integer.MAX_VALUE;
int smallestIdx = -1;
int second = Integer.MAX_VALUE;
int secondIdx = -1;
int largest = -1;
int i = a.length - 1;
for (i = a.length - 1; i >= 0; i--) {
if (a[i] < smallest) {
second = smallest;
secondIdx = smallestIdx;
smallest = a[i];
smallestIdx = i;
} else if (a[i] < second) {
second = a[i];
secondIdx = i;
}
if (i < a.length - 1 && a[i] < a[i + 1]) {
largest = i + 1;
break;
}
}
if (i < 0) {
System.out.println("No next higher number");
return;
}
swap(a, largest, smallestIdx);
if (largest != secondIdx) {
swap(a, smallestIdx, secondIdx);
}
for (int e : a) {
System.out.print(e);
}
System.out.println();
}
public static int[] numToArray(int i) {
Stack<Integer> s = new Stack<Integer>();
do {
s.push(i % 10);
i = i / 10;
} while (i != 0);
int[] rtn = new int[s.size()];
i = 0;
for (i = 0; i < rtn.length; i++) {
rtn[i] = s.pop();
}
return rtn;
}
public static void main(String[] args) {
int num = 4765;
findNextHigher(numToArray(num));
num = 47653423;
findNextHigher(numToArray(num));
num = 4;
findNextHigher(numToArray(num));
num = 47;
findNextHigher(numToArray(num));
}
}
Sorry the previous code is wrong. This code should work. The algorithm is quite simple. Just find the first not in order pair, swap them, and sort the previous in order bits. No need to generate all permutations. It's O(log_10N)!, which is costly.
import java.util.Stack;
import java.util.Random;
public class NextHigher {
public static void swap(int[] a, int m, int n) {
if (a[m] != a[n]) {
a[m] ^= a[n];
a[n] ^= a[m];
a[m] ^= a[n];
}
}
public static int partition(int[] a, int l, int h) {
int i = l - 1;
int pivot = a[h];
for (int j = l; j <= h; j++) {
if (a[j] < pivot) {
i++;
swap(a, i, j);
}
}
swap(a, i + 1, h);
return i + 1;
}
public static void quickSort(int[] a, int l, int h) {
if (l < h) {
int p = partition(a, l, h);
quickSort(a, l, p - 1);
quickSort(a, p + 1, h);
}
}
public static void findNextHigher(int[] a) {
if (a.length == 1) {
System.out.println("No next higher number");
return;
}
int i = a.length - 1;
for (i = a.length - 1; i >= 0; i--) {
if (i < a.length - 1 && a[i] < a[i + 1]) {
break;
}
}
if (i < 0) {
System.out.println("No next higher number");
return;
}
swap(a, i, i + 1);
quickSort(a, i + 1, a.length - 1);
for (int e : a) {
System.out.print(e);
}
System.out.println();
}
public static int[] numToArray(int i) {
Stack<Integer> s = new Stack<Integer>();
do {
s.push(i % 10);
i = i / 10;
} while (i != 0);
int[] rtn = new int[s.size()];
i = 0;
for (i = 0; i < rtn.length; i++) {
rtn[i] = s.pop();
}
return rtn;
}
public static void main(String[] args) {
Random rnd = new Random();
for (int i = 0; i < 10; i++) {
int num = rnd.nextInt() & 0x7fffffff;
System.out.println(num);
findNextHigher(numToArray(num));
}
}
}
Find the first out of order element, swap it with the element in the previous in order bits that is higher than but closest to the first out of order element, and sort the previous in order bits.
import java.util.Stack;
import java.util.Random;
public class NextHigher {
public static void swap(int[] a, int m, int n) {
if (a[m] != a[n]) {
a[m] ^= a[n];
a[n] ^= a[m];
a[m] ^= a[n];
}
}
public static int partition(int[] a, int l, int h) {
int i = l - 1;
int pivot = a[h];
for (int j = l; j <= h; j++) {
if (a[j] < pivot) {
i++;
swap(a, i, j);
}
}
swap(a, i + 1, h);
return i + 1;
}
public static void quickSort(int[] a, int l, int h) {
if (l < h) {
int p = partition(a, l, h);
quickSort(a, l, p - 1);
quickSort(a, p + 1, h);
}
}
public static void findNextHigher(int[] a) {
if (a.length == 1) {
System.out.println("No next higher number");
return;
}
int i = a.length - 1;
for (i = a.length - 1; i >= 0; i--) {
if (i < a.length - 1 && a[i] < a[i + 1]) {
break;
}
}
if (i < 0) {
System.out.println("No next higher number");
return;
}
int diff = Integer.MAX_VALUE;
int idx = 0;
for (int j = i + 1; j < a.length; j++) {
if (a[j] - a[i] > 0 && a[j] - a[i] < diff) {
diff = a[j] - a[i];
idx = j;
}
}
swap(a, idx, i);
quickSort(a, i + 1, a.length - 1);
for (int e : a) {
System.out.print(e);
}
System.out.println();
}
public static int[] numToArray(int i) {
Stack<Integer> s = new Stack<Integer>();
do {
s.push(i % 10);
i = i / 10;
} while (i != 0);
int[] rtn = new int[s.size()];
i = 0;
for (i = 0; i < rtn.length; i++) {
rtn[i] = s.pop();
}
return rtn;
}
public static void main(String[] args) {
Random rnd = new Random();
for (int i = 0; i < 10; i++) {
int num = rnd.nextInt() & 0x7fffffff;
// int num = 960757364;
System.out.println(num);
findNextHigher(numToArray(num));
}
}
}
public static int getSecondLargestNumber(int num) {
int sum = 0;
int d, i=0;
int len = (new String(num+"")).length();
int a[] = new int[len];
while(num > 1) {
d = num%10;
num = num/10;
a[i] = d;
i++;
}
Arrays.sort(a);
for(int j=0; j<a.length; j++) {
if (j == 0)
sum += a[1]*Math.pow(10, 0);
else if (j==1)
sum += a[0]*Math.pow(10, 1);
else
sum += a[j]*Math.pow(10, j);
}
return sum;
}
This seems to be a phone interview question so talking a lot of code over the phone is not that great.
What about trying a simpler solution?
Add to the original number one and verify if the resulted number has all the digits from the original number.
If yes, the new number is the solution, if not repeat.
int GetGreatestNumber(int x) {
int y = x;
do {
y = y + 1;
} while (!HasAllDigits(y, x))
return y;
}
import java.util.ArrayList;
import java.util.Collections;
public class Amazon {
public static void main(String[] arg)
{
int[] arr={5,4,7,6,3};
int i,j = 0;
boolean swap=false;
int[] pos=new int[2];
ArrayList<Integer> newarr=new ArrayList<Integer>();
for(i=arr.length-1;i>0;i--)
{
for(j=i-1;j>=0;j--)
{
if(arr[i]>arr[j])
{
swap(arr,i,j);
swap=true;
pos[0]=i;
pos[1]=j;
break;
}
else if(swap)
break;
}
if(swap)
{
break;
}
}
if(pos[0]-pos[1]==1|pos[0]-pos[1]==-1)
{
for(int k=0;k<arr.length;k++)
System.out.print(arr[k]);
}
else
{
for(int k=pos[1]+1;k<arr.length;k++)
{
newarr.add(arr[k]);
}
System.out.println(pos[0]);
Collections.sort(newarr);
for(int k=0;k<=pos[1];k++)
System.out.print(arr[k]);
for(int k=0;k<arr.length-pos[1]-1;k++)
System.out.print(newarr.get(k));
}
}
private static void swap(int[] arr,int n,int m)
{
int temp=arr[m];
arr[m]=arr[n];
arr[n]=temp;
}
}
It is the same logic to find the next permutation of string. Please check the wikipedia (en.wikipedia.org/wiki/Permutation) and section: Generation in lexicographic order:
- chenlc626 March 24, 2013Generation in lexicographic order
There are many ways to systematically generate all permutations of a given sequence[citation needed]. One classical algorithm, which is both simple and flexible, is based on finding the next permutation in lexicographic ordering, if it exists. It can handle repeated values, for which case it generates the distinct multiset permutations each once. Even for ordinary permutations it is significantly more efficient than generating values for the Lehmer code in lexicographic order (possibly using the factorial number system) and converting those to permutations. To use it, one starts by sorting the sequence in (weakly) increasing order (which gives its lexicographically minimal permutation), and then repeats advancing to the next permutation as long as one is found. The method goes back to Narayana Pandita in 14th century India, and has been frequently rediscovered ever since.[12]
The following algorithm generates the next permutation lexicographically after a given permutation. It changes the given permutation in-place.
1. Find the largest index k such that a[k] < a[k + 1]. If no such index exists, the permutation is the last permutation.
2. Find the largest index l such that a[k] < a[l]. Since k + 1 is such an index, l is well defined and satisfies k < l.
3. Swap a[k] with a[l].
4. Reverse the sequence from a[k + 1] up to and including the final element a[n].
After step 1, one knows that all of the elements strictly after position k form a weakly decreasing sequence, so no permutation of these elements will make it advance in lexicographic order; to advance one must increase a[k]. Step 2 finds the smallest value a[l] to replace a[k] by, and swapping them in step 3 leaves the sequence after position k in weakly decreasing order. Reversing this sequence in step 4 then produces its lexicographically minimal permutation, and the lexicographic successor of the initial state for the whole sequence.