## Microsoft Interview Question

• 0

Country: United States

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

this is a special case of a more general partition problem that can be formulated as follows. Find all partitions of an integer 'x' with respect to V = {v[0], ..., v[n-1]}
In other words:

x = c[0]*v[0] + ... + c[n-1]*v[n-1] where each c[i] >= 0 and v[i] <= x.

Accordingly, in our case, say for x = 8
we have: V = {1, 3, 5, 7} since we are only interested in odd parts.

The general problem, as I stated it, can be solved using a simple recursive algorithm:
- suppose we are given an integer 'x'
- take v[i], partition recursively the number y = x - c[i]*v[i]
using parts v[0]..v[i-1] for all possible multiples c[i], i.e.
c[i] goes from 1 to floor(x / v[i])

``````int V[] = {1,3,5,7,9};  // which parts to use
int nv = sizeof(V) / sizeof(int);
static int cnt = 0;
std::vector< int > part; // container for partitions

// here i is the index in the array V the next part to be used
void generate_partitions(int x, int i) {
if(x == 0) { // found a partition
printf("%d: ", ++cnt);
for(int j = 0; j < part.size(); j++) {
printf("%d + ", part[j]);
}
printf("\n");
return;
}
for(int j = i; j >= 0; j--) {
int v = V[j];
int y = x, c = 0;
while(y >= v) {
part.push_back(v);
y -= v; c++;
generate_partitions(y, j-1);
}
while(c--) // remember how many times we pushed 'v'
part.pop_back();
}
}

int main() {
int x = 11;
generate_partitions(x, nv-1);
return 1;
}``````

and the output:

1: 9 + 1 + 1 +
2: 7 + 3 + 1 +
3: 7 + 1 + 1 + 1 + 1 +
4: 5 + 3 + 1 + 1 + 1 +
5: 5 + 3 + 3 +
6: 5 + 1 + 1 + 1 + 1 + 1 + 1 +
7: 5 + 5 + 1 +
8: 3 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 +
9: 3 + 3 + 1 + 1 + 1 + 1 + 1 +
10: 3 + 3 + 3 + 1 + 1 +
11: 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 +

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

where is 11??

``````def oddpart(n,l,par):
global num
if n==0:
num+=1
print num, par
return

for i in range(l,n+1,2):
par[id(1)]-=i
par[id(i)]+=1
oddpart(n-i,i,par)
par[id(1)]+=i
par[id(i)]-=1``````

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

This can be done with recursion. The only trick is to make sure that the next element of the sum is not greater than the previous (otherwise it will generate duplicates).

``````public class OddPrinter {

public static void main(String[] args) {
printOdd(8, Integer.MAX_VALUE, "");
}

public static void printOdd(int n, int prevPrint, String s){
for (int i=1;i<=n;i+=2){
if (prevPrint >= i) {
if (n-i == 0) {
System.out.println(s + Integer.toString(i));
} else
printOdd(n-i, i, s + Integer.toString(i) + "+");
}
}
}
}``````

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

Where prevPrint got updated?

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

Can you elaborate the question?

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

sorry for confusion, I mean print all integer partitions of a given number in odd parts (not compositions, i.e. order does not matter).

for example, given n = 8:
we have 8 = 7 + 1, 8 = 5 + 3, etc.

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

``````Here is the solution in JAVA
public static void compositions(int num){

for(int i =1;i<num;i +=2){
int rem = num%i;
int divident  = num/i;

if(rem%2 !=0)
System.out.print(rem);

if(rem ==0 || rem%2 !=0){

//				Print the composition based on divident
for(int j=divident;j>0;j--)
System.out.print("+"+i);
System.out.println("");
if(i>1){
//				get the i in 1s
String iIn1s = "";
for(int temp=i;temp>0;temp--)
iIn1s += "+"+1;

for(int j=1;j<divident;j++){
if(rem%2 !=0)
System.out.print(rem);
for(int k=j;k>0;k--)
System.out.print(iIn1s);

for(int l=(divident-j);l>0;l--)
System.out.print("+"+i);

System.out.println("");
}

}

}

}
}``````

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

The code pasted above gave me the following output. It did not give all the compositions.
+1
+1
+1
+1
+1
+1
+1
+1

3
+5

1
+7

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

void generateOdd(int n, vector<int> &result)
{
if ( n == 0 )
{//print result
int len = result.size();

for ( int i = 0; i<len-1; i++)
cout<<result[i]<<"+";

cout<<result[len-1]<<endl;
}
int min = n;
if ( result.empty() == false )
min = *(result.end() - 1);

for ( int j = n > min ? min : n; j>0; j--)
{
if ( (j & 0x1) == 0 )
continue;

if ( n - j > -1 )
{
result.push_back(j);
generateOdd(n-j, result);
result.pop_back();
}
}
}

int _tmain(int argc, _TCHAR* argv[])
{
vector<int> res;
generateOdd(11, res);
return 0;
}

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

see above is nothing but a different form of knapsack problem which sum to particular weight.. here total weight is 8 and values are natural numbers.... search google for fractional knapsack problem .. Now the algo is everywhere all you need to do is code in your known language....

Hemanthed

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

can you please elaborate more on that ?
from my knowledge knapsack (in whatever form it is given) is an *optimization* problem where you need to maximize the load using some set of items.

I am not sure how you can modify knapsack algo to get *exactly* a particular wieght

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

see above is nothing but a different form of knapsack problem which sum to particular weight.. here total weight is 8 and values are natural numbers.... search google for fractional knapsack problem .. Now the algo is everywhere all you need to do is code in your known language....

Hemanthed

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

see let the sum 8 be maximum weight ....
and our denomination to make such a sum be 1,2,3,4,5,6,7,....... k where k<sum here k is less than 8 so k=7.
now print all the maximum possible sets of find sum 8 from giving denominations...
u can do this problem with dynamic programming also.....
see following link so that you will get an idea ..."ww.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Greedy/greedyIntro."

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

I am still not sure whether you are referring to fractional knapsack algorithm where a greedy strategy works ?
or to the DP algorithm to find if it's possible to supply a change using coins with certain denominations ?

I think neither of these algorithms apply to this problem because, for example, the DP algorithm just provides you with the answer if it's *feasible* to supply a change but does not give you all possible ways (partitions) to do that

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

find all the odds less than n, and bfs or dfs without marking the odd is used or not

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

``````/**print all compositions of a number in odd parts, i.e. for n = 8:
7 + 1
5 + 3
5 + 1 + 1 + 1
3 + 3 + 1 + 1
3 + 1 + 1 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1 + 1 + 1 + 1**/
#include<stdio.h>
#include<stdlib.h>

int *result;
int num;

void print_result(int *r,int init, int num)
{
int flag=0,i=0,temp;
//if(!r[init])
//  return;
printf("\n");

for(i=init;i<num;i++)
{
if(r[i])
{
temp=r[i];
if(!flag)
{
flag=1;
printf("%d",i);
temp--;
while(temp)
{
printf("+%d",i);
temp--;
}
}
else
{
while(temp)
{
printf("+%d",i);
temp--;
}

}
}
}
}

void get_all_odd_sums(int init, int start, int target)
{
if(start>target)
{
return;
}

if(start==target)
{

result[start]++;
print_result(result,init,num);
result[start]--;
return;
}
result[start]++;
// target-=start;
get_all_odd_sums(init, start,target-start);

result[start]--;
if(result[init])
get_all_odd_sums(init, start+2,target);

}
void print_all_odd_comb(int n)
{
int i,j;
result=(int *)malloc(n*sizeof(int));
for(i=0;i<n;i++)
{
result[i]=0;
}

for(i=1;i<(n/2);i+=2)
{
// printf("\ni=%d",i);
get_all_odd_sums(i,i,n);

}
}

int main()
{
//int num;
printf("n=");
scanf("%d",&num);

print_all_odd_comb(num);

return 0;
}``````

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

#include<iostream>
using namespace std;

#define N 11

void print_required_numbers(int intermediate[], int i_end, int start)
{
/* This condition is to avoid printing the sets which contains exactly one element as output*/
if( i_end == 1 && start == N)
return;

for(int i=0;i<i_end;i++)
{
cout<<intermediate[i]<<" ";
}

for(int j=start;j<N;j++)
{
cout<<1<<" ";
}

cout<<endl;

for(int k=start+2;k<N;k+=2)
{
/* This condition is to remove the duplicate set */
if( i_end-1 >=0 )
{
if( k-start+1 < intermediate[i_end-1] )
{
continue;
}
}
intermediate[i_end] = k-start+1;
print_required_numbers(intermediate,i_end+1,k+1);
}

}

int main()
{
int intermediate[N] = {0};
print_required_numbers(intermediate,0,0);
getchar();
return 0;
}

For better understanding just remove all if conditions and execute the program and look at output.
Again add all the if conditions and see the difference.

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

nice coneversion of knapsack problem ...

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

private static void Printer(int n,int cur, int []array,int count,int next){

if (cur==n){
for (int i=0;i<count;++i){
System.out.print(array[i]+";");
}
System.out.println();
}else if (cur>n){
return;
}else{
for (int i=1;i<n;i+=2){
if (i<next){
continue;
}
cur+=i;
array[count]=i;
Printer(n,cur,array,count+1,i);
cur-=i;
}
}

}

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

I used recursion. Use a vector<int> to the partial sum.

``````void solve(int n, vector<int>&v) {
int k = v.size();
if (n==0) {
ostringstream oss;
rep(i,k-1)
oss << v[i] << '+';
oss << v[k-1];
cout << oss.str() << endl;
return;
}
int curr = (k==0? n : v[k-1]);
curr = min(n,curr);
curr -= !(curr%2);
for (int i = curr; i >0; i-=2) {
v.push_back(i);
solve(n-i,v);
v.resize(k);
}
}

void  odd_sum(int n)
vector<int> v;
solve(n,v);
}``````

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

print_comb(int n,int sum,int a[],int x)
{
for(int i=1:i<n;i+=2)
{
sum+=i;
a[x++]=i;
if(sum == n)
{
for(int j=0;j<x;j++)
printf("%d ",a[j]);
printf("\n");
} else if (sum > n) {
return;
} else {
print_comb(n,sum,a,x);
}
}
}

Initial call:print_comb(8,0,a[20],0)

This is raw code.Given for checking the logic.If there is any flaw in logic?

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

Looks okay.

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

``````PrintOddCombination.print(new int[8], 0, 8, 1);
public static void print(int[] arr, int len, int num, int start)
{
if (num == 0)
{
printArray(arr, len);
return;
}

int i = 0;
for (i = start; i <= num; i = i + 2)
{
arr[len++] = i;
print(arr, len, num - i, i);
len--;
}
}

public static void printArray(int[] arr, int len)
{
for (int i = 0; i < len; i++)
{
System.Console.Write(" " + arr[i]);
}
System.Console.WriteLine();
}``````

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

``````def oddpart(n,l,par):
global num
if n==0:
num+=1
print num, par
return

for i in range(l,n+1,2):
par[id(1)]-=i
par[id(i)]+=1
oddpart(n-i,i,par)
par[id(1)]+=i
par[id(i)]-=1``````

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

Here is the working java solution based on the partition algorithm described above

``````public static void main(String[] args) {
int no = 8;
generateSum(8);
}
// populate this array with all the odd numbers till
// the given no like following
static int V[];
static Stack<Integer> s = new Stack<Integer>();

static void generateSum(int no) {
V = new int[no/2+1];
for(int i=0; i<V.length;i++)
V[i] = 1+i*2;

printSumCombination(no, V.length-1);
}

static void printSumCombination(int no, int index) {

if(no==0 && index ==-1) {
for(Object n: s.toArray())
System.out.printf("%d ", n);
System.out.printf("\n");
return;
}

for(int i = index; i>=0;i--) {
if(no==0) {
for(Object n: s.toArray())
System.out.printf("%d ", n);
System.out.printf("\n");
return;
}

int x = no;
int c = 0;
// adding the same integer multiple times and calling for next
// combination
if(x<V[i]) {
printSumCombination(x,i-1);
return;
} else {
while(x>=V[i]) {
x=x-V[i];
s.push(V[i]);
c++;
printSumCombination(x,i-1);
}
// popping out all the occurrences of this integer form the stack as
// all the combination pertaining to this integer is covered
while(c-->0)
s.pop();
}

}
}``````

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

I guess it is another fib variant.
as
f(7)=f(5)+f(3)
f(5)=f(3)+f(1)

also I guess there must be some relation btw f(2n) and f(2n-1)

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

Let Ways[i][j] represent no of ways of partitioning i such that using minimum value of j
Ways[i][j] = Ways[i-j][j] + Ways[i][j+2]
So need to find Ways[n][1] .

int CountWays(int N) {

int i, j, k;
int size = N+1;
int W[size][size];
for (i = 0; i < size; ++i) {
for (j = 0; j < size; ++j) {
W[i][j]=0;
}
}
int start;
if(N%2 ==0)
start=N-1;
else
start=N;

for (i = 0; i <size; i++) {
for (j=start; j >=0; j-=2) {
if(i<j)
W[i][j] = 0;
else if(i==j)
W[i][j] = 1;
else
W[i][j] = W[i-j][j] + W[i][j+2];
}
}

return W[N][1];
}

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

``````void foo(int* res,int depth,int N,int tillnow)
{
int i;
if(tillnow==N)
print(res,depth);
else if(tillnow>N)
return;
else
{
for(i=N&1?N:(N-1);i>=1;i-=2)
{
if(!depth || i<=res[depth-1])
{
res[depth]=i;
foo(res,depth+1,N,tillnow+i);
}
}
}
}``````

Complete code here: ideone.com/tyxoZ

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

void printComposition( int n ){
if( n == 0){
return;
}
else if( n == 1){
cout << n << " ";
}
else{
if( n % 2 == 0 ){
printComposition( n - 1);
cout << " + ";
printComposition( 1 );
}
else{
printComposition( n - 2 );
cout << " + ";
printComposition( 2 );
}
}
}
int main(){

for(int i = 0; i <= 10; i++){
printComposition( i );
cout << endl;
}
return 0;
}

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

``````1 #include <iostream>
2 #include <vector>
3
4 using namespace std;
5
6 void printComp(int arr[], int len, vector<int> &vec, int N) {
7     if(arr==0||len<0||N<0) return;
8
9     if(0 == N) {
10         for(int i = 0; i < vec.size(); i++)
11             cout << vec[i] << " ";
12         cout << endl;
13         return;
14     }
15     for(int i = 0; i < len; i++) {
16         vec.push_back(arr[i]);
17         printComp(arr+i, len-i, vec, N-arr[i]);
18         vec.pop_back();
19     }
20 }
21
22
23 int main() {
24     int N = 8;
25     int arr[N/2];
26     for(int i = 0; i < N/2; i++)
27         arr[N/2-1-i] = 2*i+1;
28
29     for(int i = 0; i < N/2; i++)
30         cout << arr[i] << "->";
31     cout << endl;
32
33     vector<int> vec;
34     printComp(arr, N/2, vec, N);
35
36     return 0;
37 }``````

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

``````1 #include <iostream>
2 #include <vector>
3
4 using namespace std;
5
6 void printComp(int arr[], int len, vector<int> &vec, int N) {
7     if(arr==0||len<0||N<0) return;
8
9     if(0 == N) {
10         for(int i = 0; i < vec.size(); i++)
11             cout << vec[i] << " ";
12         cout << endl;
13         return;
14     }
15     /*
16     for(int i = 0; i < len; i++) {
17         vec.push_back(arr[i]);
18         printComp(arr+i, len-i, vec, N-arr[i]);
19         vec.pop_back();
20     }
21     */
22     vec.push_back(arr[0]);
23     printComp(arr, len, vec, N-arr[0]);
24     vec.pop_back();
25     printComp(arr+1, len-1, vec, N);
26 }
27
28
29 int main() {
30     int N = 8;
31     int arr[N/2];
32     for(int i = 0; i < N/2; i++)
33         arr[N/2-1-i] = 2*i+1;
34
35     for(int i = 0; i < N/2; i++)
36         cout << arr[i] << "->";
37     cout << endl;
38
39     vector<int> vec;
40     printComp(arr, N/2, vec, N);
41
42     return 0;
43 }``````

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

The two programs above both work well for the problem.

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

#include <iostream>
#include <vector>
using namespace std;

vector<int> odd_parts;

/*
recursive print_odd_parts method
paramaters:
r: remaining part the number, for which we compute odd parts.
d: position of current odd number in the odd number list
m: max odd number we can start with.
m is used to print combination, not the permutation.
example: we print 8=5+3+1, but skip 8=3+5+1.

*/
void print_odd_parts(int r, int d, int m)
{

if(r== 0)
{
cout << odd_parts[0];
for(int j=1; j < odd_parts.size(); j++)
if(odd_parts[j] > 0)
cout << "+" << odd_parts[j];

cout << endl;

return;
}

int largest_odd_number = m % 2 == 0? m-1:m;

for(int i = largest_odd_number; i >=1; i-=2)
{
if(d == 0)
{
for(int j=0; j < odd_parts.size(); j++)
odd_parts[j] = 0;
}

odd_parts[d] = i;
m = r-i<=i?r-i:i; // this generates combination
// m = r-i; this generates permutation.

print_odd_parts(r-i, d+1,m);
}
}

int main()
{
int n = 11;
odd_parts.resize(n);
cout << "odd parts of " << n << endl;
print_odd_parts(n, 0,n);
}

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

Here is a java code that generate it:

``````private static void printCombinations(int n, String currResult, int startI) {
if (n == 0)
System.out.println(currResult);
else if (n > 0) {
for (int i = startI; i > 0; i-= 2)
printCombinations(n - i, currResult + i
+ (n - i == 0 ? "" : " + "), i);
}
}

public static void printCombinations(int n) {
int startI = n;
if (startI % 2 == 0)
startI--;
printCombinations(n, "", startI);
}``````

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

``````public static void backtrack(int x,int sum,int in) {

if (sum == x) {

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

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

}

for (int i = in; i >=1; i-=2)
if ( sum+i <= x ) {
sum+=i ;
p[cnt++] =i ;

backtrack(x,sum,i);
sum-=i ;

cnt--;

}

}

backtrack(x,0,x%2==0?(x-1):x);``````

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.