Today we continue to discuss flow networks and the max flow problem. In particular, we discuss the Ford Fulkerson method. In the maximum-flow problem, we are given a flow network G
with source s and sink t , and we wish to find a flow of maximum value. A maximum flow problem may have several sources and sinks but these are not treated any different from a single source and sink.
The Ford-Fulkerson method depends on three important ideas that transcend the method and are relevant to many flow algorithms and problems: residual networks, augmenting paths, and
cuts.  This method iteratively increases the value of the flow. We start with f (u,v) =  0 for all u,v  belonging to V and giving an initial flow of value 0. At each
iteration, the flow value in G is increased by finding an “augmenting path” in an
associated “residual network” Gf . Once the edges of an augmenting
path in Gf is known , specific edges in G can be identified for which the flow  can be changed so as to increase the value of the flow. Although each iteration of the
Ford-Fulkerson method increases the value of the flow, the flow
on any particular edge of G may increase or decrease; decreasing the flow on some
edges may be necessary in order to enable an algorithm to send more flow from the
source to the sink. The flow is augmented repeatedly until the residual network has
no more augmenting paths. The max-flow min-cut theorem will show that upon
termination, this process yields a maximum flow.
FORD-FULKERSON-METHOD(G,s,t)
   initialize flow f to 0
   while there exists an augmenting path p in the residual network Gf
   augment flow f along p
   return f

# puzzle
It’s summer time and three of the college friends, A, B and C went to sports club to enjoy the vacation. They saw an interesting game being played there.
Game name is “hit and win”. There was a triangular setup of green ropes on ground. You have to move on the triangular path and on the turn you have to hit other mate using paper ball until only one is left for winning.
A’s chances of hitting is 0.3.
B has hitting chance of 0.5 .
C has 100% chance of hitting the target.
If a person is hit, he is out from path and cannot take a turn.
Suppose order of throwing balls is A, B, C. You being close to A, what strategy would you suggest A for having maximum chance of winning.

The order is A, B, C
if A misses B and C eliminate either of them and A has a chance to eliminate the remaining.

#coding interview
Find distance between two nodes in a binary tree
Distance between nodes can be found out this way:
dist(n1, n2) = dist(n1, root) + dist(n2, root) - 2 * dist(root, lca)

int getDistance(node root, int n1, int n2)
{
if (root == null)  return;
int d1 = INT_MAX;
int d2 = INT_MAX;
int distance = 0;
int level = 1;
node lca = getlca(root, n1, n2, ref d1, ref d2, ref distance, level);
if (d1 != INT_MAX  && d2 != INT_MAX)
   return distance;
if (d1 != INT_MAX) // n1 is ancestor of n2
{
    distance = getlevel(lca, n2);
    return distance
}
if (d2 != INT_MAX) // n2 is ancestor of n1
{
    distance = getlevel(lca, n1);
    return distance;
}
return INT_MAX;
}

node getlca(node root, int n1, int n2, ref int d1, ref int d2, ref distance, int level)
{
if (root == null) return null;
if (root.data == n1){
d1 = level;
return root;
}
if (root.data == n2){
d2 = level;
return root;
}
var leftlca = getlca(root.left, n1, n2, ref d1, ref d2, ref distance, level+1);
var rightlca = getlca(root.right, n1, n2, ref d1, ref d2, ref distance, level+1);
if (leftlca && rightlca)
{
distance = d1 + d2 - 2 * level;
 return root;
}
if (leftlca != null){
      return leftlca;
}else{
      return rightlca;
}
}