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 -:

Matrix ADT

You have to implement a matrix ADT using concepts of C++ classes taught in the lectures. The input matrices would be square matrices. The  class must support the following functions:

1. Matrix Addition

2. Matrix Subtraction

3. Matrix Multiplication

The program should take as input: dimension of a square matrix N, two matrices of size N x N with integer values, and one operator symbol (+, - ,*). It must perform the corresponding operation using member functions of Matrix class. You are supposed to implement the following functions of the class MatrixADT matrixType add(matrixType M1, matrixType M2): The function should add matrices M1 and M2 and store the result in "resultMatrix". The function should return the "resultMatrix".

matrixType subtract(matrixType M1, matrixType M2):

The function should subtract matrix M2 from M1 and store the result in "resultMatrix". The function should return the "resultMatrix".

matrixType multiply(matrixType M1, matrixType M2):

The function should multiply matrices M1 and M2 and store the result in "resultMatrix". Be careful, it is M1*M2 and not M2*M1. The function should return the "resultMatrix".

INPUT:

In the first line, one integer which is the dimension of the matrix  and one operator (one of +, - or *)

Two NxN matrices one after the other, supplied one row at a time.

OUTPUT:

Resultant matrix after performing the specified operation, one row at a time. For subtraction, if A is the first matrix and B is the second matrix, perform A-B.

CONSTRAINTS:

The inputs will satisfy the following constraints:

1<=N<=10

There is no need to validate the value of N.

There are no constraints on the values of the entries of the matrices.

Solution-:

Number in a position

You are given a sequence of integers. The length of the sequence is unknown but the sequence ends with a -1. You are given another number pos . Your task is to output the integer in position pos. If pos > length of the sequence output -1.

You are supposed to implement two functions :
Node loadNum(): Function to load the numbers onto the linked list      Return a pointer to the head of the list
void releaseMem(Node head): Function to release the memory after every iteration



Note: pos is indexed from 1.

Input
T
a11 a12 .. -1
Pos 1
…
…
aT1  aT2 … -1
Pos T

Output
N1
N2
..
..
NT

Constraints
1 <= T <= 30
1 <= aij <= 100
There is no restriction on the length of each list.

Example
Input
1
4 3 2 1 -1
2

Output
3

Explanation
3 is the number in the second position.

Solution -:

Topper and Average

Given a list of student names and their  marks in K subjects,  find the average mark for every student. Also, print a list of toppers in each subject. (Assume there is only one  topper).

Use the given structure Student (in C language). You should the  implement following functions which are called in main():
 char * getTopper(struct Student s[], int nStudents, int subjectIndex, int nSubjects);
/*
Return name of topper of a subject.
Arguments :
array of Student records.
number of Students (nStudents).
index of subject for which function should find toper (subjectIndex).
number of Subjects (nSubjects)
 */
float getAvg(struct Student  s, int nSubjects);
/*
return avg mark of a student.
Arguments :
a Student record s.
number of Subjects (nSubjects)
*/
void setValues(struct Student* s, const char * name, float marks[], int nSubjects);
/*
set values in structure Student
Arguments :
a pointer to a Student record (s).
name of Student (name).
mark of K subjects (marks).
number of Subjects (nSubjects)
*/

Input:
Given a list of student names and their marks in K subjects, find the average mark for every student. Also, print a list of toppers in each subject. (Assume there is only one topper).

The first line contains the number of students (N) and the number of subjects (K). Following N lines contains name of student and the marks of K subjects.

Output
The first N lines of output should contain average marks of each student (Print 6 decimal places) . Following K lines should contain the name of the topper of each subject in the order in which the subjects are given.

Constraints
1 <= N <=100
1 <= K <=10
Assume that Name does not contain spaces and the maximum length of names of the students is 10 (excluding the NULL character at the end).
0 <= Mark <=100 and the marks are real numbers.

Solution-:

Triplet Search

Given an array of unique numbers and a value, a valid triplet is a set of three numbers (not necessarily continuous in the array) that add up to the value. Write a program to count all valid triplets. Print the number of  valid triplets. Hint: Can you solve this in O(n^2) steps?

Input : First line contains N and Sum (Space separated). Second line contains space separated list of N numbers.

Output: Number of triplets such that  sum possible

Constraints:

• 0 < N < 100
• All numbers in the list are unique and between -10^4 to 10^4
• -10^3 < Sum < 10^3

Solution -:

Evaluating polynomials

You are given a polynomial of degree n. The polynomial is of the form P(x) = anxn + an-1xn-1 + … + a0. For given values k and m, You are required to find P(k) at the end of the mth iteration of Horner’s rule. The steps involved in the Horner’s rule are given below,

Pn (x) = an

Pn-1 (x) = an-1 + x * Pn (x)                              1st iteration.

Pn-2 (x) = an-2 + x * Pn-1 (x)                           2nd iteration.

.

.

P0 (x) = a0 + x * P1 (x)                                  nth iteration.

In general, Pi (x) = ai + x * Pi + 1 (x) and P0(x) is the final result.

Input

n m k an an-1 …. a0

(Space separated)

Output: P(k) value at the end of the mth iteration.

Sample Input:

2 2 5

3 2 1

Sample Output:

86

Constraints:

1 <= n, k, m <= 10

0 <= ai <=10


Solution -:

Selection Sort

Selection sort is a sorting algorithm that sorts n elements in an array using n-1 calls of a procedure called Select() . Select(i) selects the smallest of the elements from positions i+1 to n and swaps with the element at i. Given a list of unsorted elements having N numbers, print the array of elements after K calls to Select() starting with Select(1) as the first call and Select(K) as the last call with increasing order of parameters to Select().

Input:

N K m1 m2 m3 .. mN (Space separated) (where mi's are elements of unsorted list)

Output:

Space separated list of N numbers after K calls to of Select().

Constraint:

2<= N <= 100

1<= K <= (N-1)

Numbers will be given in the range [-1000,1000].

Example 1:

5

1

9 8 7 6 5

Expected Output:

5 8 7 6 9

Closest Numbers

You are given a sorted list of N numbers and a number Num. Write a program to find the five numbers that are closest (numerically) to Num. A number x in the array is closest to Num if |Num-x| is the smallest among all such x possible.

Note: If the Num is present in given list, then it should be in the output.

Constraints:
        5 < N <20
        All numbers in list are between -10000 to 10000
        -10000 <Num< 10000
        There could be numbers that are repeated
Input:      
    N Num
    m1 m2 m3 .. mN
where mi's are N numbers in sorted order.

Output:
    p1 p2 p3 p4 p5
where pi's are closest numbers in increasing order of absolute difference from Num. If there are two numbers with same difference, print the larger one first.

Solution-

#include<stdio.h>

Solve the Mystery

Solve the mystery.

Input :
First line contains T - No. of test cases.
For each test case there are two lines. 
first line contains N. 
Second line contains N space separated integers A[1] to A[N].

Output :
Print answer of the mystery in separate lines.

Constraints : 
1<=T<=10 
1<= N <= 10^5 
0<= A[i] <= 10^5

Blocks world (Programming Assignment)

Write a program which does the following:

There are 3 tables in a room. Every table can hold any number of blocks stacked on each other with only one block touching the table. No two blocks are of the same size. At any point of time, the blocks must be placed in ALL tables in such a way that no smaller sized block will have a larger sized block on top of it. Initially all the blocks are placed on table number 1 in the correct fashion (biggest block at bottom and smallest block at the top). Our aim is to move all the blocks from table number 1 to table number 3 such that at every step all the constraints are satisfied and the final order in table 3 is: smallest block must be at the top and the largest at the bottom and all the other blocks in between in increasing size. Tables 2 and 1 should not have any blocks on them at the end of the process. You are allowed to move only one block at a time from any table to any other table.

Palindrome (Programming Assignment )

Write a program which takes a string as input and prints the longest prefix of the string whose reverse is a valid suffix of the string. For example, if "notation" is given as input, the prefix "no" is the longest prefix that has a matching valid suffix (namely "on") at the end.

If a string is a palindrome (i.e. if the string is the same as its reverse), then the prefix is the whole string itself. For example, if input is "civic", then the longest prefix is "civic" itself. If the string has no valid prefix, print 0. For example, if the input string is "bird", there is a mismatch at the first character itself and there is no valid prefix.

The symbols in the string will only be from the set {A-Z,a-z}. The symbols are case sensitive. i.e. ‘A’ and ‘a’ are considered to be different.

You are provided with a function called printChars ( ) that prints a character array from the starting position pointed to by p to the ending position pointed to by q. If p is NULL, it prints 0.

The prototype of the function is:

void printChars(char *p, char *q);

You do not have to write the program for printChars ( ) function. This function is automatically added at the end of the code segment that you write.

You can use string functions in the library if you desire to.

INPUT:
Input is a string of length N composed of symbols only from the set {A-Za,z}.

OUTPUT:
The longest prefix that has a corresponding matching suffix and 0 if such a prefix does not exist.

CONSTRAINTS:
The inputs will satisfy the following properties. It is not necessary to validate the inputs.

1<=N<=99

Evaluating a Polynomial (Programming Assignment )

You are given a polynomial of degree n. The polynomial is of the form P(x) = anxn + an-1xn-1 + … + a0, where the ai‘s are the coefficients.  Given an integer x, write a program that will evaluate P(x).

You are provided with a function named power( ) that takes two positive integers x & y and returns xy. If y is 0, the function returns 1.

The prototype of this function is

int power(int x, int y);

You do not have to write the program for power ( ) function. This function is automatically added at the end of the code segment that you write.

INPUT: Line 1 contains the integers n and x separated by whitespace.

Line 2 contains the coefficients an, an-1…, a0 separated by whitespace.

OUTPUT: A single integer which is P(x).

CONSTRAINTS: The inputs will satisfy the following properties. It is not necessary to validate the inputs.

1 <= n <= 10 1 <= x <= 10

0 <= ai <=10

Solution-: