Microsoft Interview Question

  • microsoft-interview-questions
    0
    of 0 votes
    29
    Answers

    find the balance index of an array where balanced index i is defined as the one whose left sum is equal to the right sum of the index .
    i.e
    summation (1 to i-1) = summation (i+1 to length of an array) firdt I gave o(n2) solution , but then before i could give O(n) solution it was time up for me,
    O(n) solution will be we have to loop through i = 1 to N and find if ( sum of array - sum of array (1 to i-1 ) = ( sum of array - sum of array (1 to i+1 ) the return i.
    Your thoughts?

    - softy on July 15, 2012 in India for bing Report Duplicate | Flag
    Microsoft Algorithm Arrays Coding Data Structures

Team: bing
Country: India
Interview Type: In-Person


Comment hidden because of low score. Click to expand.
15
of 19 vote

here first we traverse the array once to find total sum of array....

then we again start from 0th position and start subtracting value from total sum and go on adding it to leftsum and then compare leftsum and total remaining sum

#include<stdio.h>
 
int equil(int arr[],int size)
{
        int i=0,arrsum=0;
        int leftsum=0;
 
        for(i=0;i<size;i++)
                arrsum+=arr[i];
 
        for(i=0;i<size;i++)
        {
                arrsum-= arr[i];
                
                if(leftsum == arrsum)   
                        return i;
 
                leftsum+=arr[i];
        }
 
        return -1;
}
 
 
int main()
{
        int arr[] = {-7, 1, 5, 2, -4, 3, 0};
        int size = sizeof(arr)/sizeof(arr[0]);
        printf("Equilibrium index is : %d",equil(arr,size));
 
        return 0;
        
}

- student on July 15, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

pretty cool !!

- maverick2587 on July 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

nice

- rkt on August 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Logic is very nice but I think the code has a bug, the

if(leftsum == arrsum)  return i;

should come after

leftsum+=arr[i];

- ishtiaque.h on October 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
4
of 4 vote

Hint: Start from both the ends..

void find_balance_index() {
	int a[]= {1,3,4,6,7,2,5,9,1,11,9,6,5,8,9,1}, i=0, j=0, sum_l=0, sum_r=0;

	j = ARRAY_SIZE(a) - 1;
//	if(j%2==0) { printf("-%d---No balance can be found----\n", j); exit(0); }
	while(i<j) {
			//printf("Indice Values: %d -- %d\n", a[i], a[j]);
			if(sum_l < sum_r)
				sum_l += a[i++];
			else sum_r += a[j--];;
			printf("Indices: %d -- %d\t\t", i, j);
			printf("SUMs: %d -- %d\n", sum_l, sum_r);
	
	}
	if(sum_l == sum_r) printf("Finally The balance is @ %d \n", i);
	else printf("-Final---No balance can be found----\n");
}

- Zander on July 15, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

i think if array length is even, we can still have balance index.
int[] a = {1,5,5,6} => a[2] is balance index.

- dandy on August 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Does this work if there are negative numbers in the array?

- Naveen Reddy Mandadi on August 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

int retind(int size)
{
float f=sqrt((size*size-size)/2);
int i=f;
if((f-i)>0)
return -1
else
return i;
}

i think this will fix it up..........

- kararicky on August 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

edit :
sum of array - sum of array (1 to i-1 ) = ( sum of array - sum of array (i+1 to length of array ) then return i.

- softy on July 15, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

i have posted a solution .,,,,,,,hope its the best

- kararicky on August 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Is the array sorted?
If it is sorted than take one index i=0 and other index j=n-1;

int get_balance_index(int a[n])
{
sum_l=a[i]; sum_r=a[j];
while(1){
	if(i>=j )
	{
		if(sum_l==sum_r) 
			return i;
		else
			return -1;
	}
	if( i+1<j &&sum_l<sum_r)
		sum_l+=a[++i];
	else if(i< j-1 && sum_l>sum_r)
		sum_r+=a[--j];
}

- Yoda on July 15, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

If it is not sorted traverse 2 times

int get_index_point(int a[n])
{
int sum=0;
//calculate sum
for(int i=0;i<n-1;i++)
	sum+=a[i];

//calculate sum/2	
int sum_half=0;
for(int i=0; sum_half<sum/2; i++)
	sum_half+=a[i];
//Sum(a[0..i-1]) = Sum(a[i..n-1])	
if(sum_half-a[i]==sum/2) 
	return i-1;
else 
	return -1;
}

- Yoda on July 15, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

this will only check if the midpoint is balanced index or not ...

eg
in array [10 4 3 2 5] 1st position is the balanced inxdex since leftsum = rightsum = 10

- student on July 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here, for every i, you have to compute 2 subarray sums: [0, i-1] and [i+1, N-1]. This can be done by maintaining a sum[] array where sum[i] is the sum of the array from 0 to i (inclusive).

- anujkaliaiitd on July 15, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The solution of this problem can be achieved by Divide and Conquer rule.
Let us take above mentioned array = {10,4,3,2,5}

1. Find the middle index of the array,In this case index is (0 + 5)/2 = 2.
2. Calculate the sum of two subarrays (Left subarray starting from 0 to index - 1 and right subarray starting from index + 1 to end) and check the condition.In this case left subarray sum up to 10 + 4 = 14 and right subarray 2 + 5 =7.
3. That means now we need to shift the index from 2nd to left.Now the new index is (0 + 2)/2 = 1
4. Left subarray contains 10 and right subarray sum up to 3+ 2 + 5 = 10.So the index is 1 in this case.

- TechGroup on July 15, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Your Algorithm works but the time complexity is O(nlogn).

Recurrence Relation:T(n) = T(n/2) + O(n-1) where
T(n/2) is the time complexity to solve the left/right subarray and
O(n-1) is the complexity to compute the sum for both subarrays

If we solve this we will get O(nlogn)

- CVD on July 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

int compute_index(int arr[],int size)
{
int sum1=0,sum2=0;
int i=0,j=size-1;
for( ;i<10 && j>=0;)
{
if(sum1==sum2 && i==j)
return i;
else if(i==j)
return -1;
else if(sum1>sum2)
sum2 =sum2+arr[j--];
else if(sum2>sum1)
sum1=sum1+ arr[i++];
else if(sum2==sum1)
{
sum1 =sum1+arr[i++];
sum2 =sum2+arr[j--];
}
cout<<i<<" "<<j<<" sum1: "<<sum1<<" sum2: "<<sum2<<endl;
}
}

- Varun Varunesh on July 16, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Here last line "cout" is not needed.... i.e. only used to check

- Varun Varunesh on July 16, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int GetBalancedIndex(int[] inputArray)
        {


            Int64 arraySum = 0;
            Int64 leftSumt = 0;
            for (int i = 0; i < inputArray.Length; i++)
            {
                Console.Write(inputArray[i] + " , ");
                arraySum += inputArray[i];
            }
            Console.WriteLine();
            for (int i = 0; i < inputArray.Length; i++)
            {
                leftSumt += inputArray[i];
                arraySum -= inputArray[i];
                if (arraySum == leftSumt)
                {
                    Console.WriteLine("Balanced Index {0} : ", i);
                    return i;
                }

            }
            return -1;


        }

- ajaypathak on July 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is a simple question. Why are we making it complicated. "Student" has already given the solution.

- DarkKnight on July 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

+1

- Anonymous on August 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<conio.h>
#include<stdio.h>

int balpoint(int a[],int size);
int main()
{
    int arr[]={1,3,4,6,7,2,5,9,1,11,9,6,5,8,9,1};
    int size= sizeof(arr)/sizeof(arr[0]);
    printf("balanced index=%d",balpoint(arr,size));
    getch();
    return 0;
}


int balpoint(int a[],int size)
{
    int leftsum=0;
    int rightsum=0;
    int i=0;
    leftsum=a[0];
    for(i=2;i<size;i++)
      rightsum +=a[i];
    if(leftsum==rightsum)
        return 1;
    else
    {
        for(i=2;i<size-1;i++)
        {
            leftsum +=a[i-1];
            rightsum -=a[i];
            if(leftsum==rightsum)
                return i;
                }
                }
   
   return -1;
}

- raamos on July 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//if the array is sorted
	//worst case complexity O(n)
	static void sortedArrayApproch(int sortedArray[]){
		if(null==sortedArray ){
			System.out.println("not threr");
			System.exit(0);
		}
		int i=0, j = sortedArray.length-1, leftsum=0, rightsum =0;
		int loopcount =0;
		System.out.println(sortedArray.length);
		while(i<j){
			loopcount++;
			if(leftsum<rightsum)
				leftsum+=sortedArray[i++];
			else
				rightsum+=sortedArray[j--];
			if(((j-i)*sortedArray[j])<Math.abs(rightsum-leftsum)){
				System.out.println(loopcount);
				System.out.println("cannot be fount");
				System.exit(0);
			}
		}
		System.out.println(loopcount);
		if(leftsum == rightsum)
			System.out.println(i);
		else
			System.out.println("not there");
	}
	//if we does not know whether array is sorted
	//O(n)
	static void  unSortedArrayApproch(int a[]){
		if(null==a ){
			System.out.println("not threr");
			System.exit(0);
		}
		int i=0, j = a.length-1, leftsum=0, rightsum =0;
		while(i<j){
			if(leftsum<rightsum)
				leftsum+=a[i++];
			else
				rightsum+=a[j--];
		}
		if(leftsum == rightsum)
			System.out.println(i);
		else
			System.out.println("not there");
	}

- pratap.raavi on July 26, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int index(int arr[],int size)
{
int leftsum=0, rytsum=0, i=0, j=size-1;
while(i!=j)
{
if(leftsum>rytsum)
{
rytsum+=arr[j];
j--;
}
else
{
leftsum+=arr[i];
i++;
}
if(leftsum==rytsum)
cout<<i;
else
count<<"not poss";

- bsnabg on July 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

While @student already gave a correct answer, I think there's another simple approach to this problem, it does require O(n) space though (so I wouldn't argue this is better than @student's solution)

The idea is to create an auxiliary array which contains the accumulative sum of the original array, then scan through the auxiliary array for element that is exactly half of the last element

int FindEquilibriumSimple(const vector<float >& input) {
  int num_elem = input.size();
  vector<float> sums(num_elem, 0);
  sums[0] = input[0];
  for (int i = 1; i < num_elem; ++i) {
    sums[i] = sums[i-1] + input[i];
  }
  
  float target = sums[num_elem - 1] / 2;
  for (int i = 0; i < num_elem - 1; ++i) {
    if (sums[i] == target) // better to use abs diff < eps
      return i;
  }
  
  return -1;
}

I have implemented both approach and from the test cases I provided so far they produce the same result, try it out here: ideone.com/bsc0f

- airfang613 on July 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is a solution in C#

public int FindbalancedIndex(int[] array)        
        {            
            int low = 0;
            int high = array.Length-1;

            int lsum=array[low];//sum of array members starting from left
            int rsum=array[high];////sum of array members starting from right

            while (low < high-1)
            {                
                if (lsum == rsum) //add to both sums and increment both indices
                {
                    lsum += array[++low];
                    rsum += array[++high];

                }
                else if (lsum < rsum)                
                    lsum += array[++low];                
                else                
                    rsum += array[--high];
                
            }
            return (lsum == rsum) ? low : -1;
        }

- Pradeep on July 31, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int getIndex(int[] array)
    {
        
        if(array.length==1)
            return 0;
        
        int sum= getSum(array);
        
        int headSum= 0;
        int tailSum= sum - array[0];
        
        for(int i=1; i<array.length-1; i++)
        {
            headSum+= array[i-1];
            tailSum-= array[i];
            
            if(headSum==tailSum)
                return i;
        }
        
        return -1;
    }

- nj on August 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void findBalancedIndex(int[] inpArr) {
		int i = 0;
		int j = inpArr.length-1;
		int leftSum = inpArr[i];
		int rightSum = inpArr[j];
		while(i!=j) {
			if(leftSum > rightSum) {
				j--;
				rightSum += inpArr[j];
			} else {
				i++;
				leftSum += inpArr[i];
			}
		}
		if(leftSum == rightSum) {
			System.out.println("Balanced index is " + (i+1));
		} else {
			System.out.println("Balanced index does not exist");
		}
	}

- Vin on September 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Question:
array: 1 1 0 0 0 1 1
we have three equilibrium point in this array. Which one should we return?

- Kevin on March 09, 2013 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book walking you through 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