Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
this is about generating permutations in lexicographical order:
use std::next_permutation() for that ))
I solved it in a different way. If I remember correctly the space complexity blows up if we try to compute the permutations.
* The number is actually provided as an array of chars.
* Take an array of length 10. to hash the rightmost occurance of each digit (0-9).
* Process the array from right to left.
* If you encounter a digit for which there is a higher digit to its right, Find the rightmost occurance of it (from the hash table) and swap the elements.
* Sort the numbers to the right of the element you just swapped.
public static int getNextNumberWithSameDigits(int n){
char[] digits = Integer.toString(n).toCharArray();
for (int i = digits.length-1; i>0; i--){
for(int j = i-1; j>=0; j--){
if (digits[i] < digits[j]){
// swap and return
char tmp = digits[i];
digits[i] = digits[j];
digits[j] = tmp;
return Integer.parseInt(new String(digits));
}
}
}
return -1;
}
This doesn't work in all cases, take for example 2531. With your code it would return 3521, where correct would be 3125. The correct solution would rotate subarray [i..j] left until a[i] moved to a[j] position:
for (int i = digits.length-1; i>0; --i) {
for (int j = i-1; j>=0; --j) {
if (digits[i] > digits[j]) {
// rotate subarray [j..digits.length-1] right
// digits.length - i times
for (int k = 0; k < digits.length - i; ++k) {
char t = digits[digits.length-1];
for (int l = digits.length-1; l > j; --l) {
digits[l] = digits[l-1];
}
digits[j] = t;
}
return Integer.parseInt(new String(digits));
}
}
}
Some diff idea,
Firstly, we need use Xiaochao's way to swap the data.
then, I think we need to sort the digits behind swap index.
e.g. original digital is 34951,
1. from right to left, scan the digital,
a. 1 is less all digits
b. 5 is less 9, but greater than 4, so current the i is 3, and j is 1
c. swap digits[i] and digits[j], not the digits is 35941,
2. sort from the digits[i+1] to digits[length - 1], here it is 941
So, the answer is 35149
@yaya your idea is correct: this algorithm just generates the permutations in lexicographical order. But we also have to take care of duplicate digits. The code is below:
// lexicographically permutes an array of n elements
bool next(int *x, int n) {
// find the rightmost x[i] which is smaller then x[i+1]
int i = n - 1;
do { i--; } while(x[i] >= x[i+1]);
if(i < 0)
return false; // all permutations enumerated
// now we have:
// x[i] < x[i+1] > x[i+2] > ... > x[n-2] > x[n-1]
// find rightmost j such that x[i] < x[j]
int j = n - 1;
while(x[i] >= x[j]) j--;
// we have: x[i] < x[j] where j = i+1 .. n-1
swap(x[i], x[j]);
// now elements x[i+1].. x[n-1] form a falling sequence => reverse it
int r = n - 1, s = i + 1;
while(s < r) {
swap(x[s], x[r]);
s++, r--;
}
return true;
}
// computes the next number after 'N' formed from the same digits
int next_number(int N, int *x, int n_digits) {
int i;
for(i = n_digits - 1; N != 0; i--) {
x[i] = N % 10, N /= 10; // convert the number to an array of digits
}
if(!next(x, n_digits)) // compute the next permutation
return 0; // all numbers enumerated
for(i = 0, N = 0; i < n_digits; i++) { // convert back to a number
N = N*10 + x[i];
}
return N;
}
int main() {
int n = 10; // max no of digits
int *x = new int[n+1], *y = x + 1;
x[0] = n+1; // sentinel
int N = 11553, n_digits = 5;
while(1) {
printf("next: %d\n", N);
N = next_number(N, x, n_digits);
if(N == 0) break;
}
delete []x;
return 1;
}
output:
next: 11553
next: 13155
next: 13515
next: 13551
next: 15135
next: 15153
next: 15315
next: 15351
next: 15513
next: 15531
next: 31155
next: 31515
next: 31551
next: 35115
next: 35151
next: 35511
next: 51135
next: 51153
next: 51315
next: 51351
next: 51513
next: 51531
next: 53115
next: 53151
next: 53511
next: 55113
next: 55131
next: 55311
1. Start moving pointer from right to left until the sequence traversal is decreasing.
Eg. N=142521, pointer stops at '2'521.
2. Swap the digit so found with LUB-digit(least upper bound digit) among right digits.
Eg. SWAP '2'521-->'5'221
3. Sort the digits which are to pointer's right
Eg. '5'221-->'5'122
1. Store the digits in the given number in an array. unit's place digit goes to
arr[0], ten's place digit goes to arr[1] so on... set a flag bool possible =0.
2. Scan the array from arr[0] till end
a. if (arr[i]>arr[i+1]) swap arr[i] and arr[i+1]; possible =1; break the loop
3. if (possible == 0) print ("Given number is the maximum number")
return (same number)
else
{
sort the array in descending order from arr[0] to arr[i];
reconstruct the number from the modified array like 1*arr[0]+10*arr[1]+..so on;
return (new number);
}
I read through all these steps . its interesting. Any idea on the below method ?
1)Convert the number to character array
2) Increment the given number by 1
3) Convert the incremented number to character array and compare each and every character with the given number which is in character array. If all the numbers are present . return that number .
I may be wrong, just a thought. suggestions are most welcome
Here:
- Varun February 14, 2013Careercup question?id=11543949