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

- Dot August 21, 2015 | Flag Reply
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?

- Sachin August 25, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- malinbupt September 25, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous October 14, 2015 | Flag
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

- smarthbehl August 21, 2015 | Flag Reply
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.

- dot August 21, 2015 | Flag Reply
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;
}

- Josh August 21, 2015 | Flag Reply
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). - divm01986 August 21, 2015 | Flag Reply
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[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.

- rajeev@udhar.com August 22, 2015 | Flag Reply
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;
  }

- thewhatwhat August 22, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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)

- thewhatwhat August 22, 2015 | Flag
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;
}
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);
}

}

- Martin August 22, 2015 | Flag Reply
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;
}
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);
}

}

- Martin Dureja August 22, 2015 | Flag Reply
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]
            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;
}

- Anonymous August 23, 2015 | Flag Reply
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]
            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;
}

- diba.bec August 23, 2015 | Flag Reply
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

- VinceBarresi August 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Ertuğrul Çetin September 21, 2015 | Flag Reply
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.

- Prob September 23, 2015 | Flag Reply
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[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;
}

- hnatsu May 17, 2016 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More