This is a continuation of the series of coding exercises from previous posts to see a sample of the interview questions being asked.

#codingexercise
1. An Array of buildings is facing the sun. The heights of the buildings is given in an array, Find out which all buildings will see the sunset.
List<int > SeeSunsetBuildings(List<int> heights)
{
var ret = new List<int>();
if (heights.Count == 0) return ret;
int min = heights[0];
for (int i =1; i < heights.Count; i++)
{
if (heights[i] > min)
    ret.Add(heights[i])
}
return ret;
}
2. Print all nodes at a distance k from a given node
void printKDistanceDown(Node root, int k)
{
if (root == null || k < 0) return;
if (k == 0)
   Console.Write(root.data);
printKDistanceDown(root.left, k-1);
printKDistanceDown(root.right, k-1);
}

// returns distance of root from target
int PrintKDistanceNode(Node root, Node target, int k)
{
if (root == null) return -1;
if (root == target){printKDistanceDown(root, k); return 0;}
int dl = printKDistanceNode(root.left, target, k);
if (dl != -1)
{
   if (dl + 1 == k)
       Console.Write(root.data);
   else
       printKDistanceDown(root.right, k -dl-2);
   return 1 + dl;
}
int dr = printKDistanceDown(root.right, target, k);
if (dr != -1)
{
      if (dr +1 ==k)
         Console.Write(root.data);
      else
          printKDistanceDown(root.left, k-dr-2);
      return 1+dr;
}
return -1;
}

3. Count the decoding for a given digit string. Let say ‘A’ -> 1, B -> 2 and so on
 Eg : Input: digits[] = “123”
Output: 3  //”ABC”, “ LC” ,  “AW”

bool GetCode(string digits, ref stringbuilder candidate, ref int count)
{
if (digits.length == 0) { Console.Write(candidate.toString()); count += 1; return true; }
for (int i =0; i < 2 && i<=digits.length; i++)
{
  int code = int(digits.Substring(0,i+1);
  if (code >=1 && code <=26){
         candidate.add(lookup(code));
        if ( GetCode(digits.GetRange(i+1,digits.length-i-1), ref candidate,  ref count))
         return true;
}
return false;
}

Find the maximum sum root to leaf in a tree

Void getLeafMax ( node root, int sum,  ref int max)
{
If (root == null) return;
Sum += root.data;
If (root.left == null && root.right == null)
{
If sum > max
    sum = max;
}
Getleafmax (root.left, sum, max);
Getleafmax (root.right, sum, max);

I haven't seen an example in node.js where an http response stream is piped to a downloadable file. So here it goes :

var path = require('path');

var mime = require('mime');



app.get('/download', function(req, res){



  var file = __dirname + '/upload-folder/dramaticpenguin.MOV';



  var filename = path.basename(file);

  var mimetype = mime.lookup(file);



  res.setHeader('Content-disposition', 'attachment; filename=' + filename);

  res.setHeader('Content-type', mimetype);



 var options = {

    host: 'sourceserver.com',

    port: 443,

    path: '/resource/',

    method: 'get',

    headers: {

    'Content-Type': 'application/octet-stream',

    'Authorization': 'Basic some_token',

    }

  };

  var httpreq = https.request(options, function (response) {

   // a response is a readable stream

   response.pipe(res);

   });

   httpreq.end();

});

#codingexercise
 A linked list has values sorted by absolute values. Sort the linked list by actual values
 void SortByActual(ref Node root)
{
if (root == null) return;
Node prev = root;
Node curr = prev.next;
while ( curr != null)
{
 if (curr.data < prev.data)
{
prev.next = curr.next;
Push(ref root, curr);
curr = prev;
}
else{
prev = curr;
}
curr = curr.next;
}

}

#programming interview questions
Determine cycles in graphs
Topological sort discussed in the previous blog post can help detect cycles. It is a linear ordering of all vertices along a horizontal line so that all the directed edges go from left to right. If the time taken to visit the next element is less than any of the predecessors then we have a cycle.
Bellman-Ford algorithm can work with negative-weight edges in the input graph. If there are no cycles, the algorithm takes gives the shortest paths and their weights. It relaxes each edge of the graph once and then determines cycle.
Bellman-Ford(G, w, s)
Initialize-single-source(G,s)
for i = 1 to number of vertices -1
    for each edge (u,v) belongs to edges E in G
          relax(u,v,w)
for each edge(u,v) belongs to edges E in G
     if (v.d  > u.d  + w(u,v))
         return False
return True

In a plane n points (X and Y) is given. How will you find out the maximum collinear points. Extend this algorithm for points (X, Y and Z) in 3D plane.
int Get MaxCollinear(List<Point> p)
{
var collinear = new List<Tuple<int,int,int>>();
for (int i =0; i < p.Count; i++)
   for (int j =0; j < p.Count; j++)
     for (int k =0; k<p.Count;k++)
    {
            if (p[i] ==p[j] || p[j] == p[k] || p[k] == p[i]) continue;
            if (collinear.contains(p[i],p[j],p[k])) continue;
            if (isCollinear(p[i],p[j],p[k]))  collinear.Add(p[i],p[j],p[k]);
     }
var ret = Merge(collinear);
return ret.count();
}

bool isCollinear(Point p, Point q, Point r)
{
if (q.x >= min(p.x,r.x) && q.x<= max(p.x,r.x)
    && q.y >= min(p.y,r.y) && q.y <= max(p.y,r.y)))
   return True;
return False;
}
List<Point> Merge(List<Tuple<int,int,int>> collinear)
{
// two points are common between entries
var max = new List<Point>()
{
for (int i =0 i < collinear.count; i++){
   var ret = new List<Point>();
   for (int j =0; j <collinear.count; j++)
    {
          if ( i != j  && collinear[i].Intersects(collinear[j]).Count > 2){
                       ret.add(collinear[i].items);
                       ret.add(collinear[j].items);
          }
    }
    if (ret.Count > max.Count)
          ret.CopyTo(ref max);
}
return max;
}

#coding exercise
Write box stacking algorithm
int GetStackedBoxesCount(List<Tuple<int,int,int>> boxes)
{
int n = boxes.Length;
int best = new List<int>(n);
for (int i =1; i < n; i++)
for (int j = 0; j < i j++)
{
    if (box[i].first * box[i].second < box[j].first * box[j].second && best[j] + 1 > best[i])
          best[i] = best[j] + 1;
}
return best.max();
}

Minimum number of steps between start and end positions for a knight on a chessboard
void GetMinMoves(Point start, Point end, int count, ref int min)
{
 if ( start == end) { if (count < min), {min = count;} }
 var x = new List<int>() { 2, 1, -1, -2, -2, -1,  1,  2};
 var y = new List<int>() { 1, 2,  2,  1, -1, -2, -2, -1};
for (int k =0 ; k < 8; k ++)
{
   start.x += x[k];
   start.y += y[k];
   if (isValid(start))
       GetMinMoves(start, end, count + 1, ref min);
   start.x -= x[k];
   start.y -= y[k];
}
}

int GetWordSnake( char[,] board, Point start, int count, string candidate, Dictionary<string, string> d)
{
  for (int i =0; i< 4; i++)
  {
        start = update(start, i);
        candidate.Add(board[start.x, start.y]);
        id (d.contains(candidate)) print(candidate);
        if (d.containsprefix(candidate) && count < board.rows * board.cols)
               GetWordSnake(board, start, count+1, candidate, d);
        start = revert(start, i)
  }
}

Perform Topological Sort
Topological DFS(int[,] G, List<int> color, List<int> parent, ref List<int> result)
for (int i =0; i < G.rows; i++)
{
    color[i] = white;
    parent[i] = -1;
}
time = 0;
for (int j =0 ; j < G.rows; j++)
{
      if (color[j] == white)
         DFS-Visit(G, j, ref color, ref parent, ref time, def result)
}
}

DFS-Visit(int[,] G, int u, ref List<int> color, ref List<int> parent, ref int time,ref List<int> result)
{
time = time + 1;
//u.start = time;
color[i] = gray;
for (int i = 0; i < G.cols; i++)
   var v =  G[u, i];
       if v > 0 &&color[v] == white
           parent[v] = u;
           DFS-Visit(G, v, color, parent, time, result)
color[u] = black;
time = time + 1;
result.InsertAt(0, u);
//u.f = time
}

Storing backups of Virtual machines

This example is for a VMWare vCenter which allows virtual machines to be backed up and recovered.  Generally some space is reserved on the VMWare vCenter for storing backups of VMs provisioned on the vCenter. Typically about 20% of the storage on the vCenter is earmarked for this purpose.  A backup is typically a portable tar file comprising of vmdk and other relevant files.

The benefit of using the storage is that the vCenter keeps track of these files that can be queried and used from different clients through command line, API or web interface.  

However, clients can also choose to download these files to their repository of choice and manage it themselves. This is especially helpful if the archives have to be used outside of the vCenter they originated from.

An example of download is given from pyvmomi library

   def download_file(url, local_filename, cookie, headers):

        r = requests.get(url, stream=True, headers=headers,cookies=cookie,verify=False)

        with open(local_filename, 'wb') as f:

            for chunk in r.iter_content(chunk_size=1024*1024*64):

                if chunk:

                    f.write(chunk)

                    f.flush()

        return local_filename

Now vmdks  can be exported with

    def export_vmdks(vm, prefix_clone, esxhost, server_name):

        import pyVmomi

        HttpNfcLease = vm.ExportVm()

        try:

            infos = HttpNfcLease.info

            device_urls = infos.deviceUrl

            vmdks = []        

            for device_url in device_urls:

                deviceId = device_url.key

                deviceUrlStr = device_url.url

                diskFileName =  vm.name.replace(prefix_clone,'') + "-" + device_url.targetId

                diskUrlStr = deviceUrlStr.replace("*", esxhost)

                diskLocalPath = './' + diskFileName

                cookie = make_compatible_cookie(si._stub.cookie)

                headers = {'Content-Type': 'application/octet-stream'}

                logger.debug("[%s] exporting disk: %s" %(server_name,diskFileName))

                

                download_file(diskUrlStr, diskFileName, cookie, headers)

                vmdks.append({"filename":diskFileName,"id":deviceId})

        finally:

            HttpNfcLease.Complete()

        return vmdks

#codingexercise

convert a binary tree into doubly linked list
Node BT2DLLHelper(Node root)
{
if (root==null) return root;
if (root.left != null)
{
Node left = BT2DLLHelper(root.left);
for (; left.right != null; left = left.right);
left.right = root;
root.left = left;
}
if (root.right != null)
{
Node right = BT2DLLHelper(root.right);
for (; right.left != null; right = right.left);
right.left = root;
root.right = right;
}
return root;
}
Node BT2DLL(Node root)
{
if (root == null) return root;
root = BT2DLLHelper (root);
for( ; root.left != null; root = root.left);
return root;
}

Taking backup of virtual machines in VCenter
If you have wanted to automate taking a backup in vCenter, then here is a succinct summary of the steps:

                            vm_is_off = vm.summary.runtime.powerState == "poweredOff"

                            if str2bool(self.halt_vm):

                                vm.ShutdownGuest()

                                vm_is_off = True

                            if  vm_is_off:

                                vmdks = self.export_vmdks(vm)

                                ovf_filename = self.create_ovf(vm, vmdks)

                            else:

                                new_vm = self.clone_vm(vm)

                                vmdks = self.export_vmdks(new_vm)

                                ovf_filename = self.create_ovf(vm, vmdks)

                                self.wait_task(new_vm.Destroy_Task())

                            if str2bool(self.create_ovafile):

                                ova_filename = self.create_ova(vm, vmdks, ovf_filename)

                            if str2bool(self.halt_vm):

                                vm.PowerOnVM()

Essentially, we need all the data flushed to disk as vmdk. This happens when the vm is in the powered off state. If the vm is on, we clone it so as to minimize the disruption to the existing and then export the vmdks.  Additionally we create OVF descriptor and package. OVF is a an open standard developed by Distributed Management Task Force to meet the need of the industry to create a portable format for virtual machines that is vendor and platform independent. An OVF package consists of an OVF descriptor, a set of virtual disks, a set of localization bundles, a manifest and a certificate. The .ovf file is the main document of an OVF package. It contains all the metadata for the OVF package.
Often it is incovenient to transfer multiple files as in the package above. Instead a tarball is made for portability. This is called an OVA (Open Virtualization Format Archive). However, it is not merely a tarball since the order of the files and their naming is controlled.
Courtesy: TISbackup
#codingexercise
Find a number in a rotated sorted array
int GetNumber(List<int> sortedRotated, int num)
{
int n = sortedRotated.Count;
int pivot = find_pivot(sortedRotated, 0, n-1, num); // binary search
if (pivot == -1)
      return binary_search(sortedRotated, 0, n-1);
if (sortedRotated[pivot] == num)
      return pivot;
if (sortedRotated[pivot] <= num)
     return GetNumber(sortedRotated, 0, pivot-1, num);
else
     return GetNumber(sortedRotated, pivot+1, n, num);
}
int find_pivot( List<int> sortedRotated, int start, int end)
{
 if (start < end)
     return -1;
 if (start == end) return start;
int mid = (start + end ) / 2;
if ( mid < end && sortedRotated[mid] > sortedRotated[mid+1]) return mid;
if (mid > start && sortedRotated[mid-1] > sortedRotated[mid]) return mid-1;
if (sortedRotated[low] >= sortedRotated[mid])
    return find_pivot(sortedRotated, start, mid-1);
return  find_pivot(sortedRotated, mid+1, end);
}

#coding exercise
Int isRotated (string a1, string a2)
{
 return a1.length == a2.length && (a1+a1).indexof (a2) != -1;
}
}

Taking Backup of VM instances on AWS

If you are familiar with saving the states of your VM instances, you will know that you can take snapshots.  From VMWare documentation:

“On vSphere, backups are usually done by taking a snapshot, to efficiency obtain a static image of the virtual machine. Snapshots are a view of a virtual machine at a certain point in time, and enable quick and clean backup operation. Snapshots also provide an incremental backup mechanism called changed block tracking. ”

Well the equivalent for AWS is taking AMI which stands for Amazon Machine Image. With AMI, you can launch instances and specify as many instances as you need.  It specifies  a template for the root volume for the instance, launch permissions that control which AWS Accounts can use the AMI to launch instances and a block device mapping that specifies the volumes to attach to the instance. If the AMI is EBS backed, it is automatically registered. We can also take snapshots of an EBS volume that the VM is using. EBS volume snapshots also help to launch instances. We can do both for making sure no information is lost on recovery.

Here’s the sample code to do it:

        import boto3

        ec2 = boto3.resource('ec2', region_name=region, aws_access_key_id=accesskey,

                          aws_secret_access_key=accesssecret)

        instances = ec2.instances.filter(

        Filters=[{'Name': 'tag:Name', 'Values': [name]}])

        for instance in instances:

            print('instance_id='+instance.id)

            import random

            response = instance.create_image(Name=name+"Backup"+str(random.randint(1,99999)), InstanceId=instance.id, Description='Full Backup', NoReboot=False, DryRun=False)

            print(response.id)

The image created by the steps above is EBS-backed. If the instance was customized with instance store volumes or EBS volumes in addition to the root device volumes, the new AMI contains the block device mapping information for those volumes. Because the volumes are independent and their mapping only uses their reference, when the instance is launched from this AMI, all those additional volumes are also available.

Instance.volumes.all() gives the iterator for all volumes attached the instance.

An AMI can also be created from a snapshot of the root device volume. However, some AWS OS flavors have billingProduct code associated with an AMI to verify subscription status for package updates and this is not maintained when creating an AMI from an EBS Snapshot. Therefore instances cannot be launched successfully from such AMI.

Alternatively, if the root device volume is snapshot, then instances can be launched from the EBS Snapshot.

#codingexercise
Get the intersection point of two linked lists
Find the count of one linked list as c1
Find the count of another linked list as c2
Traverse the longer list by abs(c1-c2) nodes
Then traverse them together one node each until a match.

Find all connected components in a graph
int getCount(int[,] adj)
{
int count = 0
for (int i =0; i < row; i++)
   for(int j =0; j < col; j++)
    if (adj[i,j] && !visited[i,j]){
          DFS(adj, i, j, visited);
          ++count;
    }
}
#coding exercise
Add two numbers where the digits are represented by nodes in a linked list 
Find the  lengths of both the linked list.
If they are of equal size recursively go down both lists until the last and then add and carry forward to stack unwind
If they are different lengths, then walk down the longer until the size are same.