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
When the BFS is used to choose the augmenting path as a shortest path from s to t in the residual network, where each edge has unit distance, the algorithm is then called Edmonds-Karp algorithm
It can be shown that with this algorithm for all vertices, the shortest path distance in the residual network increases monotonically with each flow augmentation.
#puzzle
There are 3 ants sitting on three corners of a triangle. All ants randomly pick a direction and start moving along edge of the triangle. What is the probability that any two ants collide?
There are two choices for each ant that  makes the total number of possibilities as 2 ^ 3 = 8
Out of these only two  - clockwise and anticlockwise movements will not result in a collision. So the answer is 6/8
#coding interview
How do we sort an array consisting of three elements 0,1, 2 without counting ?
We use the Dutch National Flag Algorithm
This algorithm is described as
Divide the array into four regions:
1 to Low -1 as all zeros
Low to Mid - 1 as all ones
Mid to High as unknown
and High+1 to N as twos

Initially Low is set to 1, Mid is set to 1 and High to N and we shrink the unknown by swapping the mid element with the corresponding region.
while mid <= Hi
    if A[mid] == 0 Swap(A,low,mid) low++ mid++
    if A[mid] == 1 Mid++;
    if A[mid] == 2 Swap(A,mid, high) high--

void SortThrees(List<int> nums)
{
assert(nums.all(x => x == 0 || x == 1 || x == 2));
int N = nums.Count;
int low = 1;
int mid = 1;
int high = N;
while ( mid <= high)
{
switch(A[mid-1])
{
case 0: {Swap (ref nums, low-1, mid-1); low++; mid++; break;}
case 1: { mid++, break;}
case 2: {Swap(ref nums, mid-1, high-1); high--; break;}
default:
       raise Exception("Invalid element");
       break;
}
}
}

There are other approaches possible to merging the Binary Search Tree

1) Add the elements of one tree to the other one at a time by moving the root until there are no more nodes in the tree 

2) Transform one of the trees into inorder and insert the items into the other tree. 

3) Jointly traverse both trees to find the minimum in either tree, delete it and add to a new BST 

  

Deleting a node from a tree 

Node TreeDelete(ref node root, node z) 

{ 

If (z==null) return NULL; 

If (root == null) return NULL; 

Node y  = null; 

If (z.left == null || z.right ==null) 

       Y = z; 

Else 

      Y = TreeSuccessor(ref node, z) ;

X = null ;

If (y.left != null)  

                X = y.left ;

else 

                x = y.right ;

If (x != NULL) 

                x.parent = y.parent ;

If (y.parent == NULL) 

                Root = x ;

 Else if (y = y.parent.left)

          then 

             y.parent.left = x ;

         else 

             y.parent.right = x ;

if (y != z )

    then z.data = y.data ;

return y 

} 

  

void TreeInsert(Node tree1, Node z) 

{ 

Node Y = NULL; 

Node x = tree1; 

While (x != NULL){ 

      Y = X; 

       If  (z.data  < x.data) 

           X= x.left; 

     Else 

           X = x.right;  

z.parent = y; 

if (y == NULL) 

        tree1 = Z; 

else if (z.data < y.data) 

             z = y.left; 

        else 

            z = y.right; 

} 

  

} 

Node Merge(Node tree1, Node tree2) 

{ 

Node current = tree2; 

While (current) 

{ 

Var root = TreeDelete(ref tree2, current); 

TreeInsert(ref tree1, root); 

Current = tree2; 

} 

Return tree1; 

}
Node TreeSuccessor(Node x)
{
If (x == null) return null;
If (x.right) return TreeMinimum(x.right);
Node y = x.parent;
While(y != null && y.right == x){
    X = y;
    Y = y.p;
}
Return y;
}

Node TreePredecessor(Node x)

{

If (x == null) return null;

If (x.left) return TreeMaximum(x.left);

Node y = x.parent;

While(y != null && y.left == x){

    X = y;

    Y = y.p;

}

Return y;

} 

Node TreeMinimum(node root)
{
If(root == null) return null;
Node current = root;
While(current && current.left)
       Current = current.left;
   Return current;
}

Node TreeMaximum(node root)
{
If(root == null) return null;
Node current = root;
While(current && current.right)
       Current = current.right;
   Return current;

}

#codingexercise

Merge two Binary Search Trees(BST)

Node Merge(Node tree1, Node tree2)

{

var in1 = new List<int>();

InOrder(Node tree1, ref in1);

var in2 = newList<int>();

InOrder(Node tree2, ref in2);

var result = in1.Merge(in2);

return ToBST(result, 0, result.count-1);

}

void InOrder (Node root, List<int> tree)

{

if (root == null) return;

InOrder(root.left);

tree.add(root.data);

InOrder(root.right);

}

Node ToBST(List<int> nums, int start, int end)

{

if (start > end) return null;

int mid = (start + end) / 2;

var root == new Node();

root.data = nums[mid];

root.left = ToBST(nums,start, mid-1);

root.right = ToBST(nums, mid+1, end);

return root;

}

Another method to do this is to use two auxiliary stacks for two BSTs.  If we get a element smaller from the trees, we print it. If the element is greater, we push it to the stack for the next iteration.

We use the iterative inorder traversal :

-          Create an empty stack S

-          Initialize current node as root

-          Push the current node to stack S, set current to current.left, until current is NULL

-          If the current is null and stack is not empty then

o   Pop the top item from stack

o   Print the popped item

o   Set current = popped_item.right

o   Goto step 3

-          If current is null and the stack is empty, then we are done.

To merge the BST we do the following:

Initialize two stacks s1 and s2 from null.

If the first tree is null, do iterative inorder traversal of second to print the merge

If the second tree is null, do iterative inorder traversal of first to print the merge

Set current in tree 1 to be cur1 and current in tree 2 to be cur2

While either cur1 or cur 2 is not null or  one of the stacks is not empty:

-          If cur 1 or cur 2 is not null

o   For both the tree, if the current is not null, push it onto the stack, set current to current.left This will be repeated by the while until current is nul is null

-          Else

o   If either of the stacks is empty, then one tree is exhausted, print the other tree.  Do this for both stacks.

o   Set the current of each tree to the popped element from respective tree

o   Compare the two current and execute an iteration of step3 from iterative inorder traversal above  - the smaller of the two current nodes is printed, the larger pushed back on its corresponding stack

At the end of the while loop, both stacks should be empty and the currents must be pointing to null and both the trees would be printed.

There are other approaches possible:

1) Add the elements of one tree to the other one at a time by moving the root until there are no more nodes in the tree
2) Transform one of the trees into inorder and insert the items into the other tree.
3) Jointly traverse both trees to find the minimum in either tree, delete it and add to a new BST

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. However the method greatly depends on this choice. If the path is chosen poorly, the method might not even terminate. It may increase the augmentations but the method need not even converge to a maximum value.  On the other hand, if the path is chosen by using a breadth first search, the algorithm runs in polynomial time.
A breadth first search proceeds like this:
BFS(G,s)
for each vertex u belonging to V - s
       u.color = white
       u.parent = nil
       u.d = infinity
s.color = gray
s.parent = nil
s.d = 0
Initialize a Queue Q
Enqueue(Q,s)
while Q is not empty
        u = Dequeue(Q)
        for each v belonging to Adj(u)
              if v.color == white
                  v.parent = u
                  v.d = u.d + 1
                  v.color = gray
                  Enqueue(Q,v)
        u.color = black
With this traversal, the maximum number of times the Ford Fulkerson method may be run to achieve a max flow f is f times because the flow increase by at least one unit in each iterartion. The time to find a path with BFS is O(V+E) = O(E) Each iteration of the while loop takes O(E) times and the total running time as O(E) * f

#puzzle
A man is allocated a task. He doubles the task done everyday. If the man completely does the task in 18 days, how many days did it take for the man to complete 25% of the task?
This is another example of where a solution is arrived at faster by working backwards from the end. In this case the full task was done in 18 days, therefore half task was done in 17 days and a quarter task was done in 16 days.  If we were to form an algebraic equation as
(x + 2x + 4x + .... 2 ^ 17 x) = 18 and then determine x to compute the first sixteen terms it would take longer.

There is an 8 by 8 chessboard in which two diagonally opposite corners have been cut off.You are given 31 dominos, and a single domino can cover exactly two squares. Can you use the 31 dominos to cover the entire board?
If we remove two squares of opposite colors each we are left with 64 -2 = 62 blocks which can be covered with thirty one dominoes equally. However by cutting the opposite corners, we are eliminating two squares of same colors which leaves us with unequal number of blacks and whites and therefore a solution is not possible.

#codinginterview
Given a set of n points in a cartesian coordinate plane, find the k closest to the origin

List<Point> GetClosestToOrigin(List<Point> points)
{
points.Sort(delegate(Point a, Point b)
{
  if (a == null && b == null) return 0;
  else if (a == null) return -1;
  else if (b == null) return -1;
  else return a.CompareTo(b);
});
return points.GetRange(0,k);
}

public class Point : IComparable {
:
public int CompareTo(object obj)
{
          // A null value means that this object is greater.
        if (obj == null)
            return 1;
        Point that = obj as Point;
        if (that == null)
            throw new ArgumentException("Object is not a Point");
        int thisdistance = this.x * this.x + this.y * this.y;
        int thatdistance = that.x * that.x + that.y * that.y;
       if (thisdistance < thatdistance) return -1;
       if (thisdistance > thatdistance) return 1;
       return 0;
}
:
}

Today we continue reading the flow networks. In particular, we look at the max flow min cut theorem. A cut of the flow network is a partition of its vertices into set S and T = V- S such that s belongs to S and t belongs to T. A minimum cut of the network is a cut whose capacity is the minimum over all cuts in the network. The max flow min cut theorem states the following:
1) f is a maximum flow in network.
2) there are no augmenting paths in the residual network.
3) the magnitude of the flow is the capacity of the cut for some cut (S,G)
This is proved by contradiction. The first implies the second. If there is an augmenting path in the residual network while there is a maximum flow in the network, the maximum flow can be exceeded with the augmentation. The second implies the third because if the residual network does not have any flows  the a cut between vertices s and t that do not have a path will have only forward flow and no reverse flow which implies it is the capacity.
The Ford Fulkerson method makes use of this property.  In each iteration of the method, an augmenting path p is found and used to modify the flow f. The residual capacity of that path is found and augmented to the flow. For each edge u,v in this path p, if it already exists in the edges E, we add the residual capacity in the forward direction or reduce it in the reverse direction.  In other words, each edge encountered is either an edge in the original network or its reversal.  The algorithm repeatedly finds paths until there are no more. At that point, we have maximum flow.
This is written as :
Ford-Fulkerson(G, s, t):
for each edge (u,v) belonging to G, E
      (u,v).f = 0
while there exists a path p from s to t in the residual network Gf
      cf(p) = min{cf(u,v): (u,v) is in p}
      for each edge (u,v) in p
            if (u,v) belongs to E
                (u,v).f = (u,v).f + cf(p)
            else (v,u).f = (v,u).f  - cf(p)

#puzzle
A car has 4 tyres and 1 spare tyre. Each tyre can travel a maximum distance of 20000 miles before wearing off. What is the maximum distance the car can travel before you are forced to buy a new tyre? You are allowed to change tyres (using the spare tyre) unlimited number of times.

The idea is to use all the tyres to the full. So we rotate the spare tyre in each of the four positions. This gives us a rotation at every 5000 miles and the total distance traveled as 25000 miles.

#codingexercise
Find two numbers with a given sum in an array
void PrintPairsWithSum(List<int> num, int sum)
{
assert(num.all(x => x < sum));
var h = new Hashtable();
for (int I = 0; I < num.count; i++)
{
 int other = sum - num[I];
 if (other > 0 && h.Contains(sum-num[I]) && h[sum-num[I]] == 1)
      Console.Write(num[I], other);
h[num[I]]  = 1;
}
}
Int getTurningPoint(List<int> num)
{

For(int i = 1; i < num.count; i++)
     If (num[i-1] < num[i])
     Return i;
Return -1;

}

Today we continue reading the flow networks. In particular, we look at the max flow min cut theorem. A cut of the flow network is a partition of its vertices into set S and T = V- S such that s belongs to S and t belongs to T. A minimum cut of the network is a cut whose capacity is the minimum over all cuts in the network. The max flow min cut theorem states the following:
1) f is a maximum flow in network.
2) there are no augmenting paths in the residual network.
3) the magnitude of the flow is the capacity of the cut for some cut (S,G)
This is proved by contradiction. The first implies the second. If there is an augmenting path in the residual network while there is a maximum flow in the network, the maximum flow can be exceeded with the augmentation. The second implies the third because if the residual neywork does not have any flows  the a cut between vertices s and t that do not have a path will have only forward flow and no reverse flow which implies it is the capacity.

Yesterday we were discussing the flow networks and the Ford Fulkerson method.  It introduced us to residual network, augmenting paths and cuts. We saw how residual networks help with maximizing flow. We read  a few lemmas for residual networks.
 The first lemma was about augmentation using the flows in both the networks. The second lemma was about the binary definition of the flow along the path.  We can combine the first and second lemma into a corollary as follows: If G is a flow network, f is a flow in G, p is an augmenting path in G and fp is defined with capacity constraint along path p and then we augment f by fp, Then the function f increased by fp is a flow in G with values individually from f and fp taken together which should exceed f.
By repeatedly augmenting, we increase the flow in the network. But to be sure we have reached the maximum, we use the max flow min cut theorem which tells us that the flow is maximum if and only if the residual network contains no augmenting path. To look into this theorem, we first describe a cut of the flow network as a partition of its vertices into set S and T = V- S such that s belongs to S and t belongs to T. As we flow is depicted by directional edges. If f is a flow, then the net flow f(S,T) across the cut is defined to be the sum of all flows over all vertices belong to S and over all vertices belonging to T in the forward direction reduced by the same in the reverse direction.
 This aggregation over the vertices of T before the aggregation over the vertices of  S is also similarly performed to compute the capacity of the cut. A minimum cut of the network is a cut whose capacity is the minimum over all cuts in the network.
#puzzle
100 coins are lying flat on a table. 10 of them are heads up and 90 are tails up. How can we split the coins into two piles such that there are same number of heads up in each pile?
We make two piles
say one has 88 Tails and 2 Heads
and the other has 2 Tails and 8 Heads
Now we just invert the second pile because the tails and heads are binary and inverting one means we balance x and 10 - x in both piles.
Taking this example, we have after inverting the second pile  8 Tails and 2 Heads.

A Policeman decided to punish a prisoner and asked him to make a statement. The prisoner should make such a statement such that he is spared. The rules are that if the statement is held true by Policeman, the prisoner will be hanged to death and if the statement is held false, the prisoner will be shot dead.
Solution: The prisoner claims he will be shot dead.  If it turns out to be true, he will be hanged which would invalidate the statement. If it turns out to be false, he would be shot which would again invalidate the statement.
Yesterday we were trying to find excel column name from given number but the idea remains the same as in the previous post. Please refer the previous post for the solution.
We try an alternative today
string ToName(int col)
{
 Stringbuilder ret;
int power = 1;
int value = col;
for (int I = 1; I < INT_MAX && Math.Pow(26,i) < value; i++)
{
 power = I;
ret.add('Z');
value -= Math.Pow(26,i);
}
int remainder = col - Math.Pow(26, power);
if (remainder % 26 == 0) ret.add('A')
else
ret.add('A' + remainder%26-1);
ret.reverse();
return ret.ToString();
}