## Microsoft Interview Question

• 0

Country: United States

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

this is a modification of subset sum algorithm where we keep track of
the size of subsets generated:

``````void generate_subset_sums(int *a, int sz, int N, int S) {
std::vector< int > sums(N + 1, 0);
std::vector< std::vector< int > > nparts(N + 1);
sums[0] = 1;
nparts[0].push_back(0);
for(int i = 0; i < sz; i++)
for(int s = N; s >= 1; s--) {
if(s < a[i] || sums[s - a[i]] == 0)
continue;
sums[s] = 1;
std::vector< int >& np = nparts[s - a[i]];
for(int j = 0; j < np.size(); j++) {
if(np[j] + 1 <= S) // do not count wrong sums
nparts[s].push_back(np[j] + 1);
}
}
for(int s = 1; s <= N; s++) {
printf("sums[%d] = %d [", s, sums[s]);
for(int j = 0; j < nparts[s].size(); j++) {
printf("%d ", nparts[s][j]);
}
printf("]\n");
}
}

int main() {
int a[] = {1,2,3,4,5,7};
int sz = sizeof(a)/sizeof(int);
generate_subset_sums(a, sz, 10, 3);
return 1;
}``````

then we get the following:
sums[1] = 1 [1 ]
sums[2] = 1 [1 ]
sums[3] = 1 [2 1 ]
sums[4] = 1 [2 1 ]
sums[5] = 1 [2 2 1 ]
sums[6] = 1 [3 2 2 ]
sums[7] = 1 [3 2 2 1 ]
sums[8] = 1 [3 3 2 2 ]
sums[9] = 1 [3 3 2 2 ]
sums[10] = 1 [3 3 3 2 ]

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

please explain the algo...its hard to understand from the code..

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

sums[s] == 1 if it's feasible to get a sum s using elements from the array a[] and 0 otherwise
parts[s] - lists the number of parts in each subset that sum up to s

for example, for 10 in the above program we have:3-element
subsets: 10 = 2+3+5 = 1 + 4 + 5 = 1 + 2 + 7

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

No good! Your function takes S as a parameter, as it should, but it's not used anywhere. You've effectively hard-coded the S=3 from the problem example, but S is not constant.

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

@garyspreder: nope have a look more carefully at the algorithm. In this line:

"if(np[j] + 1 <= S)"

I collect only those subset sums which have no more
than S elements. Then, the array nparts[N] contains the necessary information

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

First, we must try and get the subsets. Let n(A) be the size of the array. Then the number of subsets of size S is n(A) C S.
Then, we must evaluate each of the subsets.
This is the simplest and right solution.

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

so we must generate all the subsets of of size s and check that sum in N ?

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

@anonymous: how you wish to generate all the subsets ? with brute force you'd get exponential time algorithm ..
in my opinion we should modify subset sum DP solution to get pseudo-polynomial time algo

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

Hi below is my code let me know if anything is wrong

``````int a[]={1,2,5,1,6,4,9,7,0,3};

int s=3;//size of subset
int n=a.length;
int temp=0;
int expected_sum=9;
int j,i,k;

for( i=0;i<n;i++)
{temp=0;
for( j=i+1;j<(i+(s-1))&&j<n;j++)
{
temp+=a[i]+a[j];

}
for( k=j;k<n;k++)
{
expected_sum=temp+a[k];
if (expected_sum==9)
{
System.out.println("Elements are at the index"+i+--j+k);
}
}

}``````

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

This is like the 3sum problem. If integers in A are bounded, can use a bit array to represent A, then convolve with itself to find A^2, A^4 etc till A^S which can be done with O(log S) convolutions, each convolution using FFT with O(L log L) where L is the range of A. Then pick the value at N from A^S.

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

The idea is to use backtracking.

``````class Solution {
private int count = 0;
private int expect;
private int size;
private int len;
public int subsetsSum (int[] val, int expect, int size) {
this.expect = expect;
this.size = size;
this.len = vl.length - 1;
backtrack (0, 0, 0, val);
return this.count;
}

private void backtrack (int idx, int currentSize, int currentVal, int[] val) {
// If meet the end of the array
if (idx > this.len)
return;
// If find a solution
if (currentSize == this.size && currentVal == this.expect) {
count++;
return;
}

// Soltuions
// Get current value
backtrack(idx + 1, currentSize + 1, currentVal + val[idx], val);
// Do not get current value
backtrack(idx + 1, currentSize, currentVal, val);
}
}``````

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

A simple recursive function will do this,

``````function subArrs(\$arr, \$sum, \$size){
if(\$size <0)
return array();
if(\$size > 0 && sizeof(\$arr) <= \$size)
if(array_sum(\$arr)== \$sum)
return array(\$arr);
else
return array();
\$moreSubs = subArrs(array_slice(\$arr, 1), \$sum,\$size);
\$subs = subArrs(array_slice(\$arr, 1), \$sum-\$arr[0],\$size - 1);
if(!\$subs)
return \$moreSubs;
foreach(\$subs as &\$sub)
array_push(\$sub,\$arr[0]);
return array_merge(\$subs, \$moreSubs);
}``````

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

``````function subArrs(\$arr, \$sum, \$size){
if(\$size <0)
return array();
if(\$size > 0 && sizeof(\$arr) <= \$size)
if(array_sum(\$arr)== \$sum)
return array(\$arr);
else
return array();
\$moreSubs = subArrs(array_slice(\$arr, 1), \$sum,\$size);
\$subs = subArrs(array_slice(\$arr, 1), \$sum-\$arr[0],\$size - 1);
if(!\$subs)
return \$moreSubs;
foreach(\$subs as &\$sub)
array_push(\$sub,\$arr[0]);
return array_merge(\$subs, \$moreSubs);
}``````

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

``````def intTobinary(num):
binary = bin(num)
return binary[2:]

def subset(lst, resultSize, total):
size = len(lst)

numberOfSubsets = pow(2, size)

for count in range(0,(numberOfSubsets)):
binary = intTobinary(count)

while (len(binary) < len(lst)):
binary = '0' + binary

result = list()
for index in range(0,len(binary)):
if (binary[index] == '1'):
result.append(lst[index])
if (len(result) ==  resultSize and sum(result) == total):
print(result)

subset([1,2,5,3,6],3,9)``````

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

NP-hard?

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

``````package com.gen.trials;

//subsets for the set of 1,2,3,5,6

import java.util.ArrayList;
import java.util.List;

import org.omg.CORBA.NVList;

public class Subsets {
public static void main(String[] args) {
int desiredNumberofElementsInSubset = 3;
List<List> listOfSubsets = new ArrayList<List>();

List<Integer> s = new ArrayList<Integer>();
int setSize = s.size();
int numberOfSubsets = (int) (Math.pow(2, setSize));

String binaryStringOfIndex = "";
for (int i = 0; i < numberOfSubsets; i++) {
binaryStringOfIndex = Integer.toBinaryString(i);

//binary String for 0 is 0.
//but if we have 10 elements in the given list
//the binary string should also have 10 characters
//now list has four elements.
//so 0 becomes 0000, 1 becomes 0001.
//appending 4 (size of elements) - 1 (binarystring length)

int bValueSize = binaryStringOfIndex.length();
for (int k = 0; k < (setSize - bValueSize); k++) {
binaryStringOfIndex = "0" + binaryStringOfIndex;
}
//if u want subsets of size 3,
//loop should be run to only those
//binary strings with three 1's in the string

List<String> list = isRegExpressionExist(binaryStringOfIndex,"1");

if(list.size()== desiredNumberofElementsInSubset){
List<Integer> subset = new ArrayList<Integer>();
for (int j = 0; j < list.size(); j++) {
}
subset = null;
}
}

for(List l : listOfSubsets)
System.out.println("listOfSubsets : " + l);
}

private static List<String> isRegExpressionExist(String label, String regEx) {

ArrayList<String> mIndex = new ArrayList<String>();
int i = 0;
for (i = 0; i < label.length(); i++) {
int j = 0;
if (label.charAt(i) == regEx.charAt(j)) {
int k = i + 1;
j++;
for (; j < regEx.length(); j++,k++) {
if (label.charAt(k) != regEx.charAt(j)) {
break;
}
}
if (regEx.length() == j) {
}
}

}
mIndex.trimToSize();
return mIndex;
}
}

Note: if we want only the subsets whose sum to N, just add a small logic to add
the numbers in the subset Lists.I have only provided the logic to generate the
subsets of size M (here it is 3).
List of all subsets of size 3 will be as follows:

listOfSubsets : [5, 3, 6]
listOfSubsets : [2, 3, 6]
listOfSubsets : [2, 5, 6]
listOfSubsets : [2, 5, 3]
listOfSubsets : [1, 3, 6]
listOfSubsets : [1, 5, 6]
listOfSubsets : [1, 5, 3]
listOfSubsets : [1, 2, 6]
listOfSubsets : [1, 2, 3]
listOfSubsets : [1, 2, 5]``````

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

``````struct Node {
int data;
Node* parent;

Node(int d=0,Node* p=0):data(d),parent(p) {}
};
void reverse(vector<int>& A,int pos,int end,int S,int N,Node* pare,vector<int>& rult)
{
if (end-pos<N)
return;
if (N==1) {
for (int i=pos; i<end; i++)
if (A[i]==S) {
Node* r=new Node(A[i],pare);
while (r) {
rult.push_back(r->data);
r=r->parent;
}
delete r;
return;
}
return;
}
for (int i=pos; A[i]<(double)S/N && i<end; i++) {
Node* r=new Node(A[i],pare);
reverse(A,i+1,end,S-A[i],N-1,r,rult);
delete r;
}
}``````

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

Pretty sure you're responding to the rong questions here....

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

We can use backtracking to generate all the subset of a given set.
Prune our backtracking by putting a conditionally checking if the number of elements in each subset whose sum is S in equal to N

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

sid_tintin has a good idea of how to use binary numbers

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

private static int Subset(int[] ar, int sum, int subno)
{
int count=0, temp=0,index=0,subsum=0;
List<int>lt = new List<int>();
List<int> ult = new List<int>(lt);
Outer: for (int i = 0; i < subno-1; i++)
{
if (index + subno - 2 < ar.Length)
{
subsum = subsum + ar[i + index];
}
}

temp = sum - subsum;
if (!lt.Contains(temp) && ar.Contains(temp))
count++;
index++;
subsum = 0;
if (lt.Count()+1 == subno)
{
ult.Sort();
lt.Sort();
if (!ult.SequenceEqual<int>(lt))
ult = lt.ToList();
else
count--;

}
lt.Clear();

if(index < ar.Length)
goto Outer;
return count;
}

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

public static void sumset(int [] array,int n,int s){
int [] tmp=new int[s];
microSoft(array,0,n,s,tmp,0,0);
}

public static void microSoft(int [] array, int current, int n,int s, int [] tmp, int count,int index){

if (current==n&&count==s){
StringBuilder sb=new StringBuilder();
for (int val:tmp){
//System.out.print(val+"+");
sb.append(val);
sb.append(",");
}
sb.setLength(sb.length()-1);
System.out.println(sb.toString());
}else if (count>=s){
return ;
}else if (current>n){
return;
} else{
for (int i=index;i<array.length;++i){
tmp[count]=array[i];
current+=array[i];
microSoft(array,current,n,s,tmp,count+1,++index);
current-=array[i];
}
}
}

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

``````public class  Test {

public static void backtrackSum(int[]A , int N , int S,int sum,int indx) {

if (sum == N && S == cnt) {

for (int j = 0 ; j < cnt ; j++)
System.out.print(p[j]+"  ") ;

System.out.println("") ;
return ;

}

for (int i = indx; i <A.length; i ++)
if ( sum+A[i] <= N ) {
sum+=A[i] ;
p[cnt++] =A[i] ;

backtrackSum(A,N,S,sum,i+1);
sum-=A[i] ;

cnt--;

}
}

public static void main(String ...args) {

// backtrackSum(A[],N,S,0,indx);

backtrackSum(new int [] {1,2,5,3,6},9,3,0,0);

}

}``````

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.