Monday, October 16, 2017

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. 

No comments:

Post a Comment