Google Interview Question


Country: United States




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

I get an idea:
first , fill the new array like this:
arr[i] = sum(a[0,i-1])
This can be done in O(n) in a for loop
Then, reversely do the operation, and add result to the previous arr.
I'll try program this out,, but have to say,, always easier to think than do it for me..

Simple code:

from random import randint

a = []
for i in xrange(randint(5,10), randint(50,60)):
    a.append(randint(1,100))

res = [0] * len(a)

sm = a[0]

for i in xrange(1, len(res)):
    res[i] = sm
    sm += a[i]

sm = a[len(a)-1]
for i in xrange(len(res)-2, -1, -1):
    res[i] += sm
    sm += a[i]

print sum(a)
print a
print res

- jilinxie1988@gmail.com January 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is the best solution. O(n) in time and O(1) in space.

- Victor January 13, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

That's awesome. Great solution!

- Skor January 14, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

You are given an array of integers 'a' that can fit in a memory. Does this mean you can use extra array. Shouldnt it be done in place?

- Learner January 23, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

java

public static int[] sumArray (int[] a) {
		int[] res = new int[a.length];
		
		int sum=a[0];
		res[0]=0;
		for (int i=1; i<a.length;i++) {
			res[i]=sum;
			sum+=a[i];
		}
		
		sum=a[a.length-1];
		for (int i=a.length-2;i>=0;i--) {
			res[i]+=sum;
			sum+=a[i];
		}
		return res;
	}

- biolxj12 February 23, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Maintain two arrays (in the case of 4 elements for the input array):
{ 0, a[0], a[0]+a[1], a[0]+a[1]+a[2] }
{ a[1]+a[2]+a[3], a[2]+a[3], a[3], 0 }
Now add the arrays element by element (example: arr1[0] + arr2[0] etc...) into a new array and we get:
{a[1]+a[2]+a[3], a[0]+a[2]+a[3], a[0]+a[1]+a[3], a[0]+a[1]+a[2]}
The resulting array is the sum of all elements except a[i].

- Anonymous January 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Although this does consume O(N) space, so maybe someone can optimize this to use O(1) space?

- Anonymous January 13, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Nice solution! My Java implementation

public static int[] sum(int[] arr){
        if (arr.length == 0)
            return new int[0];
        int[] arr1 = new int[arr.length];
        int[] arr2 = new int[arr.length];
        for (int i = 1 ; i < arr.length ; i++){
            arr1[i] = arr1[i-1] + arr[i-1];
        }
        for (int i = arr.length-2 ; i >= 0 ; i--){
            arr2[i] = arr2[i+1] + arr[i+1];
        }
        for (int i = 0 ; i < arr.length; i++){
            arr1[i] += arr2[i];
        }
        return arr1;
    }

- GK January 13, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice solution! :) Can't think of O(1) space though...

- Anonymous January 13, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

I was thinking of the following idea...will test this with code a bit later. The idea is to use recursion. Lets say we have a three element arr a[] = {1, 2, 3}

Keep a running sum of path encountered until now..
if not last element in the array, recurse
if last element in array, store the running sum into array location AND start a running sum of the values from the bottom. The value at each index is the sum of running sum from top and running sum from bottom.

This will do this with only one array

- smallchallenges January 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Nice question. My solution is to implment a subtract(a, b) function that actually does a-b without using the '-' operator. If the language is Java or C++, we can use bit manipulation based on the fact that negative number is the 2-complement of the positive counter part.

subtract(a, b) can be implemented as a + opposite(b).

If b is positive than opposite(b) is obtained by flipping b (xor with 1<<32 for int) and adding 1. If b is negative than opposite(b) is obtained by SUBTRACTING 1 and flipping it (xor with 1<<32).

Now for how to subtracting 1 from a number without using '-'. We keep iterating from the least significant bit to the most significant bit, invert the bit until the last inverted bit was 1.

Personally I think the dynamic programming solution is more intuitive and more language-agnostic.

- Xuan Luong January 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

public static int[] arrayOfSum(int[] a) {
		int sum=0;
		int [] arraySum = new int[a.length];
		
		for (int i = 0; i < a.length; i++) {
			arraySum[i] = sum;
			sum+=a[i];
		}
		sum=0;
		for (int i = a.length-1; i >= 0; i--) {
			arraySum[i] += sum;
			sum+= a[i];
		}
		
		return arraySum;
	}

- akshay January 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

nice solution by @xiejilin@limijiaoyin.com

I have 1 more idea for the problem :

1. O(n) - add all numbers ; let total sum = Sum
2. while loop over all elements, subtract current element (a[i]) from sum

for( i = 0 ; i < n ; i++){
a[i] = Sum +(~a[i] +1); /* (~a[i] +1) is a[i]'s 2's complement */
}

hence over all complexity : O(n)

- Source January 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You cannot subtract. Read the question...But yes, that is the obvious solution if you could subtract.

- akyker20 January 16, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here's a C++ solution that runs in O(n) time and uses O(n) space but can be easily modified to use O(1) space

int* solution(int* a, const int& asize){
  int* b=new int[asize];

  int sum=0;
  for(int i=0;i<asize;++i){
    sum+=a[i];
  }
  for( int i=0;i<asize,++i){
    b[i]=sum+(~a[i])+1;
  }
  return b;
}

- Anonymous January 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int* sumExcept(int[] arr, int size) {
	int* result = new int[size];
	int sum = 0;

	memset(result, 0, sizeof(int) * size);
	sum = arr[0];

	for(int i = 1; i < size; ++i) {
		result[i] = sum;
		sum += arr[i]
	}

	sum = arr[n-1];
	for (int i = size - 2; i >= 0; --i) {
		result[i] += sum;
		sum += arr[i];
	}

	return result;
}

- Bharat Kumar Arya January 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

O(1) space ?

- Anonymous January 13, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes it is O(1) space as you have to return a different array not the same one, so this much space is needed indeed and O(n) performance

- Bharat Kumar Arya January 14, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int[] sumExcluding(int[] array)
{
  if (array == null)
  {
    throw new IllegalArgumentException("array must not be null");
  }
  int[] sums = new int[array.length];
  populateSumAfter(sums, array, 0);
  int s = array[0];
  for (int i = 1; i < sums.length; i++)
  {
    sums[i] += s;
    s += array[i]; 
  }
  return sums;
}

private static int populateSumAfter(int[] sum, int[] array, int i)
{
  if (i >= sum.length)
  {
    return 0;
  }
  else
  {
    sum[i] = populateSumAfter(sum, array, i + 1);
    return sum[i] + array[i];
  }
}

- Anonymous January 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Wouldnt XOR work here?

1) Read the whole array once and calculate the sum
2) Create a new array where result[i] = sum XOR a[i]

I think this might work

O(n) both time and O(n) space.

- Illusion January 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

arr = [1,2,3,4]
sum = 10

it fails on the first element arr[0] XOR sum = 11 not 9, so this solution does not work.

- Anonymous January 14, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Following code does not use "-" sign

public class ArrayAdd {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		
		int [] arr={5,10,15,20,7};
		
		print(arr);
	}

	private static void print(int[] arr) {
		int sum=0,start=0,end=0;
		int[] temp = new int[arr.length];

		for(int i=0 ;i<arr.length;i++){
		//	System.out.println("i "+i+"arr length"+arr.length);
			start=0;
		    sum=0;
		    end=i+1;
			while(start < i)
			{
				sum+=arr[start];
				start++;
			}
		//	System.out.println("sum after start" + sum);
			
			while(end != (arr.length))
					{
				
				sum+=arr[end];
				end++;
					}
		//	System.out.println("sum after end" + sum);
			temp[i]=sum;
		}
		for(int i=0;i<temp.length;i++)
		{
			System.out.print(temp[i]+" ");
		}
	}

}

- dbpradnya January 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Following code does not uses "-" sign

public class ArrayAdd {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub


int [] arr={5,10,15,20,7};

print(arr);
}

private static void print(int[] arr) {
int sum=0,start=0,end=0;
int[] temp = new int[arr.length];

for(int i=0 ;i<arr.length;i++){
// System.out.println("i "+i+"arr length"+arr.length);
start=0;
sum=0;
end=i+1;
while(start < i)
{
sum+=arr[start];
start++;
}
// System.out.println("sum after start" + sum);

while(end != (arr.length))
{

sum+=arr[end];
end++;
}
// System.out.println("sum after end" + sum);
temp[i]=sum;
}
for(int i=0;i<temp.length;i++)
{
System.out.print(temp[i]+" ");
}
}

}

- dbpradnya January 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class ArraySum {

	public static void main(String[] args) {
		int a[] = {0,1,2,3,4,5,6,7};
		int ans[] = getArraySum(a);
		for(int i : ans)
			System.out.println(i);
		//System.out.println(twosComplementSum(50,-1));
	}

	public static int [] getArraySum(int [] arr){
		if(arr==null || arr.length==0)
			return arr;
			
		int ans[] = new int [arr.length];
		int sum=0;
		for(int i: arr)
			sum+=i;
		for(int i=0; i<arr.length; i++){
			ans[i] = twosComplementSum(sum, arr[i]);
		}
		return ans;
	}
	
	public static int twosComplementSum(int sum, int num){
		return 1 + sum + ((~1+1)^num);
	}
	
	public static int twosComplementSum2(int sum, int num){
		for(int i=0;i<32;i++){
			num = num ^ (1<<i);
		}
		sum = sum + num + 1;
		return sum;
	}
}

- Ketav January 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This implementation works. However it has a time complexity of n^2.

public static int[] addExcept(int[] test){
		
		int[] array = new int[test.length];
		
		for(int i= 0; i < test.length ; i++){
			int total = 0;
			for(int k=0; k< test.length; k++){
				if(k != i ){
					total += test[k];
				}
			}
			array[i] = total;
		}
		
		return array;
	}

- roshenw January 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int[] GetSum(int[] a)
{
int[] sumArray = new int[a.Length];
int sum = 0;
for (int i = 1; i < a.Length; i++)
{
sum = sum + a[i - 1];
sumArray[i] = sumArray[i - 1] + a[i - 1];
}
sum = 0;
for (int i = a.Length - 2; i >= 0; i--)
{
sum = sum + a[i + 1];
sumArray[i] = sum;
}
return sumArray;
}

- Daniel January 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>

void convert(int a[], int n);

int main() {
	int a[] = {1,2,3,4,5,6,7,8};
	convert(a,sizeof(a)/sizeof(int));
}

void convert(int a[], int n) {
	int left=a[0];
	a[0]=0;
	for(int i=1;i<n;i++) {
		int temp=a[i];
		a[i]=left;
		left+=temp;
	}
	int sum=left, right=0;
	for(int i=n-1;i>=1;i--) {
		int temp=sum-a[i];
		sum=a[i];
		a[i]+=right;
		right+=temp;
	}
	a[0]+=right;
	for(int i=0;i<n;i++) {
		printf("%d ",a[i]);
	}
	printf("\n");
}

- hugakkahuga January 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The code below has complexity O(n)
	Main idea is to first get the sum of the entire array.Then traverse the entire array and and each element = sum + Not(element at that position +1)

public class IntArray{
	public static void main(String args[]){
	int arr[] ={5,7,2,9,3,1,6};
	getArr(arr);
	
	}

	public static void getArr(int []arr){
		int sum = 0;
		for(int i =0;i<arr.length;i++)
			sum += arr[i];

		for(int i =0;i<arr.length;i++)
			arr[i] = sum + ~arr[i] +1;

		for(int i =0;i<arr.length;i++)
			System.out.println(arr[i]);
	}


}

- Bond January 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

you can code it as a recursion function because both of arrays fit in memory

public static int sumArray(int[] a, int[] b, int i, int preSum) {
		if (i >= a.length) {
			return 0;
		}
		int postSum = sumArray(a, b, i + 1, preSum + a[i]);
		b[i] = preSum + postSum;
		// System.out.println(i+","+b[i]);
		return a[i] + postSum;
	}

- eng.nabil2014 January 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

It is only mentioned to not use '-'. Using 2 complement's is a nice solution I can think of.

public class SumExcept {
	
	public static void main(String args[]) {
		
		Scanner s = new Scanner(System.in);
		int n=s.nextInt(),arr[]=new int[n], sum=0;
		
		for(int i=0; i<n; i++)
			sum+=(arr[i]=s.nextInt());
		
		for(int i=0;i<n;i++)
			arr[i] = sum + ~arr[i]+1;
		
		for(int i=0; i<n; i++)
			System.out.print(arr[i]+" ");
	}
}

- Anindya Dutta January 20, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void generateNegateSumArray(std::vector<int> &a, std::vector<int> &b, int length)
{
	int totalSum = 0;
	b.reserve(length);
	for(int i = 0; i < length; i++)
	{
		b[i] = a[i] * -1;
		totalSum += a[i];
	}
	
	for(int i = 0; i < length; i++)
	{
		b[i] += totalSum;
	}
}

The question asked not to use '-' OPERATOR. We can still multiply by -1 to subtract with using '-' operator.

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

This is of the order o(n)

- Booshi January 22, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Haskell code: O(n) time O(1) space

q2 l = zipWith (+) dp1 dp2
    where 
      dp1 = init $ scanl (+) 0 l
      dp2 = tail $ scanr (+) 0 l

- Anonymous January 25, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

two ways of solving it:

The first is iterative and has a worst case of o(n^2)

void func(int[] buff) {
	
	int before, after = 0;
	for(int i=0; i<buff.length; i++) {
		for(int j=i+1; j<buff.length; j++) {
			after += buff[j];
		}

		int tmp = buff[i];
		buff[i] = before + after;
		before += tmp;
		after = 0;
	}
}

Second option is recursive and has a runtime of o(n)

int func(int before, int index, int[] buff) {
	if(index >= buff.length) return 0;

	int after = func(before + buff[index], index+1, buff);
	buff[index] = before + after;

	return after+buff[index];
}

- YD March 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

assume array is {5,10,15,20,7}
the sum of the elements is = 57
so the result is {57-5, 57-10,57-15,57-20,57-7}, so {52,47,42,37,50}

two for-loop of initial array needed (first to find the sum, other to update)

- Anonymous January 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It specifically says that you cannot use the "-" operator so this solution is not valid!

- Anonymous January 13, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

without using "-" operator, 57 + (-1 *5) = 52 . Here "-" is sign, not operator :) . So this answer will become absolutely valid (by hacking the question)

- Anonymous January 13, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

lol, good luck getting past the google interview by "hacking" questions :)

- Anonymous January 13, 2015 | Flag


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