Google Interview Question for Software Engineers


Country: United States
Interview Type: In-Person




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

Time : O(n)
1. initialize leftSum, rightSum to 0
2.find sum of all elements - rightSum
3. for each element in array
a) reduce cur element from rightSum
b) compare rightSum with Left sum, if same return
c) add cur element to leftSum

int findPivot(int a[]){
int leftSum=0,rightSum=0;
for(int i=0;i<a.length;i++){
rightSum+=a[i];
}

for(int i=0;i<a.length;i++){
 rightSum-=a[i];
 if(leftSum == rightSum)
	return i;
leftSum+=a[i];
}
}

- Raj November 11, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

int arr [] ={1,2,3,4,0,6};
		int sumL=0,sumR=0;
		
		for(int i =0 ; i<arr.length ; i++){
			for(int j=0 ;j <=i ;j++){
				sumL+=arr[j];
			}
			for(int m=i ; m <arr.length ;m++){
				sumR+=arr[m];
			}
			if(sumL == sumR && sumL != 0 && sumR != 0){
				System.out.println("pivot index for the given array is : "+i);
			}
			sumL=0;sumR=0;
		}

- Manjula November 11, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

The idea is, start from zero index and sum with previous element and compare with next values some of array from that index to last index,
See algo

Leftsum=0
rightsum=0
I =0 to n
Leftsum+=a(I)
And j =I+1
Rightsum+=a(j)
End inner loop
If leftsum==rightsum
Return index I and break from outer loop
Else rightsum=0

(n2) complexity worst
Best (n)

Thanks

- Dinkar November 11, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

int[]a={1,2,3,0,6};
int l=0;
int r=a.length-1;
int somL = 0,somR=0;
while(l<r){
if(somL<somR) {
somL+=a[l];
l++;
}
else {
somR+=a[r];
r--;
}
}
System.out.println("index"+l);

- ysf.askri November 13, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class pivot {

public static void main(String[] args) {

int arr [] ={1,2,3,4,0,6};
int sumL=0,sumR=0;

for(int i =0 ; i<arr.length ; i++){
for(int j=0 ;j <=i ;j++){
sumL+=arr[j];
}
for(int m=i ; m <arr.length ;m++){
sumR+=arr[m];
}
if(sumL == sumR && sumL != 0 && sumR != 0){
System.out.println("pivot index for the given array is : "+i);
}
sumL=0;sumR=0;
}
}

}

- Manjula November 11, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*
Everyone solved it right.
Thus, I am flexing some muscle power of ZoomBA,
to showcase the full declarative nature of the language : 
*/
def find_pivot_index( arr ){
  if ( empty(arr) ) return -1
  if ( size(arr) == 1 ) return 0
  sums = [ arr[0] , sum( arr ) - arr[0] - arr[1] ]
  if ( sums[0] == sums[1] ) return 1 
  x = index ( [ 2 : #|arr| ] ) :: {  
     sums.0 += arr[ $.item - 1]
     sums.1 -= arr[ $.item ]
     sums.0 == sums.1 
  }
  x < 0 ? x : x + 2  
}
println ( find_pivot_index( [ 0,6,4,1,2,3 ] ) )

- undefined November 11, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*
Everyone solved it right.
Thus, I am flexing some muscle power of ZoomBA,
to showcase the full declarative nature of the language : 
*/
def find_pivot_index( arr ){
  if ( empty(arr) ) return -1
  if ( size(arr) == 1 ) return 0
  sums = [ 0 , sum( arr ) - arr[0] ]
  x = index ( [ 1 : #|arr| ] ) :: {  
     sums.0 += arr[ $.item - 1]
     sums.1 -= arr[ $.item ]
     sums.0 == sums.1 
  }
  x < 0 ? x : x + 1 
}
println ( find_pivot_index( [ 0,6,4,1,2,3 ] ) )

- NoOne November 11, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is an Objective-C solution, time O(n)

-(void)getPivotFrom:(NSMutableArray *)array{
    
    if ([array count] == 0) {
        
        NSLog(@"No Pivot found");
    }
    
    int totalSum = 0;
    for(int i = 0; i < [array count]; i++){
        totalSum += [array[i] intValue];
    }
    
    int leftSum = 0;
    int rightSum = totalSum - [array[0] intValue];
    
    if(leftSum == rightSum){
        
        NSLog(@"Pivot found at index 0");
        return;
    }
    
    for(int i = 1; i < [array count]; i++){
        
        leftSum += [array[i - 1] intValue];
        
        rightSum -= [array[i] intValue];
        
        if(leftSum == rightSum){
            
            NSLog(@"Pivot found at index: %i", i);
            return;
        }
    }
    
    NSLog(@"No Pivot found");
}

- oscarsanchez1937 November 11, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This solution in java

public int findPivot(int[] nums){
        if(nums.length == 0){
            return -1;
        }

        int sumLeft = nums[0];
        int sumRight = 0;
        int left = 0, right = nums.length ;
        while( left<=right  ){
            if(sumLeft > sumRight){
                sumRight += nums[--right];
            }else if(sumLeft < sumRight){
                sumLeft += nums[++left];
            }else{
                if(left+1 == right-1){
                    return left+1;
                }

                if(nums[right-1] == 0){
                    right--;
                }else if(nums[left+1] == 0){
                    left++;
                }else {
                    sumRight += nums[right--];
                    sumLeft += nums[left++];
                }
            }
        }
        return -1;
    }

- JosephEl November 11, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

package com.eb.corealgo;

public class Pivot {

	int getPivotIndex(int array[]){
		
		if(array == null){
			
			return -1;
		}
		
		if(array.length == 1){
			
			return 0;
		}
		

		int sL = 0;
		
		int sR = 0;
		
		for(int i = 0; i<array.length ; i++ ){
	
			sL = sL + array[i];
			
			sR = sR + array[array.length -1 -i];
			
			if(sL == sR){
				
				return i;
			}
		}
		
		return 0;
	}
	
	
	public static void main(String args[]){
		
		Pivot p = new Pivot();
		
		int arr [] ={1,2,3,4,1,0,4,0,6};
		
		System.out.println(p.getPivotIndex(arr));
	}
}

- shashikumar November 12, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Objective C solution

-(int) findPivot: (NSArray*) arr{
	int leftSum = 0;
	int rightSum = 0;

	//rightSum is the sum of array elements

	for(int i = 0; i < [arr count];i++){
		rightSum += [[arr objectAtIndex:i]intValue] ;
	}
	for(int j = 0; j < [arr count];j++){
		leftSum += [[arr objectAtIndex:j]intValue];
		rightSum -= [[arr objectAtIndex:j]intValue];
		if(leftSum == rightSum){
			return j;
		}
	}
	return -1;
	NSLog(@"pivot not found");
}

- Alisha November 12, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Sum all elements first
2. for each element check ((Sum - element)%2) == 0
3. The element for which the above is true is the index

int arr [] ={1,2,3,4,0,6};
		int sum = 0;
		
		for(int i =0 ; i<arr.length ; i++){
			sum+= arr[i];
		}
		
		for(int i =0 ; i<arr.length ; i++){
			tempSum = sum;
			if((tempSum - arr[i])%2 == 0)
				return i;
		}

- liju.leelives November 13, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int pivot(int arr[],int n)
{
int sum=0;
for(int i=0;i<n;i++)
sum+=arr[i];
int tot=0;
for(int i=0;i<n;i++)
{
sum-=arr[i];
if(sum==tot)
return i;
tot+=arr[i];
}
return -1;

}

- pratyush2013 November 13, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def findPivot(myList):
    sumLeft = 0
    sumRight = sum(myList) - myList[0]
    if sumLeft == sumRight:
        return 0
    else:
        for i in range(1, len(myList)):
            sumLeft += myList[i]
            sumRight -= myList[i]
            if sumLeft == sumRight:
                return i
    return -1

- Newbie November 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// Worst Condition for Time Complexity and Space Complexity is less than 0(n).
public static int quickFindPivot(int arr[]){
		int leftIndex = 0;
		int rightIndex = arr.length -1;
		int sumLeft = 0,sumRight = 0; 
		int count = 0;
		
		while(leftIndex < rightIndex){
			count++;
			if(sumLeft < sumRight){
				sumLeft += arr[leftIndex];
				leftIndex++;
			} else {
				sumRight += arr[rightIndex];
				rightIndex--;
			}
		}	
		System.out.println("sumLeft:"+sumLeft);
		System.out.println("sumRight:"+sumRight);
		if(sumLeft == sumRight){
			System.out.println("count:"+count);
			return leftIndex;
		}
		
		return -1;
	}

- umesh.shaw November 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int pivot(vector<int> cov) {
	int n = v.length();
	vector<int> v1(n);
	for (auto i = 0; i<n; i++) v1[i] = (i==0?)v[0]: v1[i-1]+v[i];
	for (auto i = 0; i<n; i++) {
		if (2*v1[i]+v[i] == v1[n-1]) return i;
	}
}

- Oldmonk November 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int pivot(vector<int> cov) {
	int n = v.length();
	vector<int> v1(n);
	for (auto i = 0; i<n; i++) v1[i] = (i==0?)v[0]: v1[i-1]+v[i];
	for (auto i = 0; i<n; i++) {
		if (2*v1[i]+v[i] == v1[n-1]) return i;
	}
}

- Oldmonk November 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int pivot(vector<int> cov) {
	int n = v.length();
	vector<int> v1(n);
	for (auto i = 0; i<n; i++) v1[i] = (i==0?)v[0]: v1[i-1]+v[i];
	for (auto i = 0; i<n; i++) {
		if (2*v1[i]+v[i] == v1[n-1]) return i;
	}
}

- Oldmonk November 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int pivot(vector<int> cov) {
	int n = v.length();
	vector<int> v1(n);
	for (auto i = 0; i<n; i++) v1[i] = (i==0?)v[0]: v1[i-1]+v[i];
	return std::distance(v.begin(), std::upper_bound(v1.begin(), v1.end(), v1[n-1]/2));
}

- Oldmonk November 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int pivot(vector<int> cov) {
	int n = v.length();
	vector<int> v1(n);
	for (auto i = 0; i<n; i++) v1[i] = (i==0?)v[0]: v1[i-1]+v[i];
	return std::distance(v.begin(), std::upper_bound(v1.begin(), v1.end(), v1[n-1]/2));
}

- oldestofmonks November 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int pivotIndex(int[] arr){
	if(arr == null || arr.length < 2){
		throw new IllegalArgumentException();
	}=
	reint cumSum = 0;
	for(int i = 0; i < arr.length; i++){
		cumSum += arr[i];
	}
	
	int s = arr[0];
	for(int i = 1; i < arr.length; i++){
		s += arr[i];
		if(s == (cumSum - arr[s])){
			return i;
		}
	}
	return -1;
}

//Time Complexity: O(N) where N is the size of the array.

- divm01986 November 15, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int sumofNumbersRightEqualsLeft(int []arr){
	
	int[]sums = new int[arr.length];
	int len = arr.length, i, sum= 0;
	sums[0] = arr[0];

	for(int i = 1; i<len; i++){//Going forward. 
		sums[i] = sums[i-1] + arr[i];
	}

    for(i = len - 1 ; i>=0; i--){//Going reverse to check.
       sum += arr[i];
       if(sum == sums[i] && sum>0){
          return i;
       }
    }

    return -1;
}

- Mir November 16, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// Time : O(n)
// Space : O(1)
int pivot( const std::vector<int> &A) {
long rsum = 0;
long lsum = 0;

for (auto a: A) {
rsum += a;
}

for (int i=0; i<A.size(); i++) {
rsum -= A[i];
if (rsum == lsum)
return i;
lsum += A[i];
}
return -1;
}

int main()
{
vector<int> A{1,2,3,4,0,6};
cout << pivot(A) << endl;
return 1;
}

- EmilFlater November 16, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// Time: O(n)
// Space: O(1)
std::vector<int> arrayDuplicates(std::vector<int> &A)
{
    std::vector<int> ret;
    int processedMarker = A.size();
    
    for (int i=0; i<A.size(); i++) {
        if ( A[i] != i ) {
            int newIndex;
            
            while( A[i] != i ) {
                if (A[i] == processedMarker || A[newIndex] == processedMarker )
                    break;
                
                if (A[newIndex] == A[i]) {
                    ret.push_back(A[i]);
                    A[newIndex] = processedMarker;
                    A[i] = processedMarker;
                    break;
                }
                
                swap(A[i], A[newIndex]);
            }
        }
    }
    return ret;
}

- EmilFlater November 16, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class PivotIndex {

	public static void main(String[] args) {
		int arr[] = {8,1,2,3,4,0,6,8};
		System.out.println(pivotIdx(arr));
	}
	
	static int pivotIdx(int arr[]){
		int leftSum=0, rightSum=0;
		
		int j = arr.length-1;
		int i=0;
		int totCount = 0;
		while(i<j && (totCount <= arr.length-2)){
			
			if(leftSum >= rightSum){
				rightSum = rightSum + arr[j--];
			}else{
				leftSum = leftSum + arr[i++];
			}
			totCount++;
		}
		
		if(leftSum != rightSum){
			return -1;
		}
		
		int pivot = ((i+j)/2); 
		System.out.println(arr[pivot]  +" leftSum="+ leftSum +" rightSum="+rightSum);
		return pivot;
	}
}

- reddymails November 20, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int findPivot(int[] input)
	{
		if( input == null || input.length <= 1)
			return -1;
		
		int sum_left = 0;
		int sum_right = 0;
		
		for(int i = 1; i < input.length; ++i)
		{
			sum_right += input[i];
		}
		
		for( int i = 0; i < input.length -1 ; ++i)
		{
			if(sum_left == sum_right)
				return i;
				
			sum_left += input[i];
			sum_right -= input[i+1];
		}
		return -1;
	}

- ohadr.developer November 20, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int findPivotIndex(List<Integer> ints) {
		int left = 0, right = ints.size() - 1, sumLeft = 0, sumRight = 0;
		sumLeft = ints.get(left);
		sumRight = ints.get(right);
		while (left < right) {
			if (sumLeft < sumRight) {
				sumLeft += ints.get(++left);
			} else if (sumLeft > sumRight) {
				sumRight += ints.get(++right); 
			} else {
				left++;
				right--;
			}
		}
		return sumLeft == sumRight ? right : -1;
	}

- Ahmed.Ebaid November 27, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*
 * Return pivot index of the given array of numbers
 * the pivot index is the index where sum of left and right side is equals
 */
public class PivotIndexForArray {

	public static void main(String[] args) {
		int arrays [] = {1,2,3,4,1,0,4,0,6};
		System.out.println( getPivot( arrays ));
	}
	
	private static int getPivot( int [] arrays ){
		for( int i = 1; i < arrays.length; i++ ){
			if( getSumFromStartToEnd( 0, i, arrays) == getSumFromStartToEnd( i+1, arrays.length, arrays)){
				return i;
			}
		}
		return -1;
	}
	 
	
	private static int getSumFromStartToEnd( int start, int end, int [] arrays ){
		
		if( arrays.length > 0 && start < end ){
			int sum = 0;
			for( int i = start; i < end; i++ ){
				sum += arrays[i];
			}
			return sum;
		}
		return 0;
	}

}

- Raghavendra Puttappa December 04, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*
 * Return pivot index of the given array of numbers
 * the pivot index is the index where sum of left and right side is equals
 */
public class PivotIndexForArray {

	public static void main(String[] args) {
		int arrays [] = {1,2,3,4,1,0,4,0,6};
		System.out.println( getPivot( arrays ));
	}
	
	private static int getPivot( int [] arrays ){
		for( int i = 1; i < arrays.length; i++ ){
			if( getSumFromStartToEnd( 0, i, arrays) == getSumFromStartToEnd( i+1, arrays.length, arrays)){
				return i;
			}
		}
		return -1;
	}
	 
	
	private static int getSumFromStartToEnd( int start, int end, int [] arrays ){
		
		if( arrays.length > 0 && start < end ){
			int sum = 0;
			for( int i = start; i < end; i++ ){
				sum += arrays[i];
			}
			return sum;
		}
		return 0;
	}

}

- puttappa.raghavendra December 04, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/**
 * Return the pivot index of the given array of numbers. The pivot index is the index where the sum of the numbers on the left is equal to the sum of the numbers on the right. Input Array {1,2,3,4,0,6}
 */
public class LeftPivotRightSum {
    
    public static void main(String[] args) {
        int []numbers={1,2,3,4,0,6};
        
        for (int i = 1; i < numbers.length; i++) {
            int sumLeft=0;
            int sumRight=0;
            
            for (int j = 0; j < i; j++) {
                sumLeft = sumLeft + numbers[j];
            }
            
            for (int k = i+1; k < numbers.length; k++) {
                sumRight = sumRight + numbers[k];
            }
            
            System.out.println("sum Left--"+sumLeft);
            System.out.println("sum Right--"+sumRight);
            System.out.println("-------------------------------------");
            if(sumLeft == sumRight)
            {
                System.out.println("pivot index--"+ (i+1));
            }
        }
        
    }

}

- Sudheer December 13, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/**
 * Return the pivot index of the given array of numbers. The pivot index is the index where the sum of the numbers on the left is equal to the sum of the numbers on the right. Input Array {1,2,3,4,0,6}
 */
public class LeftPivotRightSum {
    
    public static void main(String[] args) {
        int []numbers={1,2,3,4,0,6};
        
        for (int i = 1; i < numbers.length; i++) {
            int sumLeft=0;
            int sumRight=0;
            
            for (int j = 0; j < i; j++) {
                sumLeft = sumLeft + numbers[j];
            }
            
            for (int k = i+1; k < numbers.length; k++) {
                sumRight = sumRight + numbers[k];
            }
            
            System.out.println("sum Left--"+sumLeft);
            System.out.println("sum Right--"+sumRight);
            System.out.println("-------------------------------------");
            if(sumLeft == sumRight)
            {
                System.out.println("pivot index--"+ (i+1));
            }
        }
        
    }

}

- YSR December 13, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def find_pivot(a):
    sum_left = 0
    sum_right = sum(a)
    
    for pivot in xrange(len(a) + 1):
        if pivot == 0:
            sum_right -= a[pivot]
        elif pivot == len(a):
            sum_left += a[pivot - 1]
        else:
            sum_right -= a[pivot]
            sum_left += a[pivot - 1]
        
        if sum_right == sum_left:
            print sum_right, sum_left
            return pivot
    return -1

arr = [-1,1,5]
print find_pivot(arr)

- Nitish Garg December 26, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int balance(int[] a){
	int leftW=a[0];
	int rightW=a[a.length-1];
	int left=0;
	int right=a.length-1;
	while(left<right-1){		
		if(rightW>=leftW){
			left++;
			leftW+=a[left];			
		}else if(rightW<leftW){
			right--;
			rightW+=a[right];
		}	
	}
	return left;
}

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

It could be solved using O(N^2) with a linear scan for sum by moving the cursor of the pivot index from the start to the end. It could be better solved by using O(N) with a caching sum while moving left and right cursor.

JavaScript solution:

function findPivot(A) {
	var lInd = 0, 
              rInd = A.length - 1,
              lSum = A[lInd],
	      rSum = A[rInd];
	while(lInd < rInd) {
		if (lSum <= rSum) lSum += A[++lInd];
		else rSum += A[--rInd];
	}
	if (lSum === rSum) return lInd;
	return -1;
}

- ZH January 24, 2017 | 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