In continuation of our discussion on data architecture covered in previous posts, let us take an example and study it. We will review Amazon Dynamo as an example of a cloud based data storage and distributed system. Dynamo addresses the need for a reliable, scalable, highly available key-value storage system. It provides the ability to trade-off cost, consistency, durability and performance while maintaining high availability. With cloud based business such as Amazon, the compute and storage is distributed in several datacenters around the world. At this scale, there are many fault domains and and yet the persistent state has to be managed with high reliability and availability. To maitain this standard, Dynamo sacrifices consistency under certain conditions It makes extensive use of object-versioning and application assisted conflict resolution.  It is used to manage the state of services that have very high reliability requirements and need tight control over the tradeoffs between availability, consistency, cost effectiveness and performance. For a store like Amazon, a relational data store is limiting in terms of scale and availability. Dynamo provides a simple primary-key interface to meet this need.
We saw how conflict resolution is handled in Dynamo. When the conflict resolution happens and who does the conflict resolution is determined by the needs of the services using Dynamo.
Other design considerations include the ability to scale out the storage with no downtime, uniform nodes and no special roles for any set of nodes, the ability to decentralize control by way of simpler scalable peers and exploit heterogeneity in infrastructure.
Peer to Peer network formed for this storage does not depend on flooding the network with queries to find the peer with the data. Instead it relies on a structure and a globally consistent protocol to ensure that any node can route the search query to some peer that has the related data.
#codingexercise
1) Given a nested list of int array – calculate the sum of all the integers, while multiplying each number by its depth…

For example:

Here’s the depth sum of the nested list {1, {2, 3}}:

{1, {2, 3}} => 1*1 + 2*2 + 3*2 = 11

Here’s the depth sum of the nested list {1, {2, {3}}}:

{1, {2, {3}}} =>  1*1 + 2*2 + 3*3 = 14

static int CalcSum(Nested n, int depth)
{
int total = n.value * depth;
if (n.IsNested())
{
int newdepth = depth++;
foreach( var nl in n.nested)
{
   total += CalcSum(nl, newdepth)
}
}
return total;
}
2) Find sentences with the highest density of words from a list : solution

We were reviewing Amazon Dynamo as an example of a cloud based data storage and distributed system. Dynamo is a single highly available system for this entire Amazon store and it is designed to handle all loads including peak loads. Reading from their paper, we saw that Dynamo addresses the need for a reliable, scalable, highly available key-value storage system. It provides the ability to trade-off cost, consistency, durability and performance while maintaining high availability.
Let us look at the techniques involved to achieve this scale and availability. Data is partitioned and replicated using consistent hashing and consistency is facilitated by object versioning. Replicas are maintained during updates based on a quorum like technique. The replicas are kept in sync with a decentralized synchronization protocol. Dynamo employs a gossip based distributed failure detection and to determine memberships. Storage nodes can be added and removed from Dynamo without requiring any manual partitioning or redistribution.Conflicts need to be handled by determining when to resolve them and who resolves them. Eventually a consistent state will be achieved. While some systems determine when to resolve during writes, Dynamo is designed to be an always writeable store.
The writes are important to services because they could involve customer updates which cannot be lost or rejected.Therefore conflict resolution is not handled in writes. Instead, it is done during reads. To determine who performs the conflict resolution, we can choose between applications and datastore. The datastore is not context aware so it may choose to use the last write or such other straightforward mechanisms. The application is however savvy about the user context and can determine the best resolution. Therefore, the conflict resolution is performed by the application.

#codingexercise
Find a number in a rotated sorted array
int GetNumber(List<int> sortedRotated, int num)
{
int n = sortedRotated.Count;
int pivot = find_pivot(sortedRotated, 0, n-1, num); // binary search
if (pivot == -1)
      return binary_search(sortedRotated, 0, n-1);
if (sortedRotated[pivot] == num)
      return pivot;
if (sortedRotated[pivot] <= num)
     return GetNumber(sortedRotated, 0, pivot-1, num);
else
     return GetNumber(sortedRotated, pivot+1, n, num);
}
int find_pivot( List<int> sortedRotated, int start, int end)
{
 if (start < end)
     return -1;
 if (start == end) return start;
int mid = (start + end ) / 2;
if ( mid < end && sortedRotated[mid] > sortedRotated[mid+1]) return mid;
if (mid > start && sortedRotated[mid-1] > sortedRotated[mid]) return mid-1;
if (sortedRotated[low] >= sortedRotated[mid])
    return find_pivot(sortedRotated, start, mid-1);
return  find_pivot(sortedRotated, mid+1, end);
}
#alternative : http://ideone.com/e.js/F7V2aj
Also, we can use another technique that relies on a combined array that concatenates the  sortedRotated array with itself which gives a subarray that is already sorted with all of the elements. 
eg: 8, 9, 9, 1, 3, 4, 4, 4, 6, 6, 7, 7
8, 9, 9, 1, 3, 4, 4, 4, 6, 6, 7, 7, 8, 9, 9, 1, 3, 4, 4, 4, 6, 6, 7, 7
           1, 3, 4, 4, 4, 6, 6, 7, 7, 8, 9, 9,
As an example, since all the elements are sorted, finding the index of the element in this sorted sequence is a binary search. This length can then be added to the index of the pivot point to return the result.

DFS in a matrix with blockers
void DFS(int[,] A, int row, int col, int row, int col, ref int[,] visited, ref int  size)
{

var rd = { -1,-1,-1,0,0,1,1, 1};
var cd = { -1,0,1,-1,0,1,-1,0,1 };

visited[row,col] = true;
for (int k = 0; k < 8; k++)
    if (isSafe(A, row,col, row + rd[k], col +cd[k])){
           size++;
           DFS(A, row,col, row+rd[k], col+cd[k], ref visited, ref size);
}

}

In continuation of our discussion on data architecture covered in previous posts, let us take an example and study it. We will review Amazon Dynamo as an example of a cloud based data storage and distributed system. Dynamo addresses the need for a reliable, scalable, highly available key-value storage system. It provides the ability to trade-off cost, consistency, durability and performance while maintaining high availability. With cloud based business such as Amazon, the compute and storage is distributed in several datacenters around the world. At this scale, there are many fault domains and and yet the persistent state has to be managed with high reliability and availability. To maitain this standard, Dynamo sacrifices consistency under certain conditions It makes extensive use of object-versioning and application assisted conflict resolution.  It is used to manage the state of services that have very high reliability requirements and need tight control over the tradeoffs between availability, consistency, cost effectiveness and performance. For a store like Amazon, a relational data store is limiting in terms of scale and availability. Dynamo provides a simple primary-key interface to meet this need.
Let us look at the techniques involved to achieve this scale and availability. Data is partitioned and replicated using consistent hashing and consistency is facilitated by object versioning. Replicas are maintained during updates based on a quorum like technique. The replicas are kept in sync with a decentralized synchronization protocol. Dynamo employs a gossip based distributed failure detection and to determine memberships. Storage nodes can be added and removed from Dynamo without requiring any manual partitioning or redistribution. This lets Dynamo handle the peak load traffic to the Amazon store.Usually replication is performed synchronously to provide a consistent data access interface. This trades off the availability under certain failures. It is well known that consistency and availability are hard to achieve together. Availability can be increased by optimistic replication techniques where changes are allowed to propagate to replicas in the background. Disconnectivity is tolerated. Conflicts arising from now needs to be handled by determining when to resolve them and who resolves them. Eventually a consistent state will be achieved. While some systems determine when to resolve during writes, Dynamo is designed to be an always writeable store.
Dynamo has been the underlying storage technology for a number of the core services of Amazon e-commerce platform. This store handles several millions of checkouts a day.  Dynamo is a single highly available system for this entire store.
Courtesy: Amazon paper on Dynamo
#codingexercise
Count number of bridges possible between cities on northern and southern parts of the river such that they don't intersect. The southern cities are random order of the northern cities and bridges are drawn between same cities.
  cities A  B  C  D   E   F  G  H
  pairs  H  A  B  F   E    D G   C
  best    1  1  2  3   3    3  4   3
   A-A
   B-B
   D-D
   G-G

Longest increasing subsequence
int GetBridges(List<int> northernCities, List<int> southernCities)
{
return min (GetBridgesLIS(northernCities), GetBridgesLIS(southernCities));
}
int GetBridgesLIS(List<Char> A)
{
var best = new int[A.Length+1];
for (int i = 0; i < best.Length; i++)
       best[i] = 1;
for (int i = 1; i < A.Length; i++)
    for (int j=0; j < i; j++)
         if (A[i] > A[j])
          {
               best[i] = Math.Max(best[i], best[j]+1);
          }
return best.ToList().max();
}

Data architectures in Cloud Computing. 

We were discussing that traditional data processing architecture has changed a lot from where they used to be part of the ubiquitous three tier architecture involving databases, to being more distributed, scaled up and scaled out, sharded and hosted on private and public clouds, maintained on clusters and containers with shared volumes, hosted in memory and even becoming hybrid to involve SQL and NoSQL technologies. We continue reviewing some of the improvements in this field 

Today we look at data storage for social networking applications as an extreme of storage needed for this purpose. We recap the considerations presented in a video by Facebook Engineers for their data infrastructure needs. They have data arriving to the tune of several hundred Terabytes and a storage of over 300 Petabytes a fraction of which is processed. For example, their log storage flows into HDFS which is massively distributed storage. They use NoSQL Hadoop over HDFS together with Hive for data warehouse operations and SQL querying. This makes it easy for data tools and pipelines to work with this data stack.

Then they introduced Presto over HDFS for interactive analysis and Apache Giraph   over Hadoop for Graph Analytics. We will discuss Presto and Giraph shortly but let us take a look at the kind of data stored in these databases. All the images from the social networking flow into HayStack, The users are stored in mysql and all the chat is stored in H-Base. They use Scribe for Log Storage, Scuba for real-time slice and dice and Puma for Streaming analytics. These also give an indication of the major types of data processings involved with social network application.
Apache Giraph is an iterative graph processing system used for high scalability. It is used to analyze the graph formed by users and their connections.

#codingexercise
Given an array, find the maximum j-i such that arr[j] > arr[i]
int GetMaxDiff(List<int> A)
{
int diff = INT_MIN;
for (int i = 0; i < A.Length; i++)
  for (int j = A.Length -1; j > i; j--)
  {
      if (A[j] > A[i] && j-i > diff)
         diff = j-i;
  }
return diff;
}

Data architectures in Cloud Computing. 

We were discussing that traditional data processing architecture has changed a lot from where they used to be part of the ubiquitous three tier architecture involving databases, to being more distributed, scaled up and scaled out, sharded and hosted on private and public clouds, maintained on clusters and containers with shared volumes, hosted in memory and even becoming hybrid to involve SQL and NoSQL technologies. We continue reviewing some of the improvements in this field 
One of the trends is the availability of augmented memory with the help of solid state drives. The SSD increases the speed for data access by an order of magnitude compared to disk. Therefore memory intensive programs such as database and data access technologies have potential to make most use of this improvement.  With non-moveable storage such as SSD, there's also less vulnerability to faults and improved reliability of persistence. Needless to say, it improves database performance because disks don't have to be spun up.  Perhaps, the more significant contribution is when memory is backed by SSD such that in-memory programs can take more advantage of cache. Even if the database is used 24x7 for long periods of time, this does not wear the SSD. The TRIM command is especially provided for sustained long-term performance and wear-leveling. The TRIM support can be enabled on a continuous as well as a periodic basis.

 #codingexercise
Find the next greater element for all in an integer array
Int[] GetNextGreaterElements(List<int> A)
{
var result = new int[A.length];
for (int i =0; i < A.Length; i++)
{
int next = -1;
for (int j = i+1; j < A.Length; j++)
      if (A[j] > A[i]){
          next  = A[j];
          break;
      }
result[i] = next;
}
return result;

}

From database to data platform, there is evolution in programmability, toolset and workflows using the database. Also, designating dedicated instances of the database for organizational wide usage makes it appealing as a sink for all data enabling newer workflows and migration to being a platform. This means we make it easy for the data to flow into the in-memory database by writing different connectors, aggregators, input collection agents and forwarders. Newer data is not only found by content but also by source such as machine data, user data etc, technology such as document stores and key value indexes, and translations such as from one region or locale to another. 

In-memory databases could also benefit from unlimited memory via cloud resources or facilitators that stitch cloud resources. This may require moving away from cluster model where there is a differentiation between masters and slaves and enabling peer based computing scaling to unlimited numbers. There are some technical challenges in doing that but allowing a virtual cluster with cloud resources may still be viable. Moreover, we can allow smaller datasets on numerous memory rich compute resources with orders of magnitude more resources. If we make memory seamless between instances, we no longer have a cluster model but a single instance on an infinite hardware. The memory stitching layer can be offloaded to be database independent. By seamless, we mean it is not distributed model and also include the option for using SSD devices with RAM. If the in-memory database cannot be single limitless memory instance, perhaps we can consider single large scale cloud based generic cluster. Data writes that are flushed can be propagated to cloud storage. 

Azure provides cloud database as a service. It is a managed service offering database to developers. This notion of managed databases implies that the database adaptively tunes performance and automatically improves reliability and data protection which frees up the app development. It automatically scales on the fly with no downtime. We cite the Azure database as a service for the notion of managed services and for introducing elastic properties to the database. Whether a database is in memory or hosted on a cluster, is relational or NoSQL, there are benefits from managed services that makes it all the more appealing to users.

#codingexercise
Find the minimum number of deletions that will make two strings anagrams of each other
int GetMinDelete(string A, string B)
{
assert(A.ToLower() ==  A && B.ToLower() == B);
var ca = new int[26]{};
var cb = new int[26]{};
for (int i = 0; i < A.Length; i++)
    ca[A[i]-'a']++;
for (int i = 0; i < B.Length; i++)
    cb[B[i]-'a']++;
int result = 0;
for (int i = 0; i < 26; i++)
    result += Math.Abs(ca[i]-cb[i]);
return result;
}

Get Minimum sum of squares of character counts after removing k characters
step 1 make a frequency table
step 2 order frequencies in descending manner
step 3 decrement frequencies starting with the most repeating character until k characters
step 4 sum the squares of the remaining frequency counts.

We have a series of daily stock prices as a bar chart. We have to determine the span for all n days. A span is the number of days just before the given day, for which the price of the stock on the current day is less than or equal to the price of the stock on the given day. 

Int[] GetSpan(List<int> prices) 

{ 

var result = new int[prices.Length]; 

for (int I =0; I< prices.Length; I++) 

{ 

   Int count = 1; 

   For (int j = I-1; j >=0; j--) 

           If (prices[j] >prices[I]) 

               Break; 

           Else 

               Count++; 

     Result[I] = count; 

} 

Return result; 

} 

Database queries are just as important as data manipulation and archival and have played an important factor in their use. The kind of queries made has driven the adoption of the SQL standard that continues till date. Even when map-Reduce is the norm for Big Data, the ability to translate SQL queries on Big Data has become popular. Query execution and optimization is heavily dependent on costing model Once the query is sent to the database engine, it is translated into an abstract syntax tree. Then it is bound/resolved to column/table names. Next it is optimized by a set of tree transformations that chooses join orders or rewrites subselects. Both the nodes and the operations might change. The tree may be inserted into the cache and hydrated with code before execution. During execution, another set of tree transformations occur make it interpreted and more stateful. Resources acquired during cleanup are then released on cleanup. On the NoSQL side, say with Hadoop ecosystem, Hive is preferred over Pig because it is very SQL-like. It abstracts the data retrieval but does not support all the operations. Hive is also way more slower than SQL queries because there is no caching involved. It translates to MapReduce and re-runs each time. We realize its value only in context of the scale out efficiencies of Hadoop. A TableScan seems appealing only when the index seeks are in the orders of magnitude more. 

Data access patterns that involve locking and logging are generally limiting. When these constraints relaxed with say lock free skip lists, then range queries can actually scale more than B-Trees. These data structures together with multiversion concurrency control make it easier for the database to run in-memory which makes it all the more faster. In traditional databases, there is fixed overhead per query in terms of setting up contexts, preparing the tree for interpretations and running the query. The in-memory databases use code generation to avoid all this. Similarly MVCC gives the same efficiency and correctness as transactions. Given that SQL queries are becoming  a standard for working with relational, non-relational and in-memory databases, it should be safe to bet that this will become the norm for any new additions to the group. In fact, in-memory database scale out beyond single server to cluster nodes with communications based on SQL querying. Tables are distributed with hash-partitioning. What in-memory database fail to do is become a data platform like Splunk does for machine data and analysis  

#codingexercise

Reverse a singly linked list in groups of K and K+1 alternatively

eg. 1, 2, 3, 4, 5, 6,7 K= 3

3,2,1,7,6,5,4
    static Node Reverse(int k, int group, ref Node root)
    {
        Node current = root;
        Node next = null;
        Node prev = null;
        int count = 0;
        int max = k;
        if (group %2 == 1)  max = k+1 ;
        while (current != null && count < max)
        {
        next = current.next;
        current.next = prev;
        prev = current;    
        current = next;
        count++;
        }
        if (root != null)
            root.next = Reverse(k, group+1, ref next);
        return prev;
    }