#algorithm discussion continued
Today we continue reading the flow networks. We were looking at maximum flows

Maximum flows can also be calculated using "push-relabel" method. This method works in a more localized manner than Ford Fulkerson method. It works on one vertex at a time, looking only at the vertex's neighbour in the residual network. Thus it avoids examining the entire residual network to find an augmenting path. Also, they do not maintain flow conservation. Instead they maintain a preflow property which goes to say that the total flow into a vertex may exceed the flow out.

 Each vertex has an outflow pipe leading to an arbitrarily large reservoir that can accumulate fluid. In addition, each vertex, it's reservoir, and all its pipe connections sit on a platform whose height increases as the algorithm progresses. The height is used to push fluids only downhill which means from a higher vertex to a lower vertex even though there may be flows from a lower vertex to a higher vertex that may be positive.

The only outgoing flow from a vertex u that is not already saturated with flow are those that connect to vertices at the same level or at a higher level. In order to make a flow outbound from u we relabel it by pushing it one unit higher than its neighbors. This helps us rid an overflowing vertex u of its excess flow. By repeating this iteratively we get maximum flow.

The proof to show that preflow under such conditions becomes maximum will be discussed shortly.

This method performs two basic operations: pushing flow excess from a vertex to one of its neighbors and relabeling a vertex.

#codingexercise

Void getkthfirst(node head, int k, ref int count, ref node kthfirst)

{

If (head == null) return;

count = count + 1;

if (count==k) { kthfirst = head; return;}

Getkthfirst(head.next, k, ref count, ref kthfirst);

}

Bool isEqual(node tree1, node tree2)
{
if (tree1 == null && tree2 == null) return true;
if (tree1 == null || tree2 == null) return false:
if(tree1.data != tree2.data) return false;
Return isEqual(tree1.left, tree2.left) && isEqual(tree1.right, tree2.right);
}

If we define G as graph (V, E) with source s and sink t with a preflow f and a height function h, then if h(u) >= h(v) + 1, then (u,v) is not an edge in the residual network

#algorithm discussion continued
Today we continue reading the flow networks. We were looking at maximum flows

Maximum flows can also be calculated using "push-relabel" method. This method works in a more localized manner than Ford Fulkerson method. It works on one vertex at a time, looking only at the vertex's neighbour in the residual network. Thus it avoids examining the entire residual network to find an augmenting path. Also, they do not maintain flow conservation. Instead they maintain a preflow property which goes to say that the total flow into a vertex may exceed the flow out.

#codingexercise

Void getkthfirst(node head, int k, ref int count, ref node kthfirst)

{

If (head == null) return;

count = count + 1;

if (count==k) { kthfirst = head; return;}

Getkthfirst(head.next, k, ref count, ref kthfirst);

}

#algorithm discussion continued
Today we continue reading the flow networks. We were looking at max flow min cut theorem and the properties associated with it. We saw how it applied to Ford Fulkerson method. Each iteration of the method augmented the flow by considering a path in the residual network until there is no more. For each path considered, the residual capacity of that path is found and augmented to the flow network.
Maximum flow problems have a direct application in some combinatorial problems and we saw how it applied to matching in bipartite graphs. A maximum bipartite matching is a matching of maximum cardinality.

Maximum flows can also be calculated using "push-relabel" method. This method works in a more localized manner than Ford Fulkerson method. It works on one vertex at a time, looking only at the vertex's neighbour in the residual network. Thus it avoids examining the entire residual network to find an augmenting path. Also, they do not maintain flow conservation. Instead they maintain a preflow property which goes to say that the total flow into a vertex may exceed the flow out.

The excess at a vertex is the amount by which the flow in exceeds the flow out and the vertex is said to be overflowing. This method applies two operations : pushing preflow and relabeling a vertex.

Both Ford Fulkerson and Push Relabel envision the graph to be a flow network as a system of interconnected pipes of given capacities. The former uses augmenting paths in the network to give rise to an additional stream of fluid with no branches between source and sink and iteratively adds streams until there are no more. The latter assumes that each vertex has an outflow pipe leading to an arbitrarily large reservoir that can accumulate fluid. In addition, it assumes that each vertex, it's reservoir, and all its pipe connections sit on a platform whose height increases as the algorithm progresses. The height is used to push fluids only downhill which means from a higher vertex to a lower vertex even though there may be flows from a lower vertex to a higher vertex that may be positive.

The only outgoing flow from a vertex u that is not already saturated with flow are those that connect to vertices at the same level or at a higher level. In order to make a flow outbound from u we relabel it by pushing it one unit higher than its neighbors. This helps us rid an overflowing vertex u of its excess flow.

By repeating this iteratively, we induce as much flow downwards as possible. The excess in the reservoirs of the overflowing vertices is sent back up to a height higher than the source. Throughout the iterations and at this point, the preflow property holds and coverges to having no excess flow at the vertices which also results in maximum flow as the capacity constraints hold.

#codingexercise

Void getkthlast(node head, int k, ref int count, ref node kthlast)

{

If (head == null) return;

Getkthlast(head.next, k, ref count, ref kthlast);

count = count + 1;

if (count==k) { kthlast = head; return;}

}

You have a you tube video. A person watches the video in random order. You are given the start and end time of various intervals he watched. How will you confirm whether he has watched the full video or not.

Bool hasWatchedFull( interval full, List<interval> slices)
{
Var merged = merge(slices);
If (merged.first.start <= full.start && merged.last.end >= full.end && merged.sum() == full.end - full.start) return true;

return false;

}
LIst<Interval> merge(List<Interval> slices)
{
Var s = new Stack<Interval> ();
Slices.sort(); // by starting time
If (slices.count == 0) return new List<Interval>{Interval(0,0)};
If (slices.count == 1) return new List<Interval>{slices[0]};
S.push(slices[0]);
For(int i =1; i < slices.count; i++)
{
  var top = slices.top();
  If (top.end()< slices[i].start)
      S.push(slices[i]);
  Else{
     Top.end = slices[i].end;
      S.push(top);
}
Return s.toList():
}



}

#algorithm discussion continued
Today we continue reading the flow networks. We were looking at max flow min cut theorem and the properties associated with it. We saw how it applied to Ford Fulkerson method. Each iteration of the method augmented the flow by considering a path in the residual network until there is no more. For each path considered, the residual capacity of that path is found and augmented to the flow network.
Maximum flow problems have a direct application in some combinatorial problems and we saw how it applied to matching in bipartite graphs. A maximum bipartite matching is a matching of maximum cardinality.
Maximum flows can also be calculated using "push-relabel" method. This method works in a more localized manner than Ford Fulkerson method. It works on one vertex at a time, looking only at the vertex's neighbour in the residual network. Thus it avoids examining the entire residual network to find an augmenting path. Also, they do not maintain flow conservation. Instead they maintain a preflow property which goes to say that the total flow into a vertex may exceed the flow out.

#codingexercise

In the isInterleaved method earlier, we assume that the match has to be with one of the strings and not with both based on the premise in the question. If this restriction were to be relaxed we would match both one at a time.
In this case, we could do this recursively.
 Bool isInterleaved(char* A, char* B, char* C)
{
if (*c == '/0') return true;
if (*a == '/0' && '*b' == '/0') return false;
if (*c == *a && *c == *b){
    return isInterleaved(++A, B, ++C) || isInterleaved(A, ++B, ++C);
}
if (*c == *a){
return isInterleaved(++A, B, ++C);
}
if (*c == *b) {
return isInterleaved(A, ++B, ++C);
}
return false;
}

node reverse(node head, node prev)
{
if (head==null) return prev;
head.next = prev;
return reverse(head.next, head);
}

#algorithm discussion continued
Today we continue reading the flow networks. We were looking at max flow min cut theorem and the properties associated with it. We saw how it applied to Ford Fulkerson method. Each iteration of the method augmented the flow by considering a path in the residual network until there is no more. For each path considered, the residual capacity of that path is found and augmented to the flow network.
Maximum flow problems have a direct application in some combinatorial problems and we saw how it applied to matching in bipartite graphs. A maximum bipartite matching is a matching of maximum cardinality.
To find this maximum matching, we convert the bipartite graph into a flow network in which the flows correspond to matchings. A source s and a sink v are added to either sides of the bipartite graph. We assign directed edges from L to R with unit capacity for all edges with flows and zero otherwise. This is called an integer valued flow.
If the capacity function c takes on only integral values, then the maximum flow f produced by the Ford Fulkerson method has the property that f is an integer. Moreover for all vertices u and v, the flow f(u,v) is an integer.
We can prove this by induction on the number of iterations. Let us take only one iteration. Since the Ford Fulkerson method uses residual capacity and the capacity function is integral, we know that for the first iteration, this is trivially true.
Now let us assume that the nth iteration is an integral flow network. In the next iteration, we find the residual capacity and this will be for a path not encountered earlier. In this path, the residual capacity will be found as integer because the capacity function is integral. Any addition or subtraction from integers will result in integers. Therefore, the n+1th iteration will also result in an integer flow network. Consequently the claim holds.
Another claim made is that the cardinality of maximum matching M in a bipartite graph G equals the value of maximum flow f in a corresponding flow network G'.
This follows from the contradiction that if the corresponding flow f in G' is not maximum, then there is a maximum f' corresponding to the bipartite graph that is more than f and is integral. This corresponds to a maximum matching M' greater than M which contradicts our assumption and therefore the claim holds.
Maximum flows can also be calculated using "push-relabel" method. This method works in a more localized manner than Ford Fulkerson method.
#codingexercise
Check if a given string C is an interleaving of other two strings A  and B with non repeating characters:

Bool isInterleaved(char* A, char* B, char* C)
{
While(*C)
{
If (*C == *B)
       B++;
Else if (*C == *A)
      A++;
Else
        Return false;
}
C++;
}
Return true;
}

Permutations of  a string:
Void Permute (String a, StringBuilder b, bool[] used)
{
  If ( b.Length == a.Length)  { print b.ToString(); return;}
  For (int I = 0; I < a.Length ; i++)
  {
    If (used[i]) continue;
     used[i] = true;
     B += A[i];
     Permute(a, b, used);
     B [B.Length – 1] = ‘/0’;
     used[i] = false;
  }
}

#algorithm discussion continued
Today we continue reading the flow networks. We were looking at max flow min cut theorem and the properties associated with it. We saw how it applied to Ford Fulkerson method. Each iteration of the method augmented the flow by considering a path in the residual network until there is no more. For each path considered, the residual capacity of that path is found and augmented to the flow network.
How the path is chosen is not mentioned by the method. This is usually done with Breadth First Search
We saw that with BFS, the shortest path distance for all vertices in the residual network increases monotonically with each flow augmentation. We saw that in the forward direction, when we assumed the distance to decrease, we contradicted ourselves because the next vertex  v was one hop away from the current vertex u and since this vertex was not already considered its distance was the sum of the shortest distance to current vertex and one hop. This would mean that the distance to the new vertex before and after the decrease would be the same which is a contradiction.Therefore this distance increases monotonically.
Maximum flow problems have a direct application in some combinatorial problems. The multiple-source multiple-sink maximum flow. One such example is to find the maximum matching in a bipartite graph. This can be done in O(VE) time in a G = (V,E) graph
A matching is a subset of edges M such that for all vertices v in V, at most one edge of M is incident on v. We say that a vertex v belongs to V is matched by the matching M if some edge in M is incident on V and unmatched otherwise. A maximum matching is one where the number of matchings is maximum. A graph is called bipartite when all its vertex set can be partitioned into disjoint sets L and R and all edges in E go between L and R.
To find this maximum matching, we convert the bipartite graph into a flow network in which the flows correspond to matchings. A source s and a sink v are added to either sides of the bipartite graph. We assign directed edges from L to R with unit capacity for all edges with flows and zero otherwise. Since all the flows are thus integers, the flow network is called integer valued.
If M is a matching in the bipartite graph G, then there is an integer valued flow f in flow network G' with cardinality of f to be the same as that of M. Conversely if f is an integer valued flow in G', then there is a matching M in G with cardinality M to be same as that of f. Since the flow f is maximum as found by the Ford-Fulkerson method, the cardinality of maximum matching M equals the value of maximum flow.
#codingexercise
Given an array of heights of poles. Find the no of poles which are visible if you are standing at the kth pole.
int Getvisible(List<int>h, int n, int k)
{
var left = new int[n]{};
var right = new int[n]{};
int count = 1; // the current pole

left[0] = h[0];
for (int i = 1; i < n; i++)
   left [i] = max(left[i-1], h[i]);

   right[n-1] = h[n-1];
    for (int i = n-2; i >= 0; i--)
       right[i] = max(right[i+1], h[i]);

for (int i =k-1; i >= 0; i--){
      count++;
      if(h[i] != left[k])
          break;
}
for (int i =k+1; i < n; i++){
      count++;
      if (h[i] != right[k])
          break;
}
return count;
}

Connecting AWS connector with Okta 

Many organizations participate in multi factor authentication for their applications. At the same time, they expect the machines deployed in their private cloud to be joined to their corporate network. If this private cloud were to be hosted on the AWS as a VPC, it would require some form of AD Connector to talk to the on-premise Active Directory. The AD connector is a proxy and the Active directory is on – premise for the entire organization.  In this writeup targeted at a software developer audience, I explain how to configure AWS connector with Okta. 

We use AWS to connect AD using the Okta agent. The Okta AD or LDAP agent is downloaded and installed on any Windows Server with access to the Domain Controller. The Okta LDAP agent is downloaded to the Linux environment. 

We can eliminate login and password hassles by connecting the AWS with existing corporate credentials. 

Further more, for new credentials, this lets us automatically provision, update or deprovision AWS accounts when we update AD or LDAP.  

#codingexercise
Given a bst and a lower boundary values. Prune the tree if the node data lies over the boundary values

Node trimRangeLower( node root, int min)

{

If (root == null) return root;

root.left = trimRangeLower(root.left, min,);

root.right = trimRangeLower(root.right, min);

If (root.data < min)

{

Var right = root.right;

 delete root;

  Return right;

}

Return root;

}
Given a bst and a higher boundary values. Prune the tree if the node data lies under the boundary value
Node trimRangeHigher( node root, int max)

{

If (root == null) return root;

root.left = trimRangeHigher(root.left, max);

root.right = trimRangeHigher(root.right, max);

If (root.data > max )

{

Var left = root.left;

 delete root;

  Return left;

}

Return root;

}