## Google Interview Question for Applications Developers

• 1
of 1 vote

Country: United States
Interview Type: Phone Interview

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

1. First pass calculate the product P of all the numbers in array A
2. Second pass recreate the array A[i] = P / A[i]

As the interviewer has indicated the product can be very big, if the numbers in the array are big and/or the array length is big. Some languages support BigInteger operations, like Python and I think Java also has BigInteger class. If using the programming language provided implementation is not an option, then you'll need to implement your own "BigInteger" class. You need to only implement the constructor, which will take the number and convert it to string and then two methods for multiplication and division. C++ version will probably will overload the multiplication(*) and division(/) operators.

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

C++ also has extremely fast big integer libraries as one could imagine. I've used gmp which has ugly syntax but works very well.

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

Guys , I beg to differ. What you posted is only the beginning of a solution , but not a real algorithm.

Think about it, assuming the numbers all have exactly 10 digits , and there are N numbers in the array , to compute the product P of all the array numbers has the following cost:

Cost(product) = Sum(Cost( a number with >= 10*i digits * a number with 10 digits ) )

Assuming one uses an inefficient method to compute a*b , meaning the traditional n^2 algorithm , then Cost( a number with 10*i digits * a number with 10 digits ) = 11 * i

Considering this it is obvious that the cost of the product algorithm is O(n^2).

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

Karatsuba multiplication

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

Exactly. I'm pretty sure this is what the interviewer wanted to hear.

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

I think the Actual question will have one more constraint that you can not use division operator.

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

``````int n = a.length;
int[] b = new int[n];

b = 1;
for(int i = 1; i < n; i++) {
int prev = i-1;
b[i] = a[prev] * b[prev];
}

int temp = a[n-1];
int temp2;
a[n-1] = 1;
for(int i = n - 2; i >= 0; i--) {
temp2 = a[i];
a[i] = a[i+1] * temp;
temp = temp2;
}

for(int i = 0; i < n; i++) {
a[i] = a[i] * b[i]
}

// a is the result``````

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

two arrays would be used: prev and post, prev[i] = a[i]*prev[i-1]; post[i]=a[i]*post[i+1], then result[i]=prev[i-1]*post[i+1]

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

``````package com.careercup.google;

import java.util.ArrayList;

class BigIntTest
{
static class BigInt
{
public BigInt(int[] _digits)
{
for(int d : _digits)
{
}
}

public BigInt multiply(BigInt b)
{
int size = digits.size() + b.digits.size() + 1;
int[] finalProduct = new int[size];

for (int i=0; i<digits.size(); i++)
{
int carry = 0;
int[] intermediateProduct = new int[size];
for (int j=0; j<b.digits.size(); j++)
{
int tmp = (digits.get(i) * b.digits.get(j) + carry);
carry = tmp/10;
intermediateProduct[j] = tmp % 10;
}

int carry1 = 0;
int j = 0;
for (j=0; j<b.digits.size()+1; j++)
{
int tmp = finalProduct[j+i] + intermediateProduct[j] + carry1;
carry1 = tmp/10;
finalProduct[j+i] = tmp%10;
}

if (carry != 0)
{
finalProduct[j+i-1] += carry;
}
}

return new BigInt(finalProduct);
}

public int devide(BigInt b)
{
int result = 0;

while (!zero(this))
{
for (int i=0; i<b.digits.size(); i++)
{
if (digits.get(i) >= b.digits.get(i))
{
digits.set(i, digits.get(i) - b.digits.get(i));
}
else
{
digits.set(i, digits.get(i) + 10 - b.digits.get(i));
int j=i+1;
while (digits.get(j) == 0)
{
digits.set(j, 9);
j++;
}
digits.set(j, digits.get(j) - 1);
}
}
result++;
}

return result;
}

public String toString()
{
String s = new String();
while(0 == digits.get(digits.size()-1))
{
digits.remove(digits.size() -1);
}

for (int i= digits.size()-1; i>=0; i--)
{
s += digits.get(i).toString();
}
return s;
}

private Boolean zero(BigInt a)
{
for (Integer d : a.digits)
{
if (d != 0)
{
return false;
}
}

return true;
}

public ArrayList<Integer> digits = new ArrayList<Integer>();
}

public static void main (String[] args)
{
//2765
BigInt a = new BigInt(new int[]{5,6,7,2});
BigInt b = new BigInt(new int[]{2});
System.out.println(a.multiply(b));
System.out.print(a.multiply(b).devide(b));
}
}``````

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

//
int a[N],b[N];
int i,j,tmp,tot = 1,index=0;

for (i=0; i < N; i++)
{
tmp = a[i];
a[i] = 1;
tot = 0
for (j=0; j<N;j++)
{
tot = tot * a[j];
}
b[index++] = tot;
a[i] = tmp;
}
// complexity O(n^2)

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

``````int a[N],b[N];
int i,tot = 1;

for (i=0; i < N; i++)
{
tot = tot * a[i];
}
for (i=0; i<N; i++)
{
b[i] = tot / a[i];
}

}
// complexity O(2N)``````

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

Wait, I'm confused about this question. Why is it hard? Can we just go through an array, multiply all the numbers together (except for the selected cell), and then go through the array again, setting all the cells except for the selected cell to the product we just found?

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

No overflow
void fillproduct(vector<int> &num)
{
if (num.size() == 0)
return;
if (num.size() == 1)
{
num = 1;
return;
}

int cur = 1;
int last = num[num.size() -1];
for(int i=0; i<num.size(); i++)
{
int tmp = num[i];
num[i] = cur;
cur *= tmp;
}

cur = num[num.size() -1]/ num[num.size() -2];
for(int i=num.size() - 2; i>= 0; i--)
{
int tmp = i == 0 ? 1 : num[i]/ num[i-1];
num[i] *= last;
last *= cur;
cur = tmp;
}
}

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

l = [3,4,1,5,6,7]
pre = *len(l)
pos = *len(l)
for index, i in enumerate(l):
if index>0:
pre[index] = pre[index-1] * l[index-1]

index = len(l)-1
ma = index
while(index>=0):
if index<ma:
pos[index] = pos[index+1] * l[index+1]
index = index -1
print pre
print pos

for index, i in enumerate(l):
print pre[index] * pos[index] ,

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

Fairly simple question. Previous poster gave the psuedo:

@oOZz
1. First pass calculate the product P of all the numbers in array A
2. Second pass recreate the array A[i] = P / A[i]

NOTE: that you do have to make a special adjustment for the first element. You set your accumulator equal to the beginning element, and then loop starting with the 2nd element. Proper pseudo would read:

1. Set accumulator variable equal to first element in the array
2. Start with 2nd element in array and accumulate the product to the end of the array
3. Start at beginning of the array and assign to each element: accumulator/element value to the end of the array

Final consideration: As the numbers get larger, you would need to implement BigInteger or use long, or possibly another customer data type to capture the massive values that can accumulate. This algorithm runs on O(n) time and O(n) space complexity.

Here is a simple implementation of the actual code.

``````int[] a = {5,4,8,6,2,5,1,3,9,11};
int product = a;

for(int i = 1; i < a.length; i++){
product *= a[i];
}

for(int i = 0; i < a.length; i++){
a[i] = product/a[i];
}

for(int i = 0; i < a.length; i++){
System.out.print(a[i] + " ");
}``````

Output of above example:
570240 712800 356400 475200 1425600 570240 2851200 950400 316800 259200

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

The code you posted provides absolutely no improvement to my solution. Starting your loop from 0 or 1 won't change the complexity, it's still O(n). Besides you've added a third loop two print the values, whereas you could have done that in the second loop.

The main point of this question is the BigInteger part and implementation of multiplication and division for the BigInteger. The code you've provided does not address the overflow condition and therefore it's incomplete and incorrect.

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

Hi oOZz,

I never said I improved on your solution, I just actually produced a coded solution and clarified the pseudo to account for the fringe case that is not obvious until a practical implementation is attempted. As for the 3rd loop for printing, I segmented that out so that it is not part of the actual 'working code', but you are correct that it could have been accomplished during the 2nd loop.

To your last point, I did not use code to implement BigInteger (neither did you sir...), but I did include an explanation of 3 different data types to address this depending on the situation. Your suggestion that my solution is incomplete depends on whether you accept my English description as complete (if not, yours is incomplete too). As to the correctness, mine is indeed correct.

Thank you for your comment and good debate.

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

How is it O(n) for the space ? since you are not using any extra space other than input array.

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

Commenting on your "NOTE:" you could just initialize product to 1 instead of the first element in the array. It doesn't change anything but in general that is how I like to tackle problems that require finding the product of a set of numbers.

Comment hidden because of low score. Click to expand.

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.