Vector clock

#include<stdio.h>
#include<conio.h>
struct node{
int x;int y;int z;
}p1[5],p2[5],p3[5];



int main()
{int i,p,a[5],b[5],c[5],d[5];
printf("enter number of events");

scanf("%d",&p);
for(i=0;i<p;i++)
{
printf(" %d event is from e ",i+1);
scanf("%d %d",&a[0],&b[0]);
printf(" to e");
scanf("%d %d",&c[0],&d[0]);

}
for(i=0;i<5;i++)
{
p1[i].x=i+1;
p2[i].y=i+1;
p3[i].z=i+1;
}
for(i=0;i<5;i++)
{
if(c[i]==2)
{if(a[i]==1)
{
p2[d[i]].x=p1[b[i]].x;
p2[d[i]].y=p1[b[i]].y>p2[d[i]].y?p1[b[i]].y:p2[d[i]].y;
}
if(a[i]==3)
{p2[d[i]].z=p3[b[i]].z;
p2[d[i]].y=p3[b[i]].y>p2[d[i]].y?p3[b[i]].y:p2[d[i]].y;

}
}
if(c[i]==1)
{
if(a[i]==2)
{
p1[d[i]].y=p2[b[i]].y;
p1[d[i]].x=p2[b[i]].x>p1[d[i]].x?p2[b[i]].x:p1[d[i]].x;
}
if(a[i]==3)
{
p1[d[i]].z=p3[b[i]].z;
p1[d[i]].x=p3[b[i]].x>p1[d[i]].x?p3[b[i]].x:p1[d[i]].x;
}
}
if(c[i]==3)
{
if(a[i]==2)
{
p3[d[i]].y=p2[b[i]].y;
p3[d[i]].z=p2[b[i]].z>p3[d[i]].z?p2[b[i]].z:p3[d[i]].z;
}
if(a[i]==1)
{p3[d[i]].x=p1[b[i]].x;
p3[d[i]].z=p1[b[i]].z>p3[d[i]].z?p1[b[i]].z:p3[d[i]].z;
}
}
}

for(i=0;i<5;i++)
{
printf("%d ",p1[i].x);
printf("%d ",p1[i].y);
printf("%d ",p1[i].z);
printf("\n");
printf("%d ",p2[i].x);
printf("%d ",p2[i].y);
printf("%d ",p2[i].z);
printf("\n");
printf("%d ",p3[i].x);
printf("%d ",p3[i].y);
printf("%d ",p3[i].z);
printf("\n");
}


}

Binary Search Tree

Write a Program to implement Binary Search tree as discussed in the Lecture.

The following methods are to be implemented in the Binary Search Tree.

1) insert(key), function which inserts a new element into the tree.

2) remove(key), function which removes the key from the Binary Search Tree

    follow these conditions to while removing the element.

          i) if the tree-node having key is a leaf node, delete that node.

ii) replace the desired tree node with its child, if that node has only one child.

iii) If the tree node having key, has two non-empty children then use its inorder - predecessor to replace the node. Inorder - predecessor for a tree node is the right most node in its left subtree.

You need to build a binary search tree by inserting elements in the given order.

Then perform insert and remove operations on that tree based on the operation specified as a character (i - insert, d - remove).

Input:

• 1st line has number of elements to be added to the Binary Search Tree (Initial number  elements - N)
• 2nd line of the input contains the elements each separated by single whitespace.
• 3rd line has number of operations to be performed (k)
• 4th line has operation, key separated by  a white space (i - insert, d - remove)

Sample Input:

4

8 7 15 2

2

i 10 d 2

Output:

The program should output the post order traversal of BST after all the given operations are performed. Separate the elements with a single whitespace. Print “NULL”(without quotes), if the tree is empty.

Output for the above Sample Input:

7 10 15 8

Constraints:

Elements in the binary Search Tree are unique.

0<=N≤ 20

0<=key<=10000 (Elements in Tree)

0<=k<=10

Solution -:
After deadline is over

Nearest Larger Number in Stack

Nearest larger number (NLN) of  element of stack is defined as the closest greater number that are pushed before the element, if there are no such element then NLN will be -1. Given a stack of unique positive integer, return another stack with NLN of each element in the same order of original stack.

Consider example of stack, where 4 is top-most and 3 bottom-most.

3 7 5 6 8 4

Then NLN of each element is given by

-1 -1 7 7 -1 8

Explanation:

• Number greater than 4 which is closest and below stack is 8,
• Similarly the number greater 7 is greater than 6 and closest to 6
• Since there is no element greater than 8 below the stack NLN is -1

and so on ..

You have complete returnStackWithNearestGreater(Stack inputStack) that return the NLN Stack.

Input

N

a1 a2 a3 a4 .. aN

where N is number of elements in the stack, ai are elements of the stack where aN is top-most element of the stack

Ouput:

b1 b2 b3 b4 .. bN

where b1  is NLN for a1, b2 is NLN for a2 and so on….

Solution -:
After deadline is over

Value Balanced Tree

One of the most important question mostly asked in placement .

A tree is called value balanced tree if for all nodes, sum of values (assume the values are integers) of nodes in left hand side is equal to sum of values in right hand side.

Given a complete binary tree find if it is a value balanced tree or not.

You have to complete isValueBalanced(int [], int) function. You can create other functions but should be called from given function.

Input Constraints:

The input tree would be always a complete binary tree.

Input:

Number of Nodes in first line and values of nodes in level order (as represented as array) in next.

Output:

Either “Tree is value balanced” or “Tree is not value balanced”.

Solution -:
After deadline is over

String Class

Implement a custom string class with public functions

1) combine which takes as argument two strings s1, s2 and appends s2 to s1.  
2) replace which takes as argument two characters, and replaces all occurrences of the first character by the second character in the string, if the first character is found, otherwise replace returns NOT FOUND.  

In the main program take two strings as input (on first line), then take two characters as input.  Concatenate the two strings using combine.   Replace the first character in the concatenated string (if found) with the second character. 

Implement following public functions for the  String Class.

1. String String::operator+ (String str) : Create an new String object and copy the base String and then append content of String str. 
2. void String::replace (char oldChar, char newChar) : Replace the "oldChar" if found with "newChar"
3. char * String::getCharArray(): Return a Character array with content of String.
4. bool String::find (char c): Return true if the character is present in the string else false.

Input:

The first two line contains two strings, string1 and string2. The second line contains two characters char1 and char2.  

The two strings will contain only letters in English alphabet (both upper and lower case). The two characters will also be English letters.

Output:

First concatenate the two strings. In the result, all occurrences of char1 should be replaced with char2 and that should be printed out.If char1 is not present in the resultant string after concatenation, print NOT FOUND
Solution -: