Microsoft Interview Question
Team: bing
Country: India
Interview Type: In-Person
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");
}
i think if array length is even, we can still have balance index.
int[] a = {1,5,5,6} => a[2] is balance index.
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.
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];
}
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;
}
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.
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;
}
}
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;
}
This is a simple question. Why are we making it complicated. "Student" has already given the solution.
#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;
}
//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");
}
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
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;
}
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");
}
}
private static int returnBalanceIndex(int[] input) {
int sum = input[0];
for (int i = 1; i < input.length; i++) {
sum +=input[i];
}
int sumleft = input[0];
System.out.println(sum);
for (int i = 1; i < input.length; i++) {
if(sum - input[i]== (2* sumleft) ){
return i ;}
sumleft +=input[i];
}
return -1;
}
private static int returnBalanceIndex(int[] input) {
int sum = input[0];
for (int i = 1; i < input.length; i++) {
sum +=input[i];
}
int sumleft = input[0];
System.out.println(sum);
for (int i = 1; i < input.length; i++) {
if(sum - input[i]== (2* sumleft) ){
return i ;}
sumleft +=input[i];
}
return -1;
}
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
- student July 15, 2012