#codingexercise

We were discussing counting submatrices of same binary value of size k x k in an overall rectangular matrix.  

Another way to do it is to use dynamic programming as discussed here. 

void GetCountSquareBooleanSubMatrices(int [,] A, int rows, int cols, int binary, int size) 

{ 

Var dp = new int[rows, cols]; 

Int max = 1; 

for (int I = 0; I < rows; i++) 

for (int j = 0; j < cols; j++) 

{ 

If ((i-1 >= 0 && A[I,j] == A[i-1,j) && 

                   (j-1>= 0 && A[I,j] == A[I,j – 1]) && 

                   (i-1 >= 0 && j-1 >= 0 && A[I, j] == A[i-1, j-1]))  

               { 

dp[i, j] =  Math.Min(dp[I, j-1], dp[i-1,j], dp[i-1,j-1]) + 1; 

                             if (dp[i, j] > max) { 

max = dp[i, j]; 

                             } 

               } else { 

                              dp[I, j] = 1; 

               } 

} 

} 

int countZeros[max+1]; 

int countOnes[max+1]; 

for (int I =0; I < rows; i++) 

    for (int j = 0; j < cols; j++) 

           { 

                      If (A[i, j] == 0){ 

                           countZeros[dp[i,j]]++; 

                      } else { 

                           countOnes[dp[i,j]]++; 

                      } 

           } 

For (int k = max-1; k>= 0; k--) 

{ 

countZeros[i] += countZeros[i+1]; 

               countOnes[i] += countOnes[i+1]; 

} 

If (size > max) { 

      return 0; 

} 

If (binary == 0) { 

       return countZeros[size]; 

} else { 

       return countOnes[size]; 

} 

} 

We were discussing tge predecessor and successor in a preorder traversal The Predecessor for a Binary Search Tree can be looked up in the following way:
Node GetPredecessor(Node root)
{
if (root == NULL) return root;
if (root.left )
{
Node current = root.left;
While (current && current.right)
Current = current.right;
Return current;
}
Node parent = GetParent(root);
While (parent && parent.left == root)
{
root = parent;
parent = GetParent(root, parent);
}
return parent;
}
Node GetParent(Node root, Node child)
{
If (child == null) return null;
Node parent = null;
While ( root )
{
If (child.val == root.val) return parent;
parent = root;
If (child.val < root.val)
      Root = root.left;
Else
     Root = root.right;
}
Return null;
}
Node TreeSuccessor(Node z)
(
if (z == null) return null;
if (z.right)
    return TREE_MINIMUM(z.right);
Node parent = z.parent;
while(parent && parent.right == z)
{
 z = parent;
 parent = parent.parent;
 }
return parent;
}

 Public clouds offer different operating system images and container technologies  They have been continuously championing deep separation of resources for applications. Originally applications and services requiring storage and compute were monolithic and were deployed together as application server that was compute intensive and storage server that was storage intensive. Cloud introduced the notion of modular architecture and deep divisions of software on not just separate processes but also separate operating systems, containers, serverless resources and hosts such as OSv. The modules were executed on different virtual machines and those virtual machines ran on different OS images. The cloud providers often promoted virtualization technologies be it for compute or storage. While the users saw a shared-nothing architecture that looked like independent resources, the cloud providers virtualized and consolidated resources on platforms and software defined stacks. Such virtualization techniques focused on using existing technologies and features and provided platforms for application life cycle management to the cloud providers. There was no notion of administrators anymore as both the businesses as consumers of resources and the cloud providers as producers of resources maintained transparency and detail of the usages on pay as you go basis. In order to provide this virtualization starting from storage arrays to containers, vendors like Docker leveraged existing operating system features such as Linux containers and built their own containerization technologies. It was taken for granted that the operating system enabled virtualization over different hardware resources that the cloud providers - both public and hybrid needed. However, hypervisors provide more possibilities that the operating systems cannot provide to both the cloud providers and their clients.  In this article we focus on emerging trends.
Analysts love to put quadrants and stacks to explain their organization of emerging trends and improvements in existing participants of domain. This is a great practice to analyze everything out there and to categorize them for the purpose of viewing them in their context. Instead, we would like to bring to you the pockets of disruptive spaces that can emerge or is emerging from new and existing players.
We have seen GPU be a niche resource for Artificial Intelligence. We have seen object storage as a niche storage for all things big and small. We have seen containers, virtual machines, virtual storage, virtual networks, virtual data warehouses and even virtual datacenters. We have not seen a fabric that automatically determines the storage and compute setup needed for the computations and migrates them seamlessly leaving the programmer to develop only the algorithms and their variations. Is it possible to have a fabric that lets developers not have to think twice about writing O(N^2) algorithms for searching submatrices in a matrix? If they want, they can transform matrices into linear arrays and find ways to match patterns but how many need to do that today for scientific and commercial applications?
We have seen increased adoption of server-side technologies and the migration of server to the cloud but we have not seen simplification of software layers on the handheld devices. We have increased the battery power of mobile devices and the applications that run on it. There is a need for operating system, runtime and plethora of applications to power these.  But there is nothing solving the download and local install of applications on the handheld device where every experience on the software device is powered via software-as-a-service including the operating system, the mixing and matching of application portfolio and the reduction of hardware footprint on every handheld device. There is a Cicret bracelet that has yet to be commercially realized and introduces the notion of the handheld device as a mere projection on your skin so you can touch and play just like your phone. This notion that you don't need anything more than interactivity and you can help reduce the proliferation of hardware and software without compromising the popular user experience is motivation for another exciting trend
We have seen commoditization of IT in favor of business processes. We have seen commoditization of storage and compute in the form of cloud computing. We have seen virtualization over hybrid and vastly varying vendors of compute and storage. We have yet to see a universal and cheap T-shirt sized networked computers that can attach to various mobile units to offer programmable tasks such as monitoring on those remote units.

#codingexercise
Get the preorder successor of a node. A successor is one that comes after the node in the preorder traversal)
Node GetPreorderSuccessor(Node root, Node x)
{
Node result = null;
if (root == null || x == null || x == root) return result;
var list = new List<Node>();
ToPreOrder(ref list, root);
int index = root.indexOf(ref list, x);
if ( index >= 0 && index < list.Count()-1)
      return list[index+1];
return result;
}
static void ToPreOrder(ref List<Node> nodes, Node root)
{
if (root == null) return;
nodes.Add(root);
ToPreOrder(ref nodes, root.left);
ToPreOrder(ref nodes, root.right);
}
The logic for TREE-SUCCESSOR applies here too. The node that is not the root may have come from the previous frames left iteration or from the right iteration.

We were discussing file system improvements and cloud operating system.We mentioned Xen and OSv. Zen is a hypervisor technology and OSv tries to reduce the software layers for a single application on a Virtual Machine.
This means a general purpose operating system is no longer necessary. The runtime that the application requires is difficult to be ported to different hardware environment but manageable to be ported to hypervisors. This is what the cloud operating systems propose.
Why is the hypervisor technology relevant in the cloud computing business ? Public clouds offer different operating system images and container technologies  They have been continuously championing deep separation of resources for applications. Originally applications and services requiring storage and compute were monolithic and were deployed together as application server that was compute intensive and storage server that was storage intensive. Cloud introduced the notion of modular architecture and deep divisions of software on not just separate processes but also separate operating systems, containers, serverless resources and hosts such as OSv. The modules were executed on different virtual machines and those virtual machines ran on different OS images. The cloud operating systems often promoted virtualization technologies be it for compute or storage. While the users saw a shared-nothing architecture that promoted independent resources, the cloud providers virtualized and consolidated resources on platforms and software defined stacks. Such virtualization techniques focused on using existing technologies and features and provided platforms for application life cycle management to the cloud providers. There was no notion of administrators anymore as both the businesses as consumers of resources and the cloud providers as producers of resources maintained transparency and detail of the usages on pay as you go basis.In order to provide this virtualization starting from storage arrays to containers, vendors like Docker leveraged existing operating system features such as Linux containers and built their own containerization technologies. It was taken for granted that the operating system enabled virtualization over different hardware resources that the cloud providers - both public and hybrid needed. However, hypervisors provide more possibilities that the operating systems cannot provide to both the cloud providers and their clients.



#codingexercise
double GetNChooseKDP(double n, double k)
{
if (n < 0 || k < 0) return 0;
if (k == 0 || k == n)
    return 1;
return GetNChooseKDP(n-1, k-1) + GetNChooseKDP(n-1,k);
}

We were discussing counting submatrices of same binary value of size k x k in an overall rectangular matrix.
Since there are lot of overlapping subproblems in our previous approach, we can do this with dynamic programming as well. For example, we can establish a recurrence based on the current element being same as the element above it, the element to its left and the element diagonally top left to it in which case it creates a square smallest composite submatrix of size 2 x 2. The dp table matches the position of each matrix element. When the criteria is met, we take the minimum of the corresponding dp table values and add 1 for the current position. We initialize the dp table with 1 for all elements that do not match the criteria because the smallest square matrix is of size 1 x 1.  This automatically means for a unit row or unit column matrix, the count is merely one because that is the only square matrix possible.  Since we repeat with this criteria for all positions iterating from the top left of the rectangular matrix to the bottom right, this parity check adds  a row and column to considerations for matrices starting at those positions. we take the minimum count encountered for each of the three positions and add one if the parity check is satisfied. The significance of adding one is that we keep a tally of smaller submatrices formed at those positions and a bigger submatrix formed at the current position. When we are done with our iterations, we can create a frequency array for different values of the dp table. Then as we cumulate the frequencies one element to the left in the frequency array. Since the processing is the same for either binary value matching 0 or 1 as per the parameter passed in, we can build the frequency table for 0 or 1 simultaneously.
For example for size 1 we have 3 entries and for size 2 we have one entry so  when we cumulate we represent 4 matrix starting positions as contributing to size 1 and 1 matrix cell as contributing to size 2. We represent all matrix and submatrix starting position as the top-left.
The recursion is written as
(A [i,j] == A [i-1, j] &&
A [i,j] == A [i, j-1] &&
A [i,j] == A [i-1, j-1] )
=> dp [i,j] = math.min (dp [i-1,j], dp [i,j-1], dp [i-1, j-1]) +1;

Courtesy: geeksforgeeks