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 ?

Find out the 2nd largest number in a list of numbers

Assume the numbers are not sorted

int SecondLargestNumber(vector<int> v)
{
int LargestNumber = INT_MIN;
int SecondLargestNumber = INT_MIN;

        if (v.size() < 2)
        {
               return SecondLargestNumber;
        }

for (int index = 0; index < v.size(); index++)
{
if ((v[index] > LargestNumber) || (v[index] > SecondLargestNumber))
{
if ((v[index] < LargestNumber) && (v[index] > SecondLargestNumber))
{
SecondLargestNumber = v[index];
}

if (v[index] > LargestNumber)
{
SecondLargestNumber = LargestNumber;
LargestNumber = v[index];
}
}
}
   return SecondLargestNumber;
}

Pangram

interesting interview question
write a function to determine if a string is a pangram
pangram is defined as a string that has all the alphabets A to Z
it does not matter whether the characters are lower case or upper case

My Solution
Create an array of 26 booleans - one for each alphabet
set it to true each time you detect the alphabet
check at the end

bool IsPangram(string s)
{
bool flag[26];
int temp;

for (int index = 0; index < 26; index++)
{
flag[index] = false;
}

    for (int index = 0; index < s.length(); index++)
    {
temp = (int)tolower(s[index]) - 97;
flag[temp] = true;
printf("%d", tolower(s[index]));
    }
printf("\n");

for (int index = 0; index < 26; index++)
{
if (flag[index]==false)
{
return false;
}
}

return true;
}

One of the discoveries I made was that C++ standard library had an array container. It would simplify the initialization

  std::array<bool,26> myarray;

  myarray.fill(false);

Future of Pay Television

Folks who subscribe to paid video content will be using one of these means -  satellite television, traditional cable (include comparable IPTV offerings from the telcos), OTT services (Netflix, Hulu Plus, Amazon Prime, HBO Go etc.)

Satellite television is here to stay. For one the satellite television providers have a national reach. In some cases they have an international reach. DirecTV and Dish can sign up any household in USA. In contrast Comcast does not have a pipeline into majority of the households in USA.

Traditional Cable is a dying market. It is like the landline telephone market in 1999. Comcast has tried to make themselves relevant by purchasing content providers. One major difference from the landline telephone analogy Comcast still owns the broadband pipe.

The OTT players are the future in the long run. Netflix has taken the lead. The big issue for the OTT players is content. They are at the mercy of the Hollywood Studios who still get more revenue from Satellite and Traditional Cable subscribers. The obvious strategy of Netflix is to get bigger in terms of subscriber base. This would allow them to negotiate better deals with the content providers. In theory the content providers could offer a Netflix style service to undercut Netflix.

The wildcards in the future of pay television market are improvements in the wireless network capabilities, interpretation of net neutrality by the different players, legality of the bandwidth caps, broadband networks in emerging market and consolidation of content providers.

Currently there are two choices for broadband access in USA - your local cable company or your local telephone company. Improvements in the wireless network should allow for cellular carriers to stream video from OTT services to subscribers. That would add a third choice. It would improve the prospects for OTT players.

Net neutrality is influenced by politics. Generally the Republicans favor the incumbents - cable companies and telcos. The Democrats favor the Silicon Valley and the venture capitalists. The last time politics played out was in 2001. The election of the Bush in 2001 sealed the fate of the CLEC - competitive local exchange carriers.

Bandwidth caps is an hard issue. Moving to 4K content increases the pressure on the networks. It is going to be hard to increase the bandwidth available for video streaming unless consumers pay for it. That works in the favor of the cable/telco offerings.

The quality of the Broadband networks in emerging markets is poor. In general the quality and bandwidth is not suitable for unlimited video streaming. This should limit the expansion plans of the OTT players like Netflix.

Right now most of the content is owned by Comcast, Disney, CBS, Viacom, News, Time Warner and Liberty Media. It is hard for any new entrant to build a large content library to compete with the existing players

In short look for slow and steady gains in OTT subscribers in contrast to slow steady declines in subscribers to the traditional pay television industry.

A program to detect if an expression is valid

An expression is valid only if the various paranthesis { [ ( are matched and nested correctly
Write a function to see if they are matched

Solution
I used a stack to store the left facing symbols. If I detected the right facing symbols ), ] and } I checked the stack for the left facing symbols (, {, [

   bool isValid(string s)
   {
        bool flag = true;
        stack<char> sp;
       
        for (int index = 0; index < s.length(); index++)
        {
            if ((s[index]=='[')||(s[index]=='{')||(s[index]=='('))
            {
                sp.push(s[index]);
            }

            if (s[index]==']')
            {
if (sp.empty())
{
return false;
}
                if ((!sp.empty()) && (sp.top() != '['))
{
                    return false;
}

if ((!sp.empty()) && (sp.top() == '['))
{
sp.pop();
}
            }

            if (s[index]=='}')
            {
if (sp.empty())
{
return false;
}
                if ((!sp.empty()) && (sp.top() != '{'))
{
                    return false;
}

if ((!sp.empty()) && (sp.top() == '{'))
{
sp.pop();
}
            }

            if (s[index]==')')
            {
if (sp.empty())
{
return false;
}
                if ((!sp.empty()) && (sp.top() != '('))
{
                    return false;
}

if ((!sp.empty()) && (sp.top() == '('))
{
sp.pop();
}
            }

        }

        if (sp.empty() != true)
        {
            return false;
        }
        return flag;
    }