Google Interview Question for Applications Developers


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.

- oOZz July 04, 2013 | Flag Reply
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.

- Jose Cuervo July 10, 2013 | Flag
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).

- Myk Enriq July 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 votes

Karatsuba multiplication

- serg.petrenko July 09, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Miguel Oliveira July 25, 2013 | Flag
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.

Google "A Product Array Puzzle" for more info.

- dhaval6244 July 10, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

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

- Anonymous July 04, 2013 | Flag Reply
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]

- passer July 08, 2013 | Flag Reply
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)
			{
				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));
	}
}

- Anonymous July 17, 2013 | Flag Reply
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)

- mel July 27, 2013 | Flag Reply
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)

- mel July 27, 2013 | Flag Reply
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?

- derp July 29, 2013 | Flag Reply
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[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;
}
}

- Anonymous December 12, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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] ,

- simplyankush May 08, 2016 | Flag Reply
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[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

- masterjaso July 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- oOZz July 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- masterjaso July 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- MrA July 11, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- coryk135 July 15, 2013 | Flag
Comment hidden because of low score. Click to expand.


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