#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();
}

 

We were discussing the flow networks and the Ford Fulkerson method. It introduced us to residual network, augmenting paths and cuts. These are used in the max-flow min-cut theorem which explains the maximum flow in terms of cuts
Residual network consists of edges  with capacities that represent how we can change the flow on the edges of G. This is typically seen as the amount of flow that an edge can admit  and is equal to the edge's capacity minus the flow on that edge. If that value is positive, then it is included into the residual network and are excluded otherwise.  But it may also contain edges that are not in G. For example an edge whose flow has been decreased by admitting a counter flow from the opposite direction that can at most cancel out the flow is also part of residual network.
These reverse edges in the residual network allow an algorithm to send back flow that it has already sent on an edge.
The residual capacity cf(u,v) is therefore defined as
cf(u,v) = c(u,v) - f(u,v) if (u,v) belongs to E
            = f(u,v)              if (v,u) belongs to E
             = 0                    otherwise
 The above equation covers all the three cases of admitting a positive, negative or unchanged flow in terms of capacity.
Each edge of a residual network is a residual edge.
Augmentation of a flow by f to f' is defined as the previous flow f + the increase in the flow in the forward direction - the decreased flow in the reverse direction.  If the augmentation does not happen, the flow is unchanged.
Some of the lemmas associated with the maximum flow algorithm include the following:
Let G = (V,E)  be a flow network with source s and sink t, and let f  be a flow in G. Let Gf be the residual network of G induced by f and let f' be a flow in Gf.  Then the augmentation is defined as a flow in G with value equal to the individual magnitude of the two flows.
Another lemma is that if f is a flow in G and and p is an augmenting path
then the flow along the path between u and v in the residual network is the residual capacity of the path if (u,v) is on the path or zero otherwise. This binary definition of the flow along the path suggests that either and edge is counted or it isn't and when it is, the residual capacity of the path and not just between (u,v) determines the flow in the residual network.
#puzzles
Two children - a boy and a girl play in the mud. Their mother states at least one of them has a muddy head. Then she asks them if they know whether they have a muddy head. What will the children answer if they speak the truth.
The children will say No first and Yes afterwards collectively.
Let s be the statement that the son has a muddy head
Let d be the statement that the daughter has a muddy head
The mother statement is true but the kids don't see their own head  so they don't know if their head is muddy and answer no.
subsequently, each one has an additional information from their response given earlier and therefore know their state.  They would have known their respective state even if both of them answered yes in the first place.
#codingquestion
 Given n ropes of different length, combine them into a single rope,such that total cost is minimum. You can tie two ropes at a time,and cost of tying is sum of length of ropes.
Int getmin (list <int> Len)
{
Int cost = 0
Heap h = build_heap(len)
While (h.size () >1)
{
First = extract_min (h)
Second = extract_min (h)
Cost += first + second
H.insert (first+second );
}
Return cost;
}
bool  hasPythagoreanSum(List<int> sorted)
{
    assert(sorted.all(x=>x> 0));
    sorted.sort();
    Int len = sorted.count;
    For (int i=0; i<len; i++)
    {
          Int start = I + 1, end = len-1;
          While (start<end)
          {
            int sum = sorted[i] ^ 2 + sorted[start] ^2;
            int target = sorted[end] ^ 2;
            If (sum  ==  target)
            {
                return true;
            }
            If (sum  < target)
            {
                     start++;
            }
           Else
           {
               end--;
           }
      }      
  }
   Return false;
}

Find excel column name from given number for example
26 Z
52 AZ
702 ZZ
String getColName(int n)
{
Stringbuilder ret;
Int i = 0;

While(n)
{
Int rem = n%26;
If (rem==0)
{
Ret[i++] = 'Z';
N = n/26 -1;
}
Else{
Ret[i++] = 'A' +(rem-1);
N = n/26;
}
}
Ret += '/0';
Ret.reverse();
Return ret.toString();
}
This could also be done as pre compitations from powers of 26
For example 26 power 1 is Z
26 power 2 exceeds 52.
So 52 must be some multiple of 26 and offset from the previous computation which is Z. Since (52 -26) / 26 = 1, we have AZ and so on.

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;
}
}