today we look at a few more alternatives to the submatrix of 1 problem discussed earlier.
one such method is to facilitate merge along vertical and horizontal axis in a way such that contiguous regions of 1s are identified, sized and top left corner identified. then we split the original matrix into  2 power x sub matrices by repeatedly dividing  both x and y axis. This works well for cohesive matrices where the 1s are all together as islands. Since each point is counted only once during the merge before being assigned to a group and the results aggregated, this is more efficient than the nested evaluation of each point as a candidate for top left corner. Moreover we keep track of the top left and bottom right corners of each candidate submatrix from the adjoining contiguous overlaps during each merge. each overlap along a merge front determines the span of the submatrix


today we review a new topic called social balance theory from the chapter on network measures. this theory is about friends and enemies relationships abd i had never really paid attention to it so far. it states:
The friend of my friend is my friend, The friend of my enemy is my enemy, The enemy of my enemy is my friend, The enemy of my friend is my enemy.
All this theory states is that the friends or enemy relationships are consistent when the above is followed.

we can represent these relationships in a graph. The friendhip is denoted by positive edges, the enemity by negative edges and a triangle between participants denotes imbalance if the weights around the edges of the triangle taken together is less than zero. this kind of metric can also be explored for graphs that are not triangular in general.

#codingexercise
for the  problem duscussed yesterday, we see a few more alternatives

parallel processing
sum along all columns
sum along all rows
if any row or column is all zero
split the matrix on either side of the zeros
compute the submatrix as usual

another method may be to merge two sub matrices along a front
the histogram on both sides of the front are computed starting from the front and progressing outwards
for contiguous non-zero paired entries on the histograms on both sides, the max area is calculated for each contiguous zone out of which the largest is chosen

another method for a merge like above would be to find contiguous zones of ones along the front
for each of the contiguous zone, and for each of the ones in the zone find the max area on both sides noting the common width.
retirn the max of all such combined max.

Linux Containers
Today we discuss the Linux Containers. These form isolated environments within the operating system. As we know Linux itself is a modular design with layered components where every component can be replaced with another and the whole operating system can be rebuilt.
The standard layers including the operating system are:

Users
Utility Programs
System Library
Linux OS
Hardware

The interfaces between users and user programs is User Interface.
The interface between utility programs and system library is library interface
The interface between system library and Linux is system call interface.

The LXC hosts more than one containers by being a layer over the OS.  Since the OS can be over real or virtual hardware, we can have the whole stack nested as we nest containers.

A network bridge is established on the host operating system and the containers are usually NAT'ed. This means the containers are not directly reachable from the outside network. With DHCP, they get assigned an ip address so addressing is not a problem but to facilitate inbound and outbound connections, the gateway must be specified in routing table of the containers.  Outbound connections are facilitated with the gateway. If the bridge was established over the original ethernet interface of the host, the inbound connectivity is also established. This way the containers can be accessed by ssh.

Often containers are required to be cut with some customization scripts. These include provisioning a sudo user or enabling ssh access for public keys. All of these can be run as shell commands targeting the specific container from the host with something like:
lxc exec <container_name> -- command


#codingexercise
Find the largest sub matrix rectangle of 1's in a two dimensional binary matrix.
Here's the alternative version to the solution yesterday.
int GetMax(int[,] A, int R, int C)
{
int max = int_min;
for (int i = 0; i < R; i++)
   for (int j = 0; j < C; j++){
        area = AreaWithTopLeft(A,i,j, R, C);
        if (area > max)
             max = area;
     }
return max;
}
int AreaWithTopLeft(int[,] A, int i, int j, int R, int C)
{
int max = 0;
int prev = int_max;
if (A[i,j] != 1) return 0;
for (int x = i; x < R; x++){
   int count = 0;
   for (int y = j; y < C; y++)
   {
      if (A[i,j]  == 1) count++;
   }
   if (count == 0) return max;
   int newmax = min(prev, count) * (x-i+1))
   if (newmax < max)
       return max;
    max = newmax;
   prev = count;
}
return max;
}
we can also optimize the above bailing early so that we dont have to iterate when there are no ones.

Serial console on VMWare

Introduction:  We reviewed the DELL Serial Console Option. This document is about the serial console for VMWare Virtual Machines.

Architecture:

The VMWare community suggests using the virtual serial port concentrator. The concentrator also called the proxy has internal connections to several virtual machines in a datacenter and an external connection to a remote system.

The virtual serial port concentrator can be deployed as a virtual appliance involving a single virtual machine. This appliance uses the virtual machine ip address that persists across vMotion events. The Proxy accepts telnet connections from virtual machine and supports the VMWare telnet extension commands and corresponding notifications in addition to forwarding traffic both ways. The proxy serves as a point of authentication on a remote system. Since the telnet connections are internal, they need not be secured. Even a Moxa device server uses telnet console.

A virtual serial port provides out of band access to the virtual machine so that even if we lose network connectivity, we can use the serial console to interact with the machine. When this serial console is available over IP, you can remotely manage a machine even when there is a fault in the OS or the hardware of a machine.

Steps to take on the Proxy:

1.       Start the vspc.py using  - - server option

2.       Configure the vspc.py to start automatically at boot

3.       Edit the local firewall rules on the virtual serial port concentrator to permit 13370/tcp, 13371/tcp and a range of ports for target virtual machines starting at any high value say 63000

Steps to take on each VM

1.       Power off VM

2.       Add a serial port to the VM with the following settings:

On the Hardware tab, click Add.

In the Add Hardware wizard, select Serial Port.

Select where the virtual serial port sends output. It should be one of the following:

Use a physical parallel port

Use output file

Connect to named pipe

Connect via network

Choose the last option

And specify use virtual serial port concentrator and type the vSPC URI as telnet://vspc.local.lan:13370

If we don’t want to use a vSPC and provide a dedicated serial port, We can also use xcat/socat/netcat etc. Refer VMWare how to for virtual serial port configuration

select this end is the server from the first drop-down menu and select

the other end is an application from the second drop-down menu.

To connect the port to the virtual machine when the virtual machine powers on, select Connect at power on.

Click Finish to add the virtual serial port to the virtual machine.

On the Hardware tab, select the new serial port, select Yield CPU on poll, and click OK.

3.       Start the virtual machine

To query the virtual serial port connections opened on the proxy, run, from any machine including laptop with connectivity to the proxy, the following command:

./vSPC.py vspc. local.lan

machine1:500aedefafeae42434-b534dade2eawa5q3:63002

machine2:90834124ewdafwe-aw243123ewdeawdea:63003

etc.

To connect to the serial console, let’s use the corresponding port

telnet vspc.example.com 63002

Caveat : This information is provided as-is by collection from literature. 

Courtesy : VMWare vsphere web services SDK

To view consoles in public cloud refer http://docs.aws.amazon.com/AWSEC2/latest/UserGuide/instance-console.html

#codingexercise
Tell whether a matrix containing 0s and 1s can be divided into 2 sub matrices containing equal number of 1s.
Matrices can be split into two only by vertical or horizontal partitions. We can enumerate all partitions and check

bool HasEqual1and0(int[,] A, int r0, int rn, int c0, int cn)
{
int count = CountOnes(A, r0, rn, c0,cn);
for (int i = r0+1; i <= rn-1; i++)
{
int count1 =  CountOnes(A, r0, i, c0,cn);
int count2 =  CountOnes(A,i+1, rn, c0, cn);
assert(count1+count2 == count);
if (count1 == count2) return true;
}
for (int j = co+1; j<=cn-1;j++)
{
int count1 =  CountOnes(A, r0, rn, c0, j);
int count2 =  CountOnes(A, r0, rn, j+1, cn-1);
assert(count1 + count2 == count);
if (count1 == count2) return true;
}
return false;
}

int CountOnes(int[,] A, int r0, int rn, int c0, int cn)
{
int count = 0;
for (int i = r0; i <= rn; i++)
for (int j = co; j<=cn;j++)
      if (A[i,j] == 1) count++;
return count;
}

Find the largest sub matrix rectangle of 1's in the above matrix:
we  create a histogram and find the maximum area under the histogram
int maxRectange(int[,] A, int R, int C)
{
int result = GetMaxFromHistogram(A[0]); // this is the area of the first row
for (int i = 1; i < R; i++)
{
   for (int j = 0; j < C; j++)
         if (A[i, j] ) A[i, j] += A[i-1, j]
  result = max(result, GetMaxFromHistogram(A[i]));
}
 return result;
}
MaxAreaOfARectangle implemented GetMaxFromHistogram earlier

alternatively the max area of submatrix of 1s can also be found by treating each cell as the top left corner of the rectangle.

Serial Console Access over SSH

iDrac already provides console access via SSH as per the diagram below for certain DELL servers. An API service facilitating console access needs to only secure it by allowing the console access on a customer by customer basis and to only his or her servers: 

 

1. Initial setup follows this configuration: http://www.slac.stanford.edu/grp/cd/soft/unix/EnableSerialConsoleAccessViaSSH.htm 

Which specifies console redirection over SSH from iDRAC with the following setting: 

# racadm get iDRAC.SSH.Enable 

[Key=iDRAC.Embedded.1#SSH.1] 

Enable=Enabled 

2. For each console session initiation and termination, we start the console redirection with the following serial console commands: (All serial console commands are identical and at the same level as RACADM CLI subcommands. This means you can specify serial commands as well as racadm commands from the serial/telnet console.)  

1. racadm racreset – this releases the serial port used previously 

2. connect <servername> -F 

1. (Instead of <servername> we can specify switch-x where x represents a module slot number on the chassis). When the system BIOS console redirection setting is set to BMC, the –F option forces the serial console redirection session to switch from BMC to DRAC/MgmtConsole. When the system is rebooted, the BIOS console redirection setting returns to the default setting.  

2. Reboot the target 

3. <Enter><~><.>  or ^\ to exit out of the session 

4. getpbinfo (for power status and power information) 

5. serveraction ( for executing a server reset/powerdown/graceful powerdown/powerdown/powerup/powercycle)

#codingexercise
Cars 1 to 9 are parked randomly in the slots marked 1 to 9. Using the tenth slot, arrange the cars.

void arrange(ref List<int>cars)
{
for (int i = 0; i <cars.count; i ++)
{
if (cars[i] == i) continue;
for (int j =i+1; j < cars.count; j++){
   if (cars[j] == i){
          Swap(cars,i,j);
   }
}
}
}
the above method can be made linear if we maintain a lookup of where the cars can be found.

We were reviewing the vSPC.py library. This is a virtual serial port concentrator that makes the use of VMware telnet extensions.The mechanism is based on RFC2217 - compatible telnet server.
When a remote system makes a connection request to the target on the ESX server, one virtual machine acts as a virtual serial port server and another acts as a client  The proxy listens for connection requests from the remote system and forwards it to the target This is true in the opposite direction as well. The proxy forwards both ways.
The proxy which  operates as a serial port concentrator has internal connections to several virtual machines in a datacenter and an external connection to a remote system. The concentrator provides a remote system with access to multiple virtual machines that act as serial port servers.
 This is a many to one mapping. The communication happens over a network serial port which uses a network socket on the host computer. A network socket is the endpoint of a network connection and is represented by an IP address, protocol and a port number. The network serial port must be supported by the ESX and then created or reconfigured on a virtual machine.
Virtual serial ports come in handy for backup and backing option.  They remain up even when the virtual machines go through vMotion.  To support this kind of persistent connection, the proxy makes two telnet connections for the virtual machine.  The ESX server supports a telnet extension specific to VMWare that allows the proxy to postpone the vMotion event until it finishes forwarding content. The ESX server sends a vmotion-begin  command and the proxy responds with a vmotion-goahead command. During this time, the proxy buffers any additional data it receives from the remote system. When the vMotion is complete, the proxy continues the content transmission to the new instance of the virtual machine.  When the new instance of the virtual machine boots up, the ESX server configures network backing for the virtual serial port and establishes  a second telnet connection with the proxy. Before continuing with the vMotion operation, the new virtual machine instance and the proxy renegotiate the telnet COM-PORT-OPTION without the proxy losing the com-port-option for the original instance. The proxy now supports one telnet connection for each instance. After the proxy accepts a new virtual machine instance as a peer, the ESX host on the new instance sends a vmotion-complete to the proxy so that it can release the original telnet connection.

Console access is available even from DRAC over ip as shown here : http://www.slac.stanford.edu/grp/cd/soft/unix/EnableSerialConsoleAccessViaSSH.htm

and explained here : https://1drv.ms/w/s!Ashlm-Nw-wnWlk6DmH-B9_C1dul6 

#codingexercise

Given  a binary tree with positive and negative values, find the maximum sum in a path through the parent. The path may start and end at any node in the tree.

int GetMaxPath(node root, ref int sum)
{
if (root == null) return 0;

var left  = GetMaxPath(root, ref sum);
var right = GetMaxPath(root, ref sum);
var max_one = max(root.data,
                                 max(left, right) + root.data));
sum =  Max(max_one,
                   left + right + root.data,
                   sum);
return max_one;
}
GetMaxPath(tree_top, int_min);


Determine if two trees are isomorphic
Two trees are isomorphic if the left tree and the right tree are identical.
bool isIsomorphic(Node root1, Node root2)
{
if (root1 == null && root2 == null) return true;
if (root1 == null || root2 == null) return false;
if (root1.data != root2.data) return false;
 if   (((isIsomorphic(root1.left, root2.left) && isIsomorphic(root1.right, root2.right)) ||
      ((isIsomorphic(root1.left, root2.right) && isIsomorphic(root1.right, root2.left)))
{
return true;
}
return false;
}

find the length of the longest arithmetic progression in an array

int GetLongestAP(List<int>numbers)
{
var progressions = new List<List<int>>();
var candidate = new List<int>();
numbers.ForEach( x => candidate.Add(-1));
int start = 0;
int level = 0;
Combine(numbers, ref candidate, ref progressions, start, level); // already implemented in this blog
but with the enhancement that we reject combinations that are not isAP();
return progressions.Max(x => x.Count(y => y != -1)).count;
}

bool isAP(List<int> numbers)
{
if (numbers == null || numbers.count <=2) return false;
int diff = numbers[1] - numbers[0] ;
for (int i = 2; i <numbers.count; i++)
    if (numbers[i]-numbers[i-1] != diff)
        return false;
return true;
}

Yesterday we were talking about serial port and the pyserial library. Today we review the vSPC.py library. This is a virtual serial port concentrator that makes the use of VMware telnet extensions.
Its requirements are simple.
 A Linux VM w/Python 2/3
a vSPC.py script installed on the VM.
configure it to start on boot
enable local firewall rules to permit 13370/tcp, 13371/tcp and a range of ports for the targets.
This is enough to configure a virtual serial port concentrator host VM.
To configure the target, we add a serial port to the VM with the following settings:
Type : Network
Direction : Server
Port URI: vSPC.py
Use Virtual Serial Port Concentrator : <checked>
vSPC URI: telnet://vspc.local.lan:13370
Yield CPU on Poll : <checked>

To enumerate the connections from the target, we simply issue
locally : .vSPC.py localhost
remote : vSPC.py vspc.local.lan
The advantages of a serial port concentrator over statically mapped ones include :

It handles dynamic port assignment which can be queried. Static port assignments cannot be queried. The access to the target is never lost.
You no longer need the VMware console access and authorization.
The static ports are mapped onto the ESXi server which requires firewall to be opened for ESXi but vSPC runs on the local VM.
vSPC works on any Linux flavors.

The mechanism is based on RFC2217 - compatible telnet server.  The proxy which  operates as a serial port concentrator has internal connections to several virtual machines in a datacenter and an external connection to a remote system. The concentrator provides a remote system with access to multiple virtual machines that act as serial port servers.
 This is a many to one mapping.
When a remote system makes a connection request to the target on the ESX server, one virtual machine acts as a virtual serial port server and another acts as a client  The proxy listens for connection requests from the remote system and forwards it to the target This is true in the opposite direction as well. The proxy forwards both ways.
#codingexercise
        static int GetKthSmallest(int[,] A, int row, int col, int k)
        {
            int r = 0;
            int c = 0;
            int maxr = 0;
            int maxc = 0;
            int prev = -1;
            if (k <= 0 || k < prev) return -1;
            int count = 0;
            while (count < k)
            {
                // compare right and bottom and increment r or c
                // the idea is that the k largest elements will be a contiguous block 
                // and the next element for inclusion will be either to the right of this block or 
                // at the bottom of this block
                // we just need to propagate the front on all rows one cell at a time.
                if (count + 1 == k) {  return A[r, c]; }

                int rselected = r * col + c; // position of selected at bottom
                int cselected = r * col + c; // position of selected to right
                int rmax = Int16.MaxValue;  // max value on top or at left
                for (int y = 0; y <= c ; y++)
                {
                    if (r >= row - 1) break;
                    var candidate = A[r+1,y];
                    if (r < row - 1 && candidate < rmax &&
                        (prev == -1 || candidate > A[prev/col, prev%col]))
                    {
                        rmax = A[r + 1, y];
                        rselected = (r + 1) * col + y;
                    }
                    if (maxr >= row - 1) break;
                    candidate = A[maxr + 1, y];
                    if (maxr < row - 1 && A[maxr + 1, y] < rmax &&
                        (prev == -1 || candidate > A[prev/col, prev%col]))
                    {
                        rmax = A[maxr + 1, y];
                        rselected = (rmax + 1) * col + y;
                    }
                }
                for (int x = 0; x <= r; x++)
                {
                    if (c >= col - 1) break;
                    var candidate = A[r, c + 1];
                    if (c < col - 1 && candidate < rmax &&
                        (prev == -1 || candidate > A[prev/col, prev%col]))
                    {
                        rmax = A[r, c + 1];
                        rselected = r * col + c + 1;
                    }
                    if (maxc >= col - 1) break;
                    candidate = A[r, maxc + 1];
                    if (maxc < col - 1 && candidate < rmax &&
                        (prev == -1 || candidate > A[prev/col, prev%col]))
                    {
                        rmax = A[r, maxc + 1];
                        rselected = r * col + maxc + 1;
                    }
                }
                prev = r * col + c;
                r = rselected / col;
                c = rselected % col;
                if (r > maxr) maxr = r;
                if (c > maxc) maxc = c;
                count++;
            }
            return A[r, c];
        }
    class Program
    {
        static void Main(string[] args)
        {
            var A = new int [4, 4] {{10, 13, 15, 19 }, {21, 23, 24, 27}, {29, 31, 33, 37}, {41, 43, 45, 47}};
            for (int k = 1; k < 17; k++)
            {
                Console.WriteLine("K={0},Value={1}", k, GetKthSmallest(A, 4, 4, k));
            }
       }
    }

K=1,Value=10
K=2,Value=13
K=3,Value=15
K=4,Value=19
K=5,Value=21
K=6,Value=23
K=7,Value=24
K=8,Value=27
K=9,Value=29
K=10,Value=31
K=11,Value=33
K=12,Value=37
K=13,Value=41
K=14,Value=43
K=15,Value=45
K=16,Value=47