Microsoft Interview Question


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 +

- xxx April 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- light May 21, 2012 | Flag
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) + "+");
			}
		}
	}
}

- VadimM April 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Where prevPrint got updated?

- Anonymous April 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Can you elaborate the question?

- saikrishna chunchu April 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- 111 April 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- saikrishna chunchu April 18, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- ps April 18, 2012 | Flag
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;
}

- Ethan April 23, 2012 | Flag Reply
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

- Hemanth Muttevi April 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous April 17, 2012 | Flag
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

- Hemanth Muttevi April 17, 2012 | Flag Reply
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."

- Hemanth Muttevi April 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous April 17, 2012 | Flag
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

- milo April 17, 2012 | Flag Reply
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;
}

- kubrick April 17, 2012 | Flag Reply
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.

Intermdeiate array stores already added numbers.

- Anonymous April 17, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

nice coneversion of knapsack problem ...

- Anonymous April 18, 2012 | Flag Reply
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;
}
}


}

- Scott April 19, 2012 | Flag Reply
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);
	}

- Anonymous April 22, 2012 | Flag Reply
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?

- code_guru May 03, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Looks okay.

- channa May 04, 2012 | Flag
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();
        }

- Anonymous May 18, 2012 | Flag Reply
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

- light May 22, 2012 | Flag Reply
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();
			}

		}
	}

- samya June 02, 2012 | Flag Reply
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)

- Anonymous June 22, 2012 | Flag Reply
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];
}

- plagiariser July 29, 2012 | Flag Reply
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

- Aashish July 29, 2012 | Flag Reply
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;
}

- Anonymous September 02, 2012 | Flag Reply
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 }

- cjmemory September 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 }

- cjmemory September 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The two programs above both work well for the problem.

- cjmemory September 30, 2012 | Flag
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);
}

- Anwar November 03, 2012 | Flag Reply
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);
	}

- GKalchev June 07, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous June 08, 2012 | Flag


Add a Comment
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.

Learn More

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.

Learn More

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.

Learn More

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.

Learn More