## Microsoft Interview Question for Software Engineer / Developers

• 1
of 1 vote

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

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...

Comment hidden because of low score. Click to expand.
3

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

Comment hidden because of low score. Click to expand.
0

This would fail in an array sorted in ascending or descending order. A fail safe method would be to find total sum in first parse and then go on subtracting from left and adding to right with each iteration and calculating avg with whichever method you like

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

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.

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

Suppose u have an array {1,2,4,5} U divide it into {1,5} and {2,4}. U get the average same.
If the array {1,2,3,6,5} is subdivided into {2,3,5} and {1,6} the average would be 3.33 and 3.5. In this case, the average can't be equal.

What exactly is expected in this case?

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

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.

Comment hidden because of low score. Click to expand.
0

Oops. I didn't read this problem correctly. It said Average.

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

Raja you algo wont work for this input
3 5 9 11 15 20

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

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

Thanks,
Rohith

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

@rohith good work

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

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);

}

}

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

its a NP problem
subset sum problem

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

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];

Comment hidden because of low score. Click to expand.
0

// if sum is odd, no such equal partition exists
The problem never states that the partitions must be equal.

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

I don't get the problem well let say we have 100,0,1 how one can divide it into two such subarray?

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

You can't divide in that case, you poor man!

Comment hidden because of low score. Click to expand.
0

lol............

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

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)

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

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)

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

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)

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

This is a famous balanced partitioning . Its best approach is to use Dynamic Programming. Find it on Google.

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

Balanced partitioning is just about dividing into two subsets with equal sums(?). This has more constraint.

"Rohith Menon on August 18"'s solution is pretty close.

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

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);

}``````

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

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);

}

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

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);
}

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

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.

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

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;

}``````

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

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..

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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].

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.

### 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.

### 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.

### 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.