Google Interview Question
Software EngineersCountry: United States
Interview Type: Phone Interview
Suppose if we have to find the number which is just greater than B and also made up from digits of A?
Hi, Sachin. You raised a very good question. I came up with a greedy algorithm as follows, and I used string to represent a large number. Please check me.
string solve(const string &a, const string &b) {
if (a.size() < b.size())
return "";
if (a.size() > b.size()) {
string ans = a;
sort(ans.begin(), ans.end());
return move(ans);
}
int st[256] = {0};
for (char c : a)
++st[c];
string ans;
ans.reserve(b.size());
for (char c : b) {
if (st[c] > 0) {
ans.push_back(c);
--st[c];
}
else {
char x = c;
while (++x <= '9' && st[x] == 0);
if (x <= '9') {
ans.push_back(x);
--st[x];
for (char y = '0'; y <= '9'; ++y) {
while (st[y]-- > 0)
ans.push_back(y);
}
}
else {
ans = "";
}
break;
}
}
return move(ans);
}
I am thinking of the following approach.I m making the assumptions that the digits in A and B can be represented using an array and n is the number of digits.Instead of sorting all the digits in A ,Can we just do the very first pass in bubble sort for A, this will guarantee that the largest in A would be found at the end of the first pass.
That is A : 2518, Now compare A[n-1] with B[0], if its greater create the number using this digit as the first digit.
Assumption: Both A and B has same number of digits
1.) Make an array with 10 entries {0,9}
2.) Parse through A and increment count of each digit in array as it occurs
3.) Start parsing through B , let say first digit is D1 , try to find the digit larger than D1 from array made in 1 , this at max is 9 steps (so O(1) ) .
If there is a digit then make that the current digit of larger number and rearrange remaining digits from array in step 1
If there is no digit greater than
check if there is a digit equal to D1 ,
->decrement count for array formed in step 1
-> for new digit first digit is D1
else not possible
Similar to above, but without an optimization that once you create your digit array from A, you have your highest number
O(N) to parse through A + O(1) memory for digit array + O(1) time to iterate through digit array. O(N) time and O(1) memory.
// Returns a number one can make from the digits in A which is greater than B.
// Else, return -1
int numberGreatThanB(int A, int B) {
// Parse A into digit array
vector<int> digitArray(10, 0);
int digit = A % 10;
while(A) {
++digitArray[digit];
A /= 10;
digit = A % 10;
}
// We now have our digit array. Iterate through it backwards to create max number
// possible with digits from A
int maxNumberFromA = 0;
for(int i=9; i>=0; --i) {
while(digitArray[i]--) {
maxNumberFromA *= 10;
maxNumberFromA += digitArray[i];
}
}
return (maxNumberFromA > B) ? maxNumberFromA : -1;
}
#!/usr/bin/perl
# Print usage and exit if two numbers are not passed.
die "Usage: $0 number1 number2\n" if @ARGV != 2;
my $num1 = $ARGV[0];
my $num2 = $ARGV[1];
# We are going to compare the digits of each number, so split them.
my(@arr_num2) = split //, $num2;
my(@asc_arr_num1) = sort split //, $num1;
my(@desc_arr_num1) = sort {$b <=> $a} split //, $num1;
#print "@desc_arr_num1\n@asc_arr_num1\n";
#
# Of all the numbers, that can be formed from the digits of the first number, which are higher than
# second number, we will out of the lowest of them all.
#
# We'll make two arrays from the digits of first numner.
# We'll compare the digits from the array of digits from first numner in descending order with
# the digits of second number. When the digit from first number exceeds the corresponding digit
# from second number, we'll find the lowest combination of the remaining digits of first number
# and append them. For that we'll use the second array that we created from digits of first number
# in ascending order.
#
# If the resulting number at the end of the loop is lower/equal than the second number, that means
# no number can be formed from digits of first number which is bigger than second number.
#
for (my $i=0; $i<@desc_arr_num1; $i++)
{
$result .= sprintf "%d", $desc_arr_num1[$i];
if ($desc_arr_num1[$i] > $arr_num2[$i] )
{
for (my $k=0; $k<@asc_arr_num1-$i-1; $k++)
{
$result .= sprintf "%d", $asc_arr_num1[$k];
}
last;
}
}
if ($result > $num2)
{
print "$result\n";
}
else
{
print "Sorry, but no number can be formed from digits of $num1 which is bigger than $num2.\n";
}
$ careercup_5165229530939392.pl 5281 7443
8125
$ careercup_5165229530939392.pl 7442 7443
Sorry, but no number can be formed from digits of 7442 which is bigger than 7443.
$ careercup_5165229530939392.pl 123 7443
Sorry, but no number can be formed from digits of 123 which is bigger than 7443.
None of you guys have discussed about how to break an int into individual numbers. I have the following code:
int AsBiggestNumber = 0;
int pos = 0;
int count = 0;
vector<int> numbers;
while (true) {
int remainder = A%10;
if (AsBiggestNumber<remainder) {
AsBiggestNumber = remainder;
pos = count;
}
if (remainder==0)
break;
numbers.push_back(remainder);
count++;
A=A/10;
}
public class Solution{
public static Set<Integer> set = new HashSet<Integer>();
public static void main(String [] args){
System.out.println("COrrect");
int a = 456;
int b = 789;
int sol = getC(a,b,a);
System.out.println("C calue is " + String.valueOf(sol));
}
public static int getSize(int num){
int temp = num;
int noOFDigits = 0;
while(temp !=0){
temp= temp/10;
noOFDigits++;
}
int a =1;
for(int i=0 ; i < noOFDigits-1 ;i++){
a = a* 10;
}
return a;
}
public static int getC(int a, int b, int original){
if(a > b || set.contains(new Integer(a))){
return a;
}
set.add(new Integer(a));
int temp = a;
int digit = 0;
int size = 1;
digit = temp % 10;
size = getSize(temp);
temp = temp/10;
temp = (digit * (size)) + temp;
System.out.println("New num :" + String.valueOf(temp));
return getC(temp, b, original);
}
}
public class Solution{
public static Set<Integer> set = new HashSet<Integer>();
public static void main(String [] args){
System.out.println("COrrect");
int a = 456;
int b = 789;
int sol = getC(a,b,a);
System.out.println("C calue is " + String.valueOf(sol));
}
public static int getSize(int num){
int temp = num;
int noOFDigits = 0;
while(temp !=0){
temp= temp/10;
noOFDigits++;
}
int a =1;
for(int i=0 ; i < noOFDigits-1 ;i++){
a = a* 10;
}
return a;
}
public static int getC(int a, int b, int original){
if(a > b || set.contains(new Integer(a))){
return a;
}
set.add(new Integer(a));
int temp = a;
int digit = 0;
int size = 1;
digit = temp % 10;
size = getSize(temp);
temp = temp/10;
temp = (digit * (size)) + temp;
System.out.println("New num :" + String.valueOf(temp));
return getC(temp, b, original);
}
}
/*
This is a generalized problem for next higher permutation.
If A and B have same digits, this it is the special case of
next higher permutation problem.
Strategy:
---------
1. Count all digits of A in a Hash (mA),
we need these digits to create new number.
2. Try matching B digits with A-map(mA) from MSB->towards->LSB, because
we want next higher permutation. Therefore we want to keep MSB digits
as much same as possible.
3. While doing this, we can have two cases.
3a. case#1: At index i, B differs from A. Then try to get a digit from
mA which is just greater than B[i]. If found, place it in C[i]
if not found, we have to go left until i==0
3b. case#2: We have exhausted B and A. This means, A and B are permutations.
In this case also, we have to go left.
4. The only difference between case1 and 2 is, in case#1, [0,i-1] digits of
A and B are same but i differs, but for case#2, [0,i] digits are same. We need
to know this because, while left tracking, we need to give back digits to mA as necessary.
5. If (3) terminates at some i>=0, then copy B[0..i-1] => C[0...i-1]
6. Copy rest of digits from mA to C[i+1....N-1] in increasing order.
7. If i=-1, then no solution.
Complexity = O(n) [n = number of digits]
*/
#include <iostream>
#include <stdio.h>
using namespace std;
#define D_(c) ((int)c-(int)'0')
#define C_(i) ((char)(i+(int)'0'))
int main() {
freopen("input.txt", "r", stdin);
char A[100],B[100],C[100],mA[10];
scanf("%s", A);
scanf("%s", B);
for(int i=0; i<10; i++) mA[i] = 0;
int sA=0;
while(A[sA] != '\0' && A[sA] != '\n') {
mA[D_(A[sA])]++;
sA++;
}
int sB=0;
while(B[sB] != '\0' && B[sB] != '\n') sB++;
if(sA != sB) {
cout << "A & B size mismatch. No solution!!.\n";
return 0;
}
int N = sA;
int i=0;
bool match;
for(i=0; i<N; i++){
match = false;
if(mA[D_(B[i])]) {
match=true;
mA[D_(B[i])]--;
continue;
}
break;
}
if(i==N) i--;
while(i>=0){
int j;
for(j=D_(B[i])+1; j<10; j++) {
if(mA[j]) {
if(match) mA[D_(B[i])]++;
C[i] = C_(j);
mA[j]--;
break;
}
}
if(j == 10) {
if(match) mA[D_(B[i])]++;
i--;
match=true;
continue;
}
for(int k=0; k<i; k++) C[k] = B[k];
int p=9;
for(int k=N-1; k>i; k--) {
while(mA[p]==0)p--;
C[k]=C_(p);
mA[p]--;
}
break;
}
if(i<0) {
cout << "No solution\n";
return 0;
}
C[N] = '\0';
cout << C;
return 0;
}
/*
This is a generalized problem for next higher permutation.
If A and B have same digits, this it is the special case of
next higher permutation problem.
Strategy:
---------
1. Count all digits of A in a Hash (mA),
we need these digits to create new number.
2. Try matching B digits with A-map(mA) from MSB->towards->LSB, because
we want next higher permutation. Therefore we want to keep MSB digits
as much same as possible.
3. While doing this, we can have two cases.
3a. case#1: At index i, B differs from A. Then try to get a digit from
mA which is just greater than B[i]. If found, place it in C[i]
if not found, we have to go left until i==0
3b. case#2: We have exhausted B and A. This means, A and B are permutations.
In this case also, we have to go left.
4. The only difference between case1 and 2 is, in case#1, [0,i-1] digits of
A and B are same but i differs, but for case#2, [0,i] digits are same. We need
to know this because, while left tracking, we need to give back digits to mA as necessary.
5. If (3) terminates at some i>=0, then copy B[0..i-1] => C[0...i-1]
6. Copy rest of digits from mA to C[i+1....N-1] in increasing order.
7. If i=-1, then no solution.
Complexity = O(n) [n = number of digits]
*/
#include <iostream>
#include <stdio.h>
using namespace std;
#define D_(c) ((int)c-(int)'0')
#define C_(i) ((char)(i+(int)'0'))
int main() {
freopen("input.txt", "r", stdin);
char A[100],B[100],C[100],mA[10];
scanf("%s", A);
scanf("%s", B);
for(int i=0; i<10; i++) mA[i] = 0;
int sA=0;
while(A[sA] != '\0' && A[sA] != '\n') {
mA[D_(A[sA])]++;
sA++;
}
int sB=0;
while(B[sB] != '\0' && B[sB] != '\n') sB++;
if(sA != sB) {
cout << "A & B size mismatch. No solution!!.\n";
return 0;
}
int N = sA;
int i=0;
bool match;
for(i=0; i<N; i++){
match = false;
if(mA[D_(B[i])]) {
match=true;
mA[D_(B[i])]--;
continue;
}
break;
}
if(i==N) i--;
while(i>=0){
int j;
for(j=D_(B[i])+1; j<10; j++) {
if(mA[j]) {
if(match) mA[D_(B[i])]++;
C[i] = C_(j);
mA[j]--;
break;
}
}
if(j == 10) {
if(match) mA[D_(B[i])]++;
i--;
match=true;
continue;
}
for(int k=0; k<i; k++) C[k] = B[k];
int p=9;
for(int k=N-1; k>i; k--) {
while(mA[p]==0)p--;
C[k]=C_(p);
mA[p]--;
}
break;
}
if(i<0) {
cout << "No solution\n";
return 0;
}
C[N] = '\0';
cout << C;
return 0;
}
public int createBiggest(int a, int b) throws Exception {
int[] aDigitsInArray = createDigitArrayFromInt(a);
int[] bDigitsInArray = createDigitArrayFromInt(b);
if (aDigitsInArray.length < bDigitsInArray.length) {
throw new Exception("No solution");
}
Arrays.sort(aDigitsInArray);
if (aDigitsInArray.length > bDigitsInArray.length) {
return createIntFromIntArray(aDigitsInArray);
}
outer:
for (int i = 0; i < bDigitsInArray.length; i++) {
for (int j = i; j < aDigitsInArray.length; ) {
if (aDigitsInArray[j] < bDigitsInArray[i]) {
j++;
if (j == aDigitsInArray.length) {
return -1;
}
} else if (aDigitsInArray[j] == bDigitsInArray[i]) {
swap(aDigitsInArray, i, j);
break;
} else {
swap(aDigitsInArray, i, j);
if (i + 1 < bDigitsInArray.length) {
sortFrom(aDigitsInArray, i + 1);
return createIntFromIntArray(aDigitsInArray);
}
break outer;
}
}
}
return -1;
}
private void sortFrom(int[] source, int fromIndex) {
int newArrLen = source.length - fromIndex;
int[] newArr = new int[newArrLen];
System.arraycopy(source, fromIndex, newArr, 0, newArrLen);
Arrays.sort(newArr);
int index = 0;
for (int i = fromIndex; i < source.length; i++) {
source[i] = newArr[index++];
}
}
private int[] createDigitArrayFromInt(int val) {
List<Integer> values = new LinkedList<>();
while (val != 0) {
values.add(val % 10);
val /= 10;
}
Collections.reverse(values);
return values.stream().mapToInt(i -> i).toArray();
}
private int createIntFromIntArray(int[] arr) {
int result = 0;
for (int i = 0; i < arr.length; i++) {
result += Math.pow(10, i) * arr[arr.length - (i + 1)];
}
return result;
}
private void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
Based on previous submitted answers I code this, the sort of the elements is O(n)
Create an array of ten elements, count the numbers in A, the array gives us a natural sort then create the new number based on the array-count
// Sort the numbers in O(n)
public int CreateNumber(int a, int b)
{
int[] arr = new int[10];
int index = 0;
while (a > 0)
{
index = a % 10;
a = a / 10;
arr[index]++;
}
index = arr.Length-1;
int result = 0;
while (index >= 0)
{
if (arr[index] == 0)
{
index--;
continue;
}
result = result * 10 + index;
arr[index]--;
}
return result > b ? result : -1;
}
I'd just sort the digits of A into descending order. Either that's greater than B or nothing will be.
- Dot August 21, 2015(Sorry mistyped while not signed in above. Hopefully previous one gets deleted.)