Google Interview Question
Applications DevelopersCountry: United States
Interview Type: Phone Interview
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).
int n = a.length;
int[] b = new int[n];
b[0] = 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
package com.careercup.google;
import java.util.ArrayList;
class BigIntTest
{
static class BigInt
{
public BigInt(int[] _digits)
{
for(int d : _digits)
{
digits.add(d);
}
}
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));
}
}
No overflow
void fillproduct(vector<int> &num)
{
if (num.size() == 0)
return;
if (num.size() == 1)
{
num[0] = 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;
}
}
l = [3,4,1,5,6,7]
pre = [1]*len(l)
pos = [1]*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] ,
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[0];
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
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.
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.
How is it O(n) for the space ? since you are not using any extra space other than input array.
1. First pass calculate the product P of all the numbers in array A
- oOZz July 04, 20132. 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.