Interview Question - how do print out all the items in a power set for a given set

Given a set {a, b, c} how do you print out all elements of the power set

If a set has N items the power set has 2 to the power N items in it
That includes the null set

Solution

    int powerSet;
    powerSet=pow(2,N);
    for(i = 0; i<(powerSet);i++)
   {
        for(j=0;j<N;j++)
{
                 if((i & (1<<j)))
 {
                  printf("%c ",y[j]);
                 }
        }
        printf("\n");
    }          
    printf("\n");

Explanation

The outer loop executes 2^N times. Each item it prints one element in the power set S.

The inner loop uses the condition i & (1<<j) to determine whether to print individual items for the element of the power set

Dynamic Programming versus Recursion

I want to illustrate how efficient dynamic programming is compared to recursion

A man is running up a staircase with n steps, and can go either 1 steps or 2 steps at a time. Now write a program to count how many possible ways the child can run the stairs.

Implemented a program using recursion
int Stairs(int n)
{
int count = 0;

if (n <= 1)
return 1;

return Stairs(n-1) + Stairs(n-2);
}

Implemented a program using Dynamic Programming

int StairsDP(int n)

{
vector<int> count;
count.reserve(n);
int temp;

count.push_back(1);
count.push_back(1);

if (n <= 1)
return 1;

for (int index=2; index <= n; index++)
{
temp = count[index-1] + count[index-2];
count.push_back(temp);
}

return count[n];

}

Collected some timing on my personal computer

Recursion
10 0.214255 ms.
20 0.240877 ms.
30 6.01229 ms.

Dynamic Programming
10 0.0971846 ms.
20 0.0538845 ms.
30 0.0535638 ms.

You see substantial improvements in efficiency for small values of n

Cryptic Compiler Error Messages

I had a piece of code with obvious typo

int main
{
foo * p;
p = new bar();
p->f1();

return 1;
}


The compiler messages were cryptic

g++ -std=c++11 c10.cpp -o c10

c10.cpp:48:6: error: expected primary-expression before '*' token
  foo * p;
      ^
c10.cpp:48:8: error: 'p' was not declared in this scope
  foo * p;
        ^
c10.cpp:48:9: error: expected '}' before ';' token
  foo * p;
         ^
c10.cpp:49:2: error: 'p' does not name a type
  p = new bar();
  ^
c10.cpp:50:2: error: 'p' does not name a type
  p->f1();
  ^
c10.cpp:52:2: error: expected unqualified-id before 'return'
  return 1;
  ^
c10.cpp:53:1: error: expected declaration before '}' token
 }
 ^

Can the compiler messages be made better ?