Microsoft Interview Question Software Engineer / Developers
Here you are assuming the numbers that make up the average are consecutively located in the array, how would you find out if averages are formed by skip elements and also I see that you are not updating the avg of the whole aray
The key is the phrase divide the array into two subarrays. therefore you can only have average(array[0..i])=average(array[i+1..n-1]) assuming fo course that this is made possible by the values in the array. Doing the brute force will be something like take the array[0..i] and array[i+1..n-1], make the average for the two subarrays and compare them for each i from 0 to n-1. This in unnecesary. You can do first the average of the whole array. Then from this average can get the average of the whole array excetp a[0] (the formula is: avg(a[1..n-1])=(avg(a[0..n-1])*n-a[0])/(n-1)). Then you take this new average and compare it with a[0]. If they are not equal you move to the next value calculating the averages from the previously know averages using the formula from above.
First go through the array and sum up the integers then divide it by two.
let half = sum(array)/2;
Now find a subset of integers in the array such that the sum is equal to half. There are cases where no solution exist.
As you can see, finding subset then sum up the subset has many redundancies. Using dynamic programming can make this problem faster.
There is a ACM UVA problem called Tug of War that is similar to this.
I understand this problem to be a variant of the subset-sum problem.
subset-sum problem can be solved using DP, o(N2) time and o(N2) space.
Assuming we have algo for solving subset-sum.
(here i am assuming all +ve integers), -ve integers is an easy modification.
Given:
TS = total sum.
sumA/nA = sumB/nB.
sumA = (sumB)*(nA/nB)
sumA = (TS-sumA)*(nA/nB);
sumA = (TS-sumA)*(i/N-i), i from 1 to N-1. (all possible splits).
This will translate to sumA = TS*(i/N).
where i is from 1..N-1
Here is an algo,
1. Find the Total Sum of the array.
2. For i from 1 to N-1
2.1 calculate sA = TS*i/N. If sA is an integer (ie no decimal points), Then find if there is a subset from the array which gives sum = sA, and subset size = i. If such a subset is present, return true.
3. return false
Step 2.1 is a subset sum problem.
As far as the DP solution for subset sum problem, please look at http://en.wikipedia.org/wiki/Subset_sum_problem
Comments/criticisms welcome.
Thanks,
Rohith
How is this supposed to be a solution?
The subset sum tries to maximize a sum s subject to some condition s <= W, where W is a bound, what is the bound in your case? also the size of the set that comprises the sum s does not matter.
1. calculate the average of the array (called it ave)
2.sort the array
3. keep two pointer,one from the begining of the sorted array, the other endof the sorted array. starting from calculating of the first and last element. if the average=ave, print the subarray which is composed of the elements whose index are stored in the two pointers. if the average<ave, add the element which the first pointer is pointing and move the pointer forward, if the average>ave, add the element which the second pointeris pointing andmove the pointer backward; and calculate the average, continue this till average=ave.
void getsubArray(int a[],int n,int ave)
{
int i=0;
int j=n-1;
sum=a[i]+a[j];
count=2;
int average=sum/count;
while(i<=j)
{
if(average==ave)
{for(int s=0;s<=i;s++)
printf("%d",a[s]);
for(int s=n-1;s>=j;s++)
printf("%d",a[s]);
}
if(average<ave)
{
sum+=a[++i];
}
else
sum+=a[++j];
average=sum/(++count);
}
}
subset sum, using dynamic programming to solve
given: array A[1...n]
// first calculate the sum
int sum = A[1] + A[2] + ... A[n];
// if sum is odd, no such equal partition exists
if( sum % 2 != 0) return false;
// a boolean array initialized to all false except the first element
int workable[sum];
memset(workable, 0, sizeof(workable);
workable[0] = 1;
for(int i = 1; i <= n; ++i)
for(int s = sum; s >= 0; --s)
if(workable[s])
workable[s + A[i]] = 1;
return workable[sum/2];
int intarray[10];
int Sum;
/*find sum*/
for ( i = 0; i< 10; i++)
{sum += intarray[i]}
/*find average*/
int Avg;
Avg = sum / 10;
sum = 0;
/*find half array*/
for( i = 0; i<10
; i++)
{
while ((sum+= intarray[i] )/(i+1) !== avg);
}
print f ( " Array has been broken down, first %d elements in first array and remaining ones in the other, i+1)
int intarray[10];
int Sum;
/*find sum*/
for ( i = 0; i< 10; i++)
{sum += intarray[i]}
/*find average*/
int Avg;
Avg = sum / 10;
sum = 0;
/*find half array*/
for( i = 0; i<10
; i++)
{
while ((sum+= intarray[i] )/(i+1) !== avg);
}
print f ( " Array has been broken down, first %d elements in first array and remaining ones in the other, i+1)
int intarray[10];
int Sum;
/*find sum*/
for ( i = 0; i< 10; i++)
{sum += intarray[i]}
/*find average*/
int Avg;
Avg = sum / 10;
sum = 0;
/*find half array*/
for( i = 0; i<10
; i++)
{
while ((sum+= intarray[i] )/(i+1) !== avg);
}
print f ( " Array has been broken down, first %d elements in first array and remaining ones in the other, i+1)
Hi, This is a very straight forward dynamic programming problem. But works if the sum of the numbers is small. We have to find if the average of the array is same as average of some subset.Say the average of the array is stored in say a Variable reqAvg. The psuedo code is as follows.
bool isAveragePossible(int n=0,int sum=0,int index=0){
if(index==arraysize)
return (n>0)?(sum/(double)n==reqAvg):0;
if(dp[index][n][sum]!=-1)
return dp[index][n][sum];
else
return dp[index][n][sum]=isAveragePossible(n+1,sum+arr[index],index+1)||isAveragePossible(n,sum,index+1);
}
Hi, This is a very straight forward dynamic programming problem. But works if the sum of the numbers is small. We have to find if the average of the array is same as average of some subset.Say the average of the array is stored in say a Variable reqAvg. The psuedo code is as follows.
bool isAveragePossible(int n=0,int sum=0,int index=0){
if(index==arraysize)
return (n>0)?(sum/(double)n==reqAvg):0;
if(dp[index][n][sum]!=-1)
return dp[index][n][sum];
else
return dp[index][n][sum]=isAveragePossible(n+1,sum+arr[index],index+1)||isAveragePossible(n,sum,index+1);
}
AvgEqual(int arr[], rem,sum,k){
if(k > = length(arr)) return;
if(rem/(length(arr)-count) == sum/count) {
print i where X[i]=1 // as array 1;
print i where X[i]=0 // as array 2;
return; }
X[k]=1;
AvgEqual(arr, rem-arr[k],sum+arr[k],k+1,count+1);
X[k]=0;
AvgEqual(arr, rem,sum,k+1,count);
}
we can do it in a single traversal.
total1, avg 1 for avg from beginning
total2 ,avg 2for avg from last
compute from (i=0 && j<N-1) do i++ & j-- {
compute the avg1 && avg2 .
avg1 = total1 with respect to i
avg2 = total2 with respect to j
if(avg1 > avg2)
then do the process (calculate avg2)from last(decrement j by 1)
else
then do the process(calculate avg1) from beginning(increment i by 1)
if(i==j)
stop the process
}
check the avg1 == avg2
if equeal then i(==j) is the second subarray.
What about this one. I have tried all the input and it works. The complexity is O(nlogn) because of sorting.
LNode *RootL=NULL, *RootR=NULL;
void DivideSet(int A[], int len)
{
LNode *l=NULL,*r=NULL;
//Simmple step sort the array.
if (len<=1) return;
QSort(A,0,len-1);
//find the average.
unsigned long sum=0;
for (int i = 0;i<len;i++)
sum+=A[i];
int avg = sum/2;
int leftSum=0, rightSum=0;
int j = len -1;
for (;j>=0;)
{
if (leftSum+A[j]<=avg)
{
leftSum+=A[j];
if (l==NULL)
RootL=l = new LNode(A[j]);
else{
l->setNext(new LNode(A[j]));
l = l->getNext();
}
j--;
}
else if (rightSum+A[j]<=avg)
{
rightSum+=A[j];
if (r==NULL)
RootR = r= new LNode(A[j]);
else{
r->setNext(new LNode(A[j]));
r = r->getNext();
}
j--;
}
else
break;
}
//Now it is time to fine tune.
for (int k=0;k<=j;k++)
{
if (leftSum<rightSum)
{
leftSum+=A[j];
if (l==NULL)
RootL=l= new LNode(A[j]);
else{
l->setNext(new LNode(A[j]));
l = l->getNext();
}
}
else
{
rightSum+=A[j];
if (r==NULL)
RootR = r = new LNode(A[j]);
else{
r->setNext(new LNode(A[j]));
r = r->getNext();
}
}
}
return;
}
this algo is only good for positive no array...
1. first divide array in two equal parts( in term of size of an array) and keep an track of mid no.
2. find the sum of both subarray and calculate the diff betn them..
3. then find the no. closest to half of the diff of subarrays in array having greater sum and move in array with smaller sum and update the sum of both sub array.. continue dis process till sum become equal ... or n time..
note:- no same no. can be transfer in consecutive irritation...
eg.. if in some irritation x is transfer from arr1 to arr2
then in 2nd irritation x cant be transfer from arr2 to arr1..
other wise it form an infinite loop..
Here is my algo for this thingy:
1. Find the average of the array
2. Sort the array in ascending order
3. Pick the last element in the array (the biggest) and put it in subarray1
4. Keep on picking the elements from the beginning of the array untill the average of subarray1 becomes equal to the average of the original array. The elements remaining in the original array form the 2nd array.
[Note that there is no constraint in the original question to balance the arrays].
First compute the average of the entire array (lets call it 'avg')
Now start from a[0], see if a[0] == avg... then take avg of a[0] to a[1], see if its equal to avg.. and so on...
this will work, coz if 2 parts of a set have the same average, then the average of both parts is also the same!
#define N 5 main() { int arr[N] = {15,12,9,1,23}; int i; int sum = 0; float avg; /* Calculate avg of entire arr */ for (i = 0; i < N; i++) sum += arr[i]; avg = (float)sum / N; sum = 0; /* Compute moving average. (N - 1) is *not* a typo - we want to stop before putting in the last element */ for (i = 0; i < N - 1; i++) { sum += arr[i]; if (avg == (float)sum / (i+1)) { printf("Divide @ %d\n", i); return; } } printf("Arr is not suitable\n"); return; }Use cross-multiplication if you want to avoid the pesky floats...
- Bond December 25, 2007