Google Interview Question
Software EngineersCountry: United States
Interview Type: In-Person
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;
}
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
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;
}
}
}
/*
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 ] ) )
/*
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 ] ) )
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");
}
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;
}
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));
}
}
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");
}
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;
}
// 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;
}
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.
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;
}
// 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;
}
// 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;
}
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;
}
}
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;
}
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;
}
/*
* 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;
}
}
/*
* 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;
}
}
/**
* 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));
}
}
}
}
/**
* 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));
}
}
}
}
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)
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;
}
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
- Raj November 11, 2016