We were reviewing how MongoDB enables integration with social engineering applications while also enabling data and service integration for the user data inflow with APIs for data and services during peak annual sales season. At the heart of their store, they can categorize data based on merchandising, content, inventory, customer, channel, sales and fulfilment, insight and social. Out of these merchanding, inventory, customer and insight are the most heavily used for peak holiday sales season.  In addition,  supply chain management system and data warehouse also integrate well with this Storage.

The information layer improves experience with look and feel, Navigation, customization, personalization, branding, promotion, chats and ads. Each of these is a separate initiative.  The customer's perspective helps us understand their context. For example, a user would like to browse and search the store online. This is part of his research. The shopping cart helps him select the items. The checkout experience is streamlined towards purchase.  The tracking of the item improves the receiving experience.  There is feedback loop and maintenance considerations with use of item.  The dialog with the customer is the focus of the assistance efforts. All these customer experiences translate to sofware interactions in two or three major categories on the enterprise side. For example,  the Market/Offer will require services separate from sell/fulfill.  The sell/fulfill will required data servces different from insight. Note that the services are easily enumerable within each category to be different from each other while they share the same information management backend which is facilitated with MongoDB which provides a one-stop shop for information management specifically in the areas of merchandising, inventory, customer and insight  The merchandising fulfils market/offer services such as guide, offer, semantic search, recommend, rule-based decisions, pricing and coupons. The Sell/fulfill provides ways for order, payments, fraud detection, fulfilment and business rules. The Insight provides ways for session capture and activity monitoring.

#codingexercise continued

Yesterday we described finding the largest submatrix in a binary matrix. 

We said the conventional way was to find connected components. Today we explain this:

int maxsize = 0
for (int i = 0; i < ROW; i++)
   for (int j = 0; j < COL; j++)
      if ( A[i,j] == 1 && !visited[i, j])
   {
        int size = 0;
        count++;
        DFS(A, ROW, COL, i, j, ref visited, ref size);
        if (size > maxSize)
             maxSize = size;

   }
This can be modified to record the cells of the submatrix contributing to the maximum size.
Given a cell in a connected component, we can find the top-left corner of the bounding submatrix with the minimum values for the x and y co-ordinates.

The maximum values of the x and y co-ordinates leads us to the bottom-right corner of the bounding submatrix

We were reviewing how MongoDB enables integration with social engineering applications while also enabling data and service integration for the user data inflow with APIs for data and services during peak annual sales season. At the heart of their store, they can categorize data based on merchandising, content, inventory, customer, channel, sales and fulfilment, insight and social. Out of these merchanding, inventory, customer and insight are the most heavily used for peak holiday sales season.  In addition,  supply chain management system and data warehouse also integrate well with this Storage.
The information layer improves experience with look and feel, Navigation, customization, personalization, branding, promotion, chats and ads.


#codingexercise

Maximize the count of 1 in a binary matrix by flipping any submatrix exactly once. 

The usual way of answering it is to find the most connected component of zero by adjacency breadth-first-traversal and then find the top-left and bottom-right inclusive boundaries based on the min and max of co-ordinates. 

But here is a twist courtesy an online solution: 

Step 1. Calculate a similar sized matrix as the input but having values as counts of 1 for a sub matrix ending with that cell as bottom-right and starting from 0,0. Let us call this matrix 'ones' matrix. 

Step 2. Exhaustively iterate all submatrices with boundary (i,j) top left to (i+k-1, j+k-1) as bottom right and determine the number of ones after a flip of this submatrix. Let us call this as 'cal' submatrix. We are not flipping square submatrices as i and j can each range from 1 to i+k-1 as long as they are within the input matrix. Also, we count the ones of the whole input matrix. For now, let us follow the steps 

Step 3. Within each iteration, the resulting value of the whole input matrix after the flip comes out to be: 

                  ones[R,C] - ones in the chosen submatrix + zeroes in the chosen sub matrix 

               = ones[R,C] - cal(i, j, i+k-1, j+k-1) +  (k x k -cal(i, j, i+k-1, j+k-1)) 

               = ones[R, C] + k x k + 2 x cal(i, j, i+k-1, j+k-1) 

Step 4. From the value computed in step 3 for each iteration, we determine the max found so far and return it as the final result. 

Today we continue to look at emerging trends in Data storage. Retail companies are increasingly relying on data access services rather than databases. This lets them decouple their business layer from the data access and persistence layer. In this domain, they can quickly implement new business requirements, seasonal campaigns and recommendation algorithms. While traditionally these data access and database services have been hosted right out of the relational stores, companies have started adopting big data.  Moreover the data access services to big data are also no longer necessarily with the retail companies as consolidators and even database offerings have improved to take advantage of this emerging trend. MongoDB is one such data services provider that powers the customer facing companies in a comprehensive way. We take a look at this big picture.
Customer facing companies have comparmentalized the handling of user data from channels, stores, mobile devices, website and contact center.  The channels include marketplace such as online retail companies. The stores include point of sale registers and kiosks. The mobile devices include smartphone and tablets. The website includes a variety of landing pages for customers. The contact center includes customer support options. Furthermore, when users login, they do so with the logins from their social engineering applications and are not necessarily bound to the accounts of a specific store.
MongoDB enables this integration with social engineering applications with application servers while also enabling data and service integration for the said user data inflow with APIs for data and services. Web servers may also be made available for any siloed or sweeping data access. At the heart of their store, they can categorize data based on merchandising, content, inventory, customer, channel, sales and fulfilment, insight and social. Out of these merchanding, inventory, customer and insight are the most heavily used for peak holiday sales season.  The supply chain management system and data warehouse require data flows from this backend. The former is used by suppliers for and necessary for the smooth operation of data access and persistence for holiday shopping. The latter is used to power analytics. The merchandising, inventory, customer and insight information management systems enable critical business workflows in the areas of market/offer, sell/fulfill and insight. The market/offer functions includes guide, offer, semantic search, recommend, rule based decisions, pricing and coupons. The sell/fulfill include orders, payments, fraud detection, fulfilment and business rules.  The insight involves session capture and activity monitoring. We review some of these in detail in the next few posts.
Courtesy: MongoDB.

#codingexercise
In a rowwise and columnwise sorted matrix, enumerate the elements in ascending order

There is a front that moves from the top left corner to the bottom right. Element along the front are guaranteed to include the minimum. Since the front only moves one cell down or to the right, the element along the zig zag shape of the front are easy to enumerate to pick out the minimum at any step.

void PrintSerialized(int[ , ] A, int rows, int cols)

{

if ( A== null || rows == 0 || cols == 0) return;

var items = new List<Tuple<int,int>>();

items.Add(new Tuple<int,int>(0,0));

while ( items.Count != 0 )

{

// print current min

var item = RemoveMinValue(items);

Console.WriteLine(item.GetValue());

// add next candidates

var down = new Tuple<int,int>(item.first+1, item.second);

var right = new Tuple<int,int>(item.first,item.second+1);

if (IsValid(down) && items.Contains(down) == false)

    items.Add(down);

if (IsValid(right) && items.Contains(right) == false)

    items.Add(right);

}

Console.WriteLine(A[r,c]);

}

5  10   12  14

6  11  13   19

7  15  22  29

9  25  32  39

#puzzle
Without computer assistance, find five different sets of three positive integers {k, m, n}
such that k < m < n and
(1/k)+(1/m)+(1/n) = 19/84

Since this involves fractions the gcd of the denominators k,m,n can be considered to be 84.
So multiplying by 84 we can write this as a + b +c = 19 where
a = 84/k
b = 84/m
c = 84/n
and a, b, c must lie in the factors
1,2,3,4,6,7,12,14,21,28,42,84
Moreover a > b > c for k < m < n
By eliminating a few of these, we can say 'a' could start from 7,12 or 14.
We find two such pairs  for (a,b,c)
12, 6, 1  which implies k,m,n is 7,14,84
12, 4, 3  which implies k,m,n is 7, 21, 28
Similarly when a is 14, we get
14, 4, 1  which implies k,m,n is 6, 21, 84
14, 3, 2  which implies k,m,n is 6, 28, 42
Since we tried k = 6, 7, we can try k =5 and use a gcd of 420
which gives us k,m,n as 5, 60, 105

#codingexercise
In a rowwise and columnwise sorted matrix, enumerate the elements in ascending order
There is a front that moves from the top left corner to the bottom right. Element along the front are guaranteed to include the minimum. Since the front only moves one cell down or to the right, the element along the zig zag shape of the front are easy to enumerate to pick out the minimum at any step.

#puzzle
 A rearrangement of the letters of a word has no fixed letters if, when the rearrangement is placed directly below the word, no column has the same letter repeated. For instance, the blocks of letters below show that ESARET is a rearrangement with no fixed letters of T E R E S A, but R E A S T E is not.
T E R E S A              T E R E S A
E S A R E T              R E A S T E
How many distinguishable rearrangements with no fixed letters does T E R E S A have? (The two E’s are considered identical.)
Since we have been given a small search word, we could easily enumerate the combinations. For example, we can place the 2 E's in different position as follows:
E ? E ? ? ?
E ? ? ? E ?
E ? ? ? ? E
? ? E ? E ?
? ? E ? ? E
? ? ? ? E E

This yields 6 ways to do so. One way to think about this is that we are moving each of the E's to the remaining four positions and therefore there are 4-Choose-2 ways = 6 ways.
Taking one of the six arrangements above, we can also enumerate the possible arrangements of the remaining letters. Let us say E now occupies new positions X and Y. Neither X nor Y can be in their original position no matter where we put them.  So we have to place the last two letters which we call M and N and there are only 4 positions to choose from.  M can either be moved to where N was or it can be moved to one of the original positions of E. In the former case there are three positions remaining for N so there are 3 ways to do so. In the latter case there are two E's so there are two ways each for M and for N. There fore there are a total of 3 + 2 x 2 = 7 ways to place the last two letters. Moreover X and Y can also be interchanged so we have 7 times 2 equals 14 ways. Since we are doing this for each of the 6 ways to place E's to start with, we have a total of 6 x 14 = 84 ways. It is possible to enumerate all these 14 ways for a given starting arrangement of E and see that we can repeat the same for any of the remaining  arrangements of E.

codingexercise
Find the sub-tree with maximum  color difference in  a 2 colored tree
We define color difference as the magnitude of the number of vertices of one color minus the number of other color vertices where each number is a positive count.
Since it is not convenient to return all the subtrees and exhaust the search space,
We will keep track of minimum and maximum color difference of two subtrees and we will color 1 or –1 so that the equal number of both balance each other out.
When we perform a depth first search, we can find the maximum of any color by assigning  1 to that color. Since depth first traversal finds subtrees we have the maximum available for a sub tree.
When we invert the color, we can find the maximum of the opposite color with a similar depth first search.
During the depth first search for every node as the starting point, to find
1) max sum sub tree, we take a node if its value is greater than 0 => sum(parent) += max(0, sum(child))
2) min sum sub tree, we take a node if its value is lesser than 0 => sum(parent) += min(0, sum(child))
Thus for each node we have a color count array . Previously visited nodes already have this counted so this is a form of overlapping subproblems which we alleviate by memoization
After each depth first search we now have a color count array of a sub-tree for which we can find the maximum
When we get the maximum of both colors this way from the color count array, we know that the maximum color count difference is between this high number and nothing. Therefore, we have the color difference we are looking for.

int maxDiff(Node root, List<int> colors, int N)
{
   var counts = new List<int>();
   dfs(root, colors, ref counts);
   int max = counts.Max();
   colors.ForEach (x => Invert(x));
   dfs(root, colors, ref counts);
   max = Math.max(max, counts.Max());
   return max;
}