## Microsoft Interview Question for Software Engineer / Developers

• 0

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

Loop(i=1 to N of Set {N})
Loop(j=1 to M of Set {M})
Loop(k=1 to M of Set {M})
if( j == k)
print {N[i]};
print {M[k]};
End Loop
End Loop
End Loop

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

I dint quite understand the question !
By 'in sequence', do you mean the M elements should be contiguous in the input array.... eg:
INPUT: abcdefghij n=10 m=5
OUTPUTS: abcde, bcdef, cdefg, defgh.....

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

this is so called gray-code combinations, don't ask me why it works
personally I don't understand it completely, it's magic ;))

``````int N = 7;    // number of bits in words
int K = 3;    // number of bits in words
int *x;  // elements in combination at x[1] ... x[k]

void visit() // prints out one combination
{
for(int j = 1; j <= K; j++)
printf("%d ", x[j]);
printf("\n");
}

void comb_gray(int n, int k, bool z)
{
if(k == n) {
for(int j=1; j<=k; ++j)
x[j] = j;
visit();
return;
}

if(z) {// recurse in forward direction
comb_gray(n-1, k, z);
if(k > 0)  {
x[k] = n;
comb_gray(n-1, k-1, !z);
}
} else { // backward direction:
if(k > 0) {
x[k] = n;
comb_gray(n-1, k-1, !z);
}
comb_gray(n-1, k, z);
}
}

main() {
x = new int[N+1];
comb_gray(N, K, 1);
}``````

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

the Gray codes have the property of differing only in one bit for each consecutive numbers.
e.g. gray code for numbers up to 7 is:

000 : 0
001 : 1
011 : 2
010 : 3
110 : 4
111 : 5
101 : 6
100 : 7
We prepare Gray codes for the number as done above, and
then output the parent set-member if that particular bit position in gray code is '1'. :)
P.S. getting Gray code is not hard either can be achieved
using XOR for consecutive regular bit positions of
standard binary representation.

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

map all N elements to a bit in a number...creating a N bit number

int start = no with all M lower bits set;
while (start < ( pow(2,N-1) - 1))
{
print elements whose 1 bit is set.
}

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

Excellent, you are a genius!

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

I am amazed checking this solution. King_k, excellent idea.

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

This method won't work. Suppose we have 5 elements and output a combination of 3.
Now start = 01110, which means we output the middle three elements. Next start which is greater and also with same 1 count is 10011, which differ from the previous in two positions.

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

can any one pls eloborate on King_K's logic

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

In kings solution..i guess it shoud be start<=pow(2,N)-1

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

Can someone please explain King's solution with an example?

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

To do it a simpler way we can follow the bit pattern from 1 to 2^N-1.
As we increment,we can checks number of 1s set in that pattern.
If its equal to M, then print it else skip it.

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

using the bit sets logic for printing all combinations

Step 1: finding first m-1 bits to avoid and start from there.
step 2: finding the bits set in next number onward. Then set a BitArray for the same bits. Then counting total bits set in the BitArray.
step 3: if the count of bits set is m, then start printing them , else reset the
BitArray and start step 2.

``````public static void CombinationsOfMoutOfN(char []set,int m)
{

int n = set.Length;
int powerSet = (int)Math.Pow(2, n);
int skippingFirstMminusbits = (int)Math.Pow(2, m) - 1;
BitArray bitArray = new BitArray(n, false );
for (int i = skippingFirstMminusbits; i < powerSet; ++i)
{
int count = 0;
for (int j = 0; j < n; ++j)
{
//this is the logic
if ((i & (1 << j)) > 0)
{
count++;
bitArray[j] = true;
}
else
bitArray[j] = false;
}
if (count == m)
{
for (int j = 0; j < n; ++j)
{
if (bitArray[j] == true)
{
Console.Write(set[j]);
bitArray[j] = false;
}
}
}
count = 0;
Console.WriteLine("");
}``````

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.