Microsoft Interview Question for Software Engineer in Tests


Country: India




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

DP:
1. For any element, it can be 0 or non-0.
a. if 0, the number should be n-1 element.
b. if non-0, it can be 1..n. Then the n-1 sum of other n-1 should be 20-num

and merge it together:

int FindNumber(int n, int sum)
{
int tmpSum = 0;

//base
if (n == 1) return 1;
if (n == 0 ) return 0;

for (int i = 0; i<n; i++)
{
for (int j = 0; j<sum; j++)
tmpSum += FindNum(n-1, sum-j);
}
}

- wave October 20, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

approach is fine, but
(1) this is recursive, not DP
(2) need to return tmpSum in the method

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

For the same question (x1+x2+x3+x4+X5=20), if only non-zero non-negative integrals(natural numbers) were allowed, then we can formulate it as follows.
In such a case the number of solutions reduce to the number of ways in which we can make 5 partitions by drawing four lines in between
1111111111111111111 (20 1's.)
We can sum up each partition independently. This avails, any 4 locations (for 4 lines) amongst 19 gaps(between 20 1's there are 19 gaps, where we draw the lines.)

Therefore the answer is 19C4.

Using the above idea we can deduce that if 0's are allowed, then the number of combinations increases to 24C4.(Because we can keep the lines together as well.)

- DH October 23, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

that's integer partition problem. Should be some DP solution

- Anonymous October 19, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

can we find the substructure . i dont think that this problem has substructure property .

- anon October 19, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

suppose p(k,n) denotes the number of partitions of n into at most k parts.

Hence, we have p(0,n) = 0, p(1,n) = 1, p(n,n) = 1.
How to come up with a recursive formula ?

- Anonymous October 19, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

we dont need 5 loops ,we can do in just 4 loops.

int  find()
{
    int total=0;
     for(int i=0;i<=num;i++)
     {
        for(int j=0;j<=num;j++)
        {
            if(i+j>num)
            break;
            for(int k=0;k<=num;k++)
            {
                 if(i+j+k>num)
                 break;
                 for(int m=0;m<=num;m++)
                  {
                      if(i+j+k+m>num)
                      break;
                      cout<<"\n"<<i<<"  "<<j<<"  "<<k<<"  "<<m<<"  "<<num-i-j-k-m;
                      total++;
                  }
            }     
        }
     }
     return total;
}

- techcoder October 19, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

this code, is much less expensive than the previous one. Thanks techcoder. How do they expect us to answer this question(which was the number of solutions) on paper?

- devanharikumar89 October 19, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Four loops five loops.Seriously??
Use recursion..

If u have to fit 20 in x1 -x5,
give pos =5 and n=20 to following program



int FindSol(int pos, int n)
{
int sum =0;
if(pos == 1)
{
return 1;
}
if(n == 0)
{
return 1;
}

for(int i= n;i > 0;i--)
{
sum = sum + FindSol(pos -1,i);
}
return sum + 1;
}

- TheGame October 19, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

You can use ordinary generating functions as well if you don't want to do the coding. It's a method from discrete mathematics.

- Anonymous October 20, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h> 


static int findNumSoln(int var, int desiredSum) 
{ 
        int totalSoln = 0; 
        /* assert (desiredSum>=0); */
        if (var == 1 && desiredSum >=0)  { return 1; } 
        for (int i =0 ; i<=desiredSum ; i++) { 
                totalSoln += findNumSoln(var-1, desiredSum-i); 
        }
        return totalSoln;
}

int main () 
{ 

int var = findNumSoln(5, 20 ) ; 

printf ("total num soln = %d\n", var); 

return 0; 
}

- Sps October 20, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This question has a formula :

var variableCount = 5;
var desiredSum = 20;
var totalSolutions = P(desiredSum+variableCount-1,variableCount-2);

where P = permutation

- Anonymous October 22, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

asm is right. 10626. How did u get that?

- Anonymous October 23, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Anonymous, P(desiredSum+variableCount-1,variableCount-2); is wrong.

- devan October 23, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think it is C(desiredSum+variableCount-1,variableCount-1), where C = combination

- sau2pen October 24, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n*k)

P(n, k)
	if(k == 1)
		return 1
	for each i from 0 to n
		for each j from 1 to k
			v = P(i, j)*P(n-i, k-j)
			s = s+v
	return s		

main()
	P(20,5)

- Prateek Caire November 28, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def findSum(sums, n, sol):
  if n == 1:
    print sol+str(sums)
  else:
    for s in range(sums, -1, -1):
      findSum(sums-s, n-1, sol+str(s)+"+")

findSum(sum, n, "")

- amshali February 25, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

It is simple math :

http: // en.wikipedia.org / wiki / Stars_and_bars_%28combinatorics%29

- amit.verma.ce February 27, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int fs(int S, int N,String stack)
{
if(S<0 || N==0)
return 0;
if(N==1)
{
System.out.println(stack + "+" + S);
return 1;
}
int ts=0;
for(int i=0;i<S;i++)
ts+=fs(S-i,N-1,stack + "+" + i);
return ts;
}


call is using : fs(20,4,"");

ans: 1540

- Aditya June 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

recursive solution:
public static int fs(int S, int N,String stack)
{
if(S<0 || N==0)
return 0;
if(N==1)
{
System.out.println(stack + "+" + S);
return 1;
}
int ts=0;
for(int i=0;i<S;i++)
ts+=fs(S-i,N-1,stack + "+" + i);
return ts;
}

call it: fs(20,4,"");
ans : 1540

- Aditya June 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

x1+x2+x3+x20

- noah tiamsin January 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

x1+x2+x3+x20

- noah tiamsin January 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

If the problem is this simple why not a nested loop. Have five loop variables going from 0 to 20. Print the loop variables if the current sum is 20.

for ( int i = 0; i <= 20;  ++i )
		for ( int j = 0; j <= 20;  ++j )
			for ( int k = 0; k <= 20;  ++k )
				for ( int l = 0; l <= 20;  ++l )
					for ( int m = 0; m <= 20;  ++m )
					{
						if ( (i + j + k + l + m) == 20 )
						{
							printf( "(%d %d %d %d %d %d) \n" , i , j , k , l , m );
						}
					}

- Anonymous October 19, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Anonymous, thanks for the code. But this question was asked as an objective question in a written test with options(i don't recall them. they were in the range of 10,000+) for the number of solutions. So there has to be a way we can work that out on paper.

- devan October 19, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

In a DP approach it would be lot of hard work to enumerate all solutions.

- Anonymous October 19, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@devanharikumar89: you said that this problem should be solvable
by pensil-and-paper ?

meaning that there is a simple formula for the number of solution
do you remember what was the answer ?
I suspect it should be: 21*22*23 = 10626 ?

- pavel.em October 20, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yup, I think we are asked to write down the solution number rather than develop some efficient code to count it. 23*22*21 should be the right answer.

- Jingxian October 22, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The answer is correct..
But how we got 21*22*23..
Can anyone explain?

- Anonymous October 24, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

its 24c4 = 21*22*23;
simply based on partitioning 24 values containing 4 zeros and 20 one into 5 group that is we need 4 divider. so it will be 24c4

- sk March 27, 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