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