#codingexercise
Given a BinaryTree and a value, check if the path sum from root to leaf equals the given value.
bool hasPathSum(Node root, int sum)

{

if (root ==null) return sum == 0;

int newsum = sum-root.data;

if (newsum == 0 && root.left == null && root.right == null) return true;

return hasPathSum(root.left, newsum) || hasPathSum(root.right, newsum);

}

Find the maximum sum from root to leaf in a binary tree

void maxPathSum(Node root, ref int sum, ref int max)

{

if (root == null) { if (sum > max) max = sum; return;}

sum += root.data;

maxPath(root.left, ref sum, ref max);

maxPath(root.right, ref sum, ref max);

sum-= root.data;

}
Print all root to leaf paths
void getAllPaths(Node root, ref List<Node> candidate, ref List<List<Node>> paths )
{
if (root == null) { paths.Add(candidate); return;}
candidate.add(root);
getAllPaths(root.left, ref candidate, ref paths);
getAllPaths(root.right, ref candidate, ref paths);

candidate.removeLast();

}

Find the max sum between any two leaves
int maxLeavesSum(Node root, ref int leavesSum)
{
if (root == null) { leavesSum = 0; return;}
if (root.left == null && root.right == null){ leavesSum = root.data; return root.data;}
int ls = maxLeavesSum(root.left, ref leavesSum);
int rs = maxLeavesSum(root.right, ref leavesSum);
if (root.left && root.right)
{
leavesSum = max(leavesSum, rs+ls+root.data);
return max(ls,rs)+root.data;
}
return (!root.left) ? rs + root.data : ls + root.data;
}

#codingexercise
Given a BinaryTree and a value, check if the path sum from root to leaf equals the given value.
bool hasPathSum(Node root, int sum)

{

if (root ==null) return sum == 0;

int newsum = sum-root.data;

if (newsum == 0 && root.left == null && root.right == null) return true;

return hasPathSum(root.left, newsum) || hasPathSum(root.right, newsum);

}

Find the maximum sum from root to leaf in a binary tree

void maxPathSum(Node root, ref int sum, ref int max)

{

if (root == null) { if (sum > max) max = sum; return;}

sum += root.data;

maxPath(root.left, ref sum, ref max);

maxPath(root.right, ref sum, ref max);

sum-= root.data;

}
Print all root to leaf paths
void getAllPaths(Node root, ref List<Node> candidate, ref List<List<Node>> paths )
{
if (root == null) { paths.Add(candidate); return;}
candidate.add(root);
getAllPaths(root.left, ref candidate, ref paths);
getAllPaths(root.right, ref candidate, ref paths);

candidate.removeLast();

}

Today we discuss a few more coding problems :
Given a MXN matrix. To find the number of ways to reach the mth row and nth column cell from 0,0 cell. Find the same if some of the cells are marked as not reachable.

We can use backtracking here

void numPaths(int N, Point start, Point end, ref List<Point> paths, ref List<Point> candidate)

{
if (start == end) {paths.Add(candidate); return;}

for (int i = 0; i < 3; i++) // for one of three directions to take

{

var next = start.adjacents(i);

if (next.isValid() != true || next.isBlocked()) continue;

candidate.Add(next);

if (next == end) { paths.Add(candidate);}

if (next != end && candidate.Count < N)

      numPaths(next, end, ref paths, ref candidate);

candidate.RemoveLast();

} 

}

Given a BST Find maximum k elements in a tree
We can do this with inorder traversal because it will list the elements in sorted order
void KLarge(node root, ref Queue<node> window)
{
if (root == null) return
KLarge(root.left, ref window)
if (window.Count < K){
    window.enqueue(root);
}else{
   window.dequeue();
   window.enqueue(root);
}
KLarge(root.right, ref window);
}

Incidentally we can do this in steps by finding the Kth largest element before finding the N-K elements
by doing a reverse inorder traversal
KthLargest(Node root, int k, ref int visited)
{
if (root == null || visited >= k) return;
KthLargest(root.right, k, visited);
visited++;
if (visited == k)
{
 print(root.data); 
}
KthLargest(root.left, k, visited);
}
or print the large k elements in descending order
void getKLarge(node root, ref int k)
{
if (root == null || k == 0) return;
getKLarge(root.right, k);
k--;
print(root.data);
getKLarge(root.left, k);
}

Today we practice a few more coding questions:
Given two rectangles, find whether they are overlapping or not?
static bool intersects(Rectangle r1, Rectangle r2)
{
bool isdisjoint = false;
// are  they disjoint along x axis ?
if (r1.tl.x < r2.tl.x)
   isdisjoint = r1.br.x < r2.tl.x;
else
  isdisjoint = r2.br.x < r1.tl.x;
if (isdisjoint == true) return false;

// are they disjoint along y-axis ?
if (r1.br.y < r2.br.y)
   isdisjoint = r1.tl.y < r2.br.y;
else
  isdisjoint = r2.tl.y < r1.br.y;
return isdisjoint == false;
}

Given a String s and int r , first fill each character row wise and print column wise.

for e.g. String s = “abcdefgh” and r = 3
so filling column wise would give :
a d g
b e h
c f

and final answer would be adgbehcf.

string GetRearranged(string s, int r)

{

var ret = new stringbuilder(s.length);

int start = 0;

int k = 0;

for (int i = 0; i < s.length; i++)

{

if (start + k*r) < s.length){

     ret[i] = s[start + k * r];

     k = k + 1;

}else{

     k = 0;

     start++;

     ret[i] = s[start + k * r];

     k = k + 1;

}

}

return ret.toString();

}

3) Node findLCAInBT(Node root, int n1, int n2, ref bool v1, ref bool v2)
{
if (root == null) return null;
if (root.key == n1) {
v1 = true;
return root;
}
if (root.key == n2){
v2 = true;
return root;
}
var left = findLCAInBT(root.left, n1, n2, ref v1, ref v2);
var right = findLCAInBT(root.right, n1, n2, ref v1, ref v2);
if (left && right) return root;
if (left != null) return left;
else return right;
}
if ( v1  && v2 || v1 && find(lca, n2) || v2 && find(lca,n1))
     return lca;

4) Implement k stacks in an array
Use the following auxiliary data structures
an array to store the top of all k stacks. This is initialized to -1 for each stack
an array to store the next element index for all n elements. This is initialized to the next element for all but the last
a free variable pointing to the first available slot. This is initialized to the first one (free = 0)
void push(int val, int k-at-i)
{
//check for overflow and then
int i = free;
free = next[i];
next[i] = top[sn];
top[k-at-i] = i;
arr[i] = item;
}

void pop(int k-at-i)
{
//check for underflow and then
int i = top[k-at-i];
top[k-at-i] = next[i]
nex[i] = free;
free = i;
return array[i];
}

Today we practice a few more coding questions:
Given two rectangles, find whether they are overlapping or not?

Some more VMWare techniques continued from the previous two post:
1) Clone a VM:
Specify a RelocateSpec
Specify a CloneSpec
Execute the CloneVM Workflow
The specs can be completed using the information from the virtual machine target to clone.
2) Take a snapshot of the VM:
snap_info = vm.snapshot
tree = snap_info.rootSnapshotList
while tree[0].childSnapshotList is not None:
    print("Snap: {0} => {1}".format(tree[0].name, tree[0].description))
    if len(tree[0].childSnapshotList) < 1:
        break
    tree = tree[0].childSnapshotList
3) Print VM info
def print_vm_info(virtual_machine):
    summary = virtual_machine.summary
    print("Name       : ", summary.config.name)
    print("Template   : ", summary.config.template)
    print("Path       : ", summary.config.vmPathName)
    print("Guest      : ", summary.config.guestFullName)
    print("Instance UUID : ", summary.config.instanceUuid)
    print("Bios UUID     : ", summary.config.uuid)
    annotation = summary.config.annotation
    if annotation:
        print("Annotation : ", annotation)
    print("State      : ", summary.runtime.powerState)
    if summary.guest is not None:
        ip_address = summary.guest.ipAddress
        tools_version = summary.guest.toolsStatus
            print("VMware-tools: ", repr(tools_version))
            print("IP         : ", repr(ip_address))
    print("")

#codingexercise
A knight on a chess board has to move from a start to a finish position. Find if the position is reachable and the minimum number of steps to take.
Int knightMoves (point[,] board, int N, point x, point y)
{
Add the starting point to a queue
While queue is not empty
     Extract a point
     If point == destination return
     If point already visited continue
     For each of eight moves the knight can make
        Enqueue the point

Return -1;
}

#codingexercise
Multiply two linked lists representing large numbers without using additional lists.
List <int> multiply (list <int> first, list <int> second)
{
Int len1 = first.count;
Int len2 = second.count;
First.addRange (second);
Second.reset ();
Int start = 0;
For ( int I = len1- 1; I>=0; i--){
   For ( int j = len1+len2-1;j>=0; j- -)
    Second.cumulate_with_carry_over (first, len1, i,j, start);
    Start++;
}
Return second;

]
}

static void cumulate_with_carry_over(this List<int> second, List<int>first, int len1, int i, int j, int start)
{
int product = first[j]*first[i];
// add product to second at start+j
int val = second[start+j] + product

  carryover = val/10;
    operand = val %10;
Second  [start+j] = operand;
Int k = j- 1;
While (carryover != 0){
Val = second[start +k] +carryover ;
if (val/10 > 0){
    carryover = val/10;
    operand = val %10;
}else{
    carryover = 0;
    operand = val
}
if start+k<= 0
    Second  [start+k] = operand;
     second.InsertAt(0, carryover);
     Carryover = 0
else
    second[start+k] = operand;
    //second[start+k-1] += carryover'
}
K = k- 1;
}
return;
}
    123
  *123
----------
    369
  246x
123xx
----------
14829
 We review some more more common tasks with vCenter along the lines of the ones mentioned in the previous post:
To deploy an OVF:
1) first read the ovf file and get the descriptor
2) parse the descriptor to get datacenter, datastore and resource_pool
3) Create an import spec with the above parameters
4) Take an HttpNFCLease and keep it alive while posting the vmdk

To Reboot VM:
print "The current powerState is: {0}".format(VM.runtime.powerState)
TASK = VM.ResetVM_Task()
tasks.wait_for_tasks(SI, [TASK])

To Rename a VM
# rename creates a task...
task = obj.Rename(new_name)