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.

#codingexercise
Fix two swapped nodes of BST
//Inorder traversal will have two nodes out of place
void correctBSTUtil(node root, ref node first, ref node middle, ref node last, ref node prev)
// the target nodes may be adjacent then they will be found by first and middle
// otherwise they will be found by first and last
{
if (root)
{
correctBSTUtil(root.left, first, middle, last, prev);
if ( prev && root.data < prev.data)
{
if (!first)
{
first  = prev;
middle = root;
}
else
 last = root;
}
prev = root;
}
correctBSTUtil(root.right, first, middle, last, prev);
}

void correctBST(node root)
{
node first, middle, last, prev;
first=middle=last=prev=null;
correctBSTUtil(root, first, middle, last, prev);
if (first && last)
{
swap(first.data, last.data);
}
else if (first && middle)
{
swap(first.data, middle.data);
}

}

Snapshots and AMI from AWS

We were discussing backup and snapshots. AWS handles this differently. It takes snapshots of volumes and images (Amazon machine image) from instances. Both are required for a full restore although an instance can be launched from either. This is because the root drive of the instance is a volume which can be snapshot from EBS. The machine should ideally be powered off for a consistent backup otherwise it could be restarted to let other programs flush to disk.  As long as the disk captures the active state, we are good to backup because then we don't lose any transient data.

AWS comes with 'boto' sdk that facilitates some of these operations in the following way:

connection = boto.ec2.connect_to_region(region, aws_access_key_id=accesskey, aws_secret_access_key=accesssecret)

connection.get_all_instances()

// find instance

instance.create_image(hostname+"Backup", description=None, no_reboot=False, dry_run=False)

#codingexercise

Given three points a, b and c, write a function to find what type of triangle they construct or whether a triangle can be made at all.

First we rule out triangle if the points are collinear

bool collinear(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;

}

Virtual Machine snapshots on different cloud platforms. 

Cloud providers such as OpenStack, VMWare provide their own snapshot services. The snapshot of a Virtual machine is a file itself. Therefore backup of this file is equivalent to taking snapshot of the Virtual Machine. Since Cloud providers are used to create virtual machine instances, they are also the appropriate controllers to take snapshots of the created instances. 

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. ” 

Let us take a look at how to create the instances for different platforms: 

1. OpenStack: 

This provides snapshot APIs from the Images library: 

GET /v2/images 

GET /v2/images/{image_id} 

And  

POST /v2/images 

Upload and download of raw image data can be done with:  

PUT /v2/Images/{image_id}/file 

GET /v2/Images/{image_id}/file 

  

2. VMware: 

This provides workflows that can be used to create snapshot using the VCO client. 

Most of them have a generic signature as follows: 

/workflows/{workflow-id} 

/workflows/{workflow-id}/executions to check the status of the execution 

In addition, VDDK also provides abilities with a different set of API calls.  

On one vCenter Server, the moRef uniquely identifies a virtual machine. If we need to track and inventory virtual machine backups across multiple vCenter Servers, we can use moRef together with instanceUuid. We can see the instanceUuid at the following browser path:  

    https://<vcserver>/mob/?moid=ServiceInstance&doPath=content.about  

The following code sample shows how to create a snapshot on a specific virtual machine:  

    // At this point we assume the virtual machine is identified as ManagedObjectReference vmMoRef.     String SnapshotName = "Backup";     String SnapshotDescription = "Temporary Snapshot for Backup";     boolean memory_files = false;  

boolean quiesce_filesystem = true; ManagedObjectReference taskRef = serviceConnection.getservice().CreateSnapshot_Task(vmMoRef,  

SnapshotName, SnapshotDescription, memory_files, quiesce_filesystem); 

The following Java code demonstrates how to delete the snapshot:  

ManagedObjectReference removeSnapshotTask; ManagedObjectReference snapshot; // Already initialized. removeSnapshotTask = serviceConnection.getservice().removeSnapshot_Task(snapshot, Boolean FALSE);  

3. AWS provides a variety of ways to interact with the VMs. While the options 1) and 2) are for the private cloud, this one is for the public cloud and hence comes with rich documentation on steps to create a snapshot. For example, we can do this with a tool, SDK or API. 

Here is an example: 

https://ec2.amazonaws.com/?Action=CreateSnapshot 

&VolumeId=vol-1234567890abcdef0 

&Description=Daily+Backup 

&AUTHPARAMS 

Conclusion: Different cloud providers provide the ability to take snapshots and are tied directly with their abilities to create instances. We leverage these to allow instances to be snapshot in a platform agnostic manner. 

#coding exercise

Level order traversal of a tree in spiral form

Same a level order except that alternate levels are put in a stack and printed.
Void printSpiral (node root)
{

Bool drc = false;
For (int I = 1; I < height (root) I ++){
PrintGivenLevel (root, i, drc);
Drc ~= drc
}
}
void printGivenLevel(Node root, int level, bool direction)
{
   if (root == null) return;
    if (level ==1) print(root.data);
    else if level > 1{
       if (direction){
            printGivenLevel(root.left, level - 1, direction);
            printGivenLevel(root.right, level -1, direction);
       }else{
            printGivenLevel(root.right, level-1, direction);

            printGivenLevel(root.left, level -1, direction);
       }
    }
}