Microsoft Interview Question
Software Engineer / Developersthis 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);
}
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.
map all N elements to a bit in a number...creating a N bit number
start with a number with all the lower M bits set...
int start = no with all M lower bits set;
while (start < ( pow(2,N-1) - 1))
{
print elements whose 1 bit is set.
start = no greater than start with same 1 count
}
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.
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("");
}
Loop(i=1 to N of Set {N})
- sunny June 15, 2007Loop(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