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;
    }

What is the behavior of integer division in C++

I tried out this snippet

#include <stdio.h>                                                                                                                                                                                                                                                                                                        
int main()                                                                                                                                                   
{                                                                                                                                                                                                                                                                                                                                    
  int median1 = (8+9)/2;                                                                                                                            
  int median2 = (8+8)/2;                                                                                                                              printf("median1 %d median2 %d \n", median1, median2);                                                                                                                                                                                                                                        
  int median3 = (int)(8+9)/2;                                                                                                                     
  printf("median3 %d \n", median3);                                                                                                         
  return 0;                                                                                                                                                   
}                                                                                                                                                                 

The value for median1, median2 and median3 was 8

Will the result always be floor of the division ?

The answer is yes

C and C++ seem to truncate the fraction part of the quotient

Delete Node in a Linked List

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.

Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with value 3, the linked list should become 1 -> 2 -> 4 after calling your function.

Solution

It will work for all nodes except the tail node

    void deleteNode(ListNode* node) {                                   
                                                                                                
        if (node == NULL)                                                         
        {                                                                                      
            return;                                                                         
        }                                                                                       
        
        int temp = (node->next)->val;
        node->val = temp;
        
        node->next = (node->next)->next;
        
    }
};

Variable Length Array in C and C++

Traditionally C did not support variable length arrays. This is true for both K&R and C89 compilers.
The C99 standard introduced support for the variable length arrays.

The interesting part of this is that C++ never supported the variable length arrays.  If you needed the variable length arrays in C++ vectors in the standard library was your only option.


#include <stdio.h>
void foo(int n)
{
int arr[n];
printf("sizeof %d \n", sizeof(arr));
}

int main()
{
  foo(5);
}

The output of this program is 20

Common Errors in C programming language

In my ten plus years of C programming I make a lot of errors while typing programs. Some of them are syntax errors which are caught by the compiler. Some of them are not.

1. putting = instead of == in boolean expressions

2. Not explicitly casting parameters
This is usually caught by modern compilers in the form of warning messages.

3. Not handling integer overflows
If they are two unsigned integers x and y (x+y) will be positive if and only if (x+y) does not overflow

4. Not initializing variables
Not initializing variables leads to unpredictable results

5. Array subscripts
If you have an array of size n assigning a (n+1)th object should lead to a runtime error

Pitfalls of using Vectors incorrectly

I was implementing binary search and I run into an interesting problem in C++

        vector<int> nums;
        nums.reserve(30);
        nums[0] = 1;
        for (int index = 1; index < 30; index++)
        {
            nums[index] = // assign a random number
        }

        bool flag = binarySearch(v1, 57);


The problem with this code was:

I reserved memory for 30 elements and wrote into the memory. It looked like nums had 30 numbers written into memory. But the size was zero.




When I implemented a binary search function the size returned zero

bool binarySearch(vector<int>& nums, int k) 

{

...

high = nums.size();

...

}

Common Bit operations in Embedded C programming

Manipulating bits is common in embedded programming

The common operations are to set a bit, clear a bit, toggle a bit and check if a bit is set

unsigned int toggle(unsigned int x, unsigned int index)

{

x ^= 1 << index;

return x;

}

unsigned int SetBit(unsigned int x, unsigned int index)

{

unsigned int mask = 1 << index;

x = x | mask;

 

return x;

}

unsigned int ClearBit(unsigned int x, unsigned int index)

{

unsigned int mask = 1 << index;

x = x & ~mask;

return x;

}

bool IsBitSet(unsigned int x, unsigned int pos)

{

unsigned int mask = 1 << pos;

if ((x&mask))

{

return true;

}

return false;

}

Reverse digits of an integer

Reverse digits of an integer.

Example1: x = 123, return 321
Example2: x = -123, return -321

Solution

Make 

 int reverse(int x) 

 {

int  result = 0;

        

while (x!=0)

       {

if (result > INT_MAX/10 || result < INT_MIN/10)

               {

return 0;

}

result = (result*10) + (x%10);

                x= x/10;

}

        return result;

    }        

How to find if you strings are isomorphic

Given two strings s and t, determine if they are isomorphic.

Two strings are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.

For example,
Given "egg", "add", return true.

Given "foo", "bar", return false.

Given "paper", "title", return true.

Note:
You may assume both s and t have the same length.

Solution

bool IsIsomorphic(string s, string t)
{
map<char, int> smap;
map<char, int> tmap;
bool check = true;
if (s.length() != t.length())
{
        return false;
}

int len = s.length();
int index = 0;

while (index < len)
{
        char sch = s.at(index);
        char tch = t.at(index);
        int finds = smap.find(sch)->second;
        int findt = tmap.find(tch)->second;

        if ((finds > index) && (findt > index))
      {
       // ignore
      }

     if ((finds > index) && (findt < index))
    {
             check = false;
             break;
    }

      if ((finds < index) && (findt > index))
      {
           check = false;
            break;
       }

      if ((finds < index) && (findt < index) && (finds != findt))
       {
              check = false;
              break;
      }

       if (!(smap.count(sch) == tmap.count(tch)))
      {
            check = false;
            break;
       }

      smap[sch] = index;
      tmap[tch] = index;
      index++;
    }

return check;
}

Happy Numbers

Write an algorithm to determine if a number is "happy".

A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

Example: 19 is a happy number

• 12 + 92 = 82
• 82 + 22 = 68
• 62 + 82 = 100
• 12 + 02 + 02 = 1

Solution

   bool isHappy(int n) {

        int sumSquare = 0;

        int temp;

bool flag = true;

bool result = false;

set<int> HappyList;

pair<set<int>::iterator,bool> ret;

while (flag == true)

{

while (n > 0)

{

temp=n%10;

sumSquare = sumSquare + (temp*temp);

n = n/10;

}

ret = HappyList.insert(sumSquare);

if (ret.second == false)

{

flag = false;

}

        

if (sumSquare == 1)

{

result = true;

return result;

}

n = sumSquare;

sumSquare = 0;

}

        

       

        return false;

    }

• 
  

How to find duplicates in a list of number

I was trying to find out all the ways I can detect a duplicate in a list of numbers using the C++ Standard Library

Method 1
Use the fact that set does not allow duplicate numbers

bool containsDuplicate(vector<int>& nums)
{
bool DuplicateFlag = false;
set<int> s;
int previousSize = 0;

for (int index = 0; index < nums.capacity(); index++)
{
s.insert(nums[index]);
if (s.size() == previousSize)
{
DuplicateFlag = true;
break;
}
previousSize = s.size();
}

return DuplicateFlag;
}

Count the number of bits in an integer

Question
Why would someone count the number of bits in an integer ?
To Calculate parity (Okay you need to track whether the number of bits is odd or even)

Solution

    int countBits(uint32_t n) {
        int count = 0;
        while (n > 0)
        {
            n = n&(n-1);
            count++;
        }
       
        return count;
}


Trick
The expression n&(n-1) indicates whether n is a power of 2

Reverse bits in a word

Write a function to reverse bits in an integer

Bonus points for handling integers of all sizes

My Solution

Loop through half of the integer
Compare each bit with distance n from the least significant bit with the bit that is n distance from the Most Significant Bit
if they are the same do nothing
if they are different both the bits are toggled
end loop

unsigned int ReverseBits(unsigned int x)
{
unsigned int n = x;
int y = sizeof(int)*8;
int mask1, mask2;

for (int index = 0; index < y/2; index++)
{
mask1 = 1 << index;
mask2 = 1 << (y - index - 1);

// if match do nothing
if (((x & mask1)>>index) == ((x & mask2)>>(y-index-1)))
{
}
else
{
x ^= 1 << index;
x ^= 1 << (y - index - 1);
}
}

return x;
}