## Google Interview Question for Software Engineers

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
7
of 9 vote

I'd just sort the digits of A into descending order. Either that's greater than B or nothing will be.

(Sorry mistyped while not signed in above. Hopefully previous one gets deleted.)

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

Suppose if we have to find the number which is just greater than B and also made up from digits of A?

Comment hidden because of low score. Click to expand.
0

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 = {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);
}``````

Comment hidden because of low score. Click to expand.
0

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, if its greater create the number using this digit as the first digit.

Comment hidden because of low score. Click to expand.
2
of 4 vote

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

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

I'd just sort the digits of A in ascending order. Either that's greater than B or nothing will be.

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

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote
{{{/**From the example given, it looks like we have to find the smallest number that can be made from A which is larger then B, so that's the assumption I went with**/ public class NumberSvc {{{ public int createLargerNumber(int[] a, int[] b) throws NullPointerException, InvalidInputException { if(a==null||b==null) { throw new NullPointerException(); } if(b.length<a.length) { throw new InvalidInputException(); } } a=Arrays.sort(a);//Arrange all the digits in ascending order int i=0; while(true) { if(a[i]>b[i]) { break; } if(a[i]<b[i]) { int tmp=a[i]; int j=i+1; while(a[j]<b[i]) { j++; } a[i]=a[j]; a[j]=tmp; } i++; } return a; }}} //Running time complexity in worst case: O(nlogn) //Space complexity is: O(n).
Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#!/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;
my \$num2 = \$ARGV;

# 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.

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

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;
}``````

Comment hidden because of low score. Click to expand.
0

Now sort the vector and make a number starting from the end of the vector. If A's length is a then time is O(aLNa) for the sort and others are O(a)

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

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;
}

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);
}

}

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

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;
}

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);
}

}

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

``````/*
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]
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,B,C,mA;
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;
}``````

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

``````/*
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]
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,B,C,mA;
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;
}``````

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

Simple ruby solution

``````def create_c a, b
c = a.to_s.split('').sort.reverse.join.to_i
c < b ? nil : c
end``````

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

``````public int createBiggest(int a, int b) throws Exception {

int[] bDigitsInArray = createDigitArrayFromInt(b);

throw new Exception("No solution");
}

}

outer:
for (int i = 0; i < bDigitsInArray.length; i++) {

for (int j = i; j < aDigitsInArray.length; ) {

j++;

return -1;
}

} else if (aDigitsInArray[j] == bDigitsInArray[i]) {

break;

} else {

if (i + 1 < bDigitsInArray.length) {

}

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) {

while (val != 0) {

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;
}``````

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

Does this question insist that the answer is not A? ("create a new number")

If A already *is* the max arrangement of letters and the above is true, a "swapLowestDifferentDigits" function is required.

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

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;

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;
}``````

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.

### 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.