1.
record Person(String name, int age, String Degree, int YOE, String skills, int weightage) {}
class PeopleQueue {
private Person[] queue;
private int front;
private int rear;
private int capacity;
private int size;
public PeopleQueue(int capacity) {
this.capacity = capacity;
this.queue = new Person[capacity];
this.front = 0;
this.rear = -1;
this.size = 0;
}
public void enqueue(Person person) {
if (rear == capacity - 1) {
System.out.println("Queue is full. Cannot enqueue ");
return;
}
rear++;
queue[rear] = person;
size++;
}
public Person dequeue() {
if (front == capacity) {
System.out.println("Queue is empty. Cannot dequeue.");
return null;
}
Person person = queue[front];
front++;
size--;
return person;
}
public Person peek() {
if (front == -1) {
System.out.println("Queue is empty. Cannot peek.");
return null;
}
return queue[front];
}
public int size() {
return size;
}
}
public class Main {
public static void main(String[] args) {
PeopleQueue queue = new PeopleQueue(5); //creating the queue of size 5
//creating 5 records for job seekers
Person p1=new Person("Alexa", 40, "BS", 20, "Research", 7);
Person p2=new Person("Siri", 45, "BA", 25, "Chef", 9);
Person p3=new Person("Ava", 55, "MA", 35, "RJ", 8);
Person p4=new Person("Cortana", 35, "BE", 15, "Architect", 9);
Person p5=new Person("Bixby", 30, "BCOM", 5, "Accountant", 6);
//the scenario here is there are 2 openings namely problem solving and relations
management, where Alexa, Cortana and Bixby applied for problem solving whereas Siri and
Ava applied for relations management. Here relations management's position is expected to
be filled before filling problem solving.
Person[] rm={p2,p3}; //people applying for relations management
Person[] ps={p1,p4,p5}; //people applying for problem solving
for (int i = 0; i < rm.length - 1; i++) { //sorting the rm candidates in descending order of
skills weightage
for (int j = 0; j < rm.length - i - 1 ; j++) {
if (rm[j].weightage() < rm[j + 1].weightage()) {
Person temp = rm[j];
rm[j] = rm[j + 1];
rm[j + 1] = temp;
}
}
}//end of external for
queue.enqueue(rm[0]); //highest weightage in skills relevant to job is first in queue
queue.enqueue(rm[1]); //rest in the queue in descending order of skill weightage
System.out.println("Number of candidates for relations management position: " +
queue.size());
System.out.println("\nPeek at top candidate: " + queue.peek());
System.out.println("\nThe person hired for relations management is "+
queue.dequeue().name());
System.out.println(queue.dequeue().name()+" better luck next time");
for (int i = 0; i < ps.length - 1; i++) { //sorting the ps candidates in descending order of
skills weightage
for (int j = 0; j < ps.length - i - 1 ; j++) {
if (ps[j].weightage() < ps[j + 1].weightage()) {
Person temp = ps[j];
ps[j] = ps[j + 1];
ps[j + 1] = temp;
}
}
}//end of external for
queue.enqueue(ps[0]); //highest weightage in skills relevant to job is first in queue
queue.enqueue(ps[1]); //rest in the queue in descending order of skill weightage
queue.enqueue(ps[2]);
System.out.println("Number of candidates for problem solving position: " +
queue.size());
System.out.println("\nPeek at top candidate: " + queue.peek());
System.out.println("\nThe person hired for problem solving is "+
queue.dequeue().name());
System.out.println(queue.dequeue().name()+" and "+queue.dequeue().name()+" better
luck next time");
} // end of main
}//end of class main
2.
record MedicalData(String name, int age, double weight, int sysBP, int HR, int SL, int
medYears, String medicines) {} //record data classes to handle heterogenous data
class Node { // fundamental element of the linked list implementation
MedicalData data; // record type data to handle heterogenous data at once
Node next;
Node(MedicalData data) { //constructor to initialize data while creating new node
this.data = data;
this.next = null;
}
}
class Stack { // stack class using linked list node
private Node top;
private int size;
public Stack() {
this.top = null;
this.size = 0;
}
public void push(MedicalData data) {
Node newNode = new Node(data);
// Check if memory allocation for the new node
// failed
if (newNode == null) {
System.out.println("\nStack Overflow");
return; // returns the method call or exit from here
}
newNode.next = top;
top = newNode;
size++;
}
public MedicalData pop() {
if (isEmpty()) {
System.out.println("\nStack Underflow");
return null; //returns null by exiting from here
}
MedicalData data = top.data;
top = top.next;
size--;
return data;
}
public MedicalData peek() {
if (isEmpty()) {
System.out.println("\nStack Underflow");
return null; //returns null by exiting from here
}
return top.data;
}
public boolean isEmpty() {
return top == null; //returns true or false after verifying empty condition
}
public int size() {
return size;
}
}//end of stack class
public class Main {
public static void main(String[] args) {
Stack stack = new Stack();
MedicalData p1=new MedicalData("Alexa", 40, 65.5, 120 ,75, 90, 4, "XYZ");
MedicalData p2=new MedicalData("Siri", 35, 65.6, 121 ,76, 91, 5, "XYZ");
MedicalData p3=new MedicalData("Ava", 50, 65.7, 122, 77, 92, 6, "XYZ");
MedicalData p4=new MedicalData("Cortana", 25, 65.8, 123, 78, 93, 7, "XYZ");
MedicalData p5=new MedicalData("Bixby", 30, 65.9, 124, 79, 94, 8, "XYZ");
//push 5 people medical records to the stack
stack.push(p1);
stack.push(p2);
stack.push(p3);
stack.push(p4);
stack.push(p5);
System.out.println("Stack size: " + stack.size());
System.out.println("Top element: " + stack.peek());
System.out.println("Popped element: " + stack.pop());
System.out.println("Popped element: " + stack.pop());
System.out.println("Popped element: " + stack.pop());
System.out.println("Popped element: " + stack.pop());
System.out.println("Popped element: " + stack.pop());
System.out.println("Stack size after pop: " + stack.size());
MedicalData[] people={p1,p2,p3,p4,p5};
//finding minimum by weight
double w=p1.weight();
MedicalData minW=p1;
for(int i=1; i<5; i++){
if (people[i].weight()<w){
w=people[i].weight();
minW=people[i];
}
}
System.out.println("The minimum weight is "+w+" and belongs to "+minW.name());
//finding maximum by BP
int bp=p1.sysBP();
MedicalData maxBP=p1;
for(int i=1; i<5; i++){
if (people[i].sysBP()>bp){
bp=people[i].sysBP();
maxBP=people[i];
}
}
System.out.println("The maximum BP is "+bp+" and belongs to "+maxBP.name());
//push records in ascending order of the age such that old is at top
for (int i = 0; i < 4; i++) { //sorting the people array by age
for (int j = 0; j < 4 - i ; j++) {
if (people[j].age() > people[j + 1].age()) {
MedicalData temp = people[j];
people[j] = people[j + 1];
people[j + 1] = temp;
}
}
}
for(int i=0;i<5;i++){ //pushing sorted array to stack
stack.push(people[i]);
}
System.out.println("oldest person at top is "+stack.peek());
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.pop());
System.out.println(stack.pop());
}//end of main
}//end of class Main
3.
Lets consider the names VENUS, EARTH, MARS and JUPITER as input to construct binary
search tree.
The input is placed character by character and alphabetically constructed into a BST where
left of the node contains alphabets prior to the node and right contains alphabets post to
the node alphabetically.
Here the input is all capital otherwise if mixed then must use ASCII values to decide the left
and right. And since small letters ASCII range from 97-122 while capital letters range is 65-90,
therefore all small letters goes right of the node containing the capital letter. Which in case
of names will be the first capital letter becoming the root node in BST.
1. VENUS
Insert V
Insert E
Insert N
Insert U
Insert S
Depth is the distance from the root node to the node or the number of edges travelled to
reach the node from the root node. And depth of the tree is the maximum depth of a node
in the tree which is always the leaf node of the tree. Here node S has a depth of 4 which is
the depth of the tree.
2. EARTH
Insert E
Insert A
Insert R
Insert T
Insert H
Depth of the tree is given by depth of node T = depth of node H which is equal to 2.
3. MARS
Insert M
Insert A
Insert R
Insert S
Depth of the tree is given by depth of node S, which is equal to 2.
4. JUPITER
Insert J
Insert U
Insert P
Insert I
Insert T
Insert E
Insert R
Depth of the tree is given by depth of node R, which is equal to 4.
Now the balance factor is determined by the difference of height of left and height of right,
where tree is said to be balanced if every node at each level have the balance factor in
between -1,0 or 1.
Height of a node is calculated by the distance from the node to the leaf node or the number
of edges travelled between node to leaf node.
Clearly EARTH and MARS have every node in the tree with height in between -1,0 or 1 and
are balanced. Unlike VENUS and JUPITER which has nodes E,V with height -3,4 and has
nodes J,U with height 2,3 respectively and are unbalanced.
4.
A.
#include <stdio.h> //input and output library
void main() {
int matrix[4][4];
int squaredPmatrix[4][4];
int cubedDmatrix[4][4];
int sumPDmatrix[4][4];
int i, j;
// User input for the original matrix
printf("Enter the elements of the 4x4 matrix in row wise or row by row manner:\n");
for (i = 0; i < 4; i++) {
for (j = 0; j < 4; j++) {
scanf("%d", &matrix[i][j]);
}
}
printf("The 4x4 input matrix entered is:\n");
for (i = 0; i < 4; i++) {
for (j = 0; j < 4; j++) {
printf("%d\t", matrix[i][j]);
}
printf("\n");
}
// The squares of the Peripheral (P) elements of original matrix
for (i = 0; i < 4; i++) {
for (j = 0; j < 4; j++) {
if (i == 0 || i == 3 || j == 0 || j == 3) {
squaredPmatrix[i][j] = matrix[i][j] * matrix[i][j];
}
}
}
printf("The matrix with squared peripheral elements is:\n";);
for (i = 0; i < 4; i++) {
for (j = 0; j < 4; j++) {
printf("%d\t", squaredPmatrix[i][j]);
}
printf("\n");
}
// The cubes of the Diagonal (D) elements of original matrix
for (i = 0; i < 4; i++) {
for (j = 0; j < 4; j++) {
if (i == j) {
cubedDmatrix[i][j] = matrix[i][j] * matrix[i][j] * matrix[i][j];
}
}
}
printf("The matrix with cubed diagonal elements is:\n";);
for (i = 0; i < 4; i++) {
for (j = 0; j < 4; j++) {
printf("%d\t", cubedDmatrix[i][j]);
}
printf("\n");
}
// Calculate the sum of squaredP and cubedD matrices
for (i = 0; i < 4; i++) {
for (j = 0; j < 4; j++) {
sumPDmatrix[i][j] = squaredPmatrix[i][j] + cubedDmatrix[i][j];
}
}
printf("Sum of squared peripheral matrix and cubed diagonal matrix is:\n");
for (i = 0; i < 4; i++) {
for (j = 0; j < 4; j++) {
printf("%d\t", sumPDmatrix[i][j]);
}
printf("\n");
}
}//end of main
B.
#include <stdio.h> //input and output library
void main() {
int matrix[4][4];
int i, j;
// Input the 4x4 matrix
printf("Enter the elements of the 4x4 matrix:\n");
for (i = 0; i < 4; i++) {
for (j = 0; j < 4; j++) {
scanf("%d", &matrix[i][j]);
}
}
printf("The 4x4 input matrix entered is:\n");
for (i = 0; i < 4; i++) {
for (j = 0; j < 4; j++) {
printf("%d\t", matrix[i][j]);
}
printf("\n");
}
// calculating sub-matrices by vertical folding (addition) i.e. fold along vertical axis
int vertical_folded_matrix[4][2];
for (i = 0; i < 4; i++) {
for (j = 0; j < 2; j++) {
vertical_folded_matrix[i][j] = matrix[i][j] + matrix[i][3 - j];
// Add corresponding elements after folding from middle vertical axis.
//The corresponding elements are elements in the same position once folded.
//Elements that superimpose after folding(vertical axis) are in same position.
//Therefore adding first and last column values, also 2nd and 3rd column values per row.
}
}
printf("The sub-matrix folded vertically is:\n");
for (i = 0; i < 4; i++) {
for (j = 0; j < 2; j++) {
printf("%d\t", vertical_folded_matrix[i][j]);
}
printf("\n");
}
// calculating sub-matrices by horizontal folding (multiplication) i.e. fold along horizontal
axis
int horizontal_folded_matrix[2][4];
for (i = 0; i < 2; i++) {
for (j = 0; j < 4; j++) {
horizontal_folded_matrix[i][j] = matrix[i][j] * matrix[3 - i][j];
// Multiply corresponding elements after folding from middle horizontal axis.
//The corresponding elements are elements in the same position once folded.
//Elements that superimpose after folding(horizontal axis) are in same position.
//Therefore adding first and last row values, also 2nd and third row values per column.
}
}
printf("The sub-matrix folded horizontally is:\n");
for (i = 0; i < 2; i++) {
for (j = 0; j < 4; j++) {
printf("%d\t", horizontal_folded_matrix[i][j]);
}
printf("\n");
}
}//end of main
5.
Given the numbers after appropriate padding are : 12345, 25378, 02543, 71356, 99929,
23151, 00131, 04217
Hash table size : the minimum prime number which is larger than the number of keys
entered (p) = 11
Custom hashing : Stores the number in x = calculated as sum1 i.e. (sum of squares of 2nd,
3rd, 4th digits) % p
If first collision happens calculate sum2 i.e. (sum of squares of 1st and 5th digits) % p and
then store the number y locations away from the intended location
If second collision happens store the number |x-y| locations away from the intended
location
If third collision happens store the number |2x-y| locations away from the intended location
and so on...
Calculating keys for the given set of 5 numbers:
• 12345 = (2^2+3^2+4^2) % 11 = 29 % 11 = 7
• 25378 = (5^2+3^2+7^2) % 11 = 83 % 11 = 6
• 02543 = (2^2+5^2+4^2) % 11 = 45 % 11 = 1
• 71356 = (1^2+3^2+5^2) % 11 = 35 % 11 = 2
• 99929 = (9^2+9^2+2^2) % 11 = 166 % 11 = 1
• 23151 = (3^2+1^2+5^2) % 11 = 35 % 11 = 2
• 00131 = (0^2+1^2+3^2) % 11 = 10 % 11 = 10
• 04217 = (4^2+2^2+1^2) % 11 = 21 % 11 = 10
Collisions:
(1) The fifth input 99929 have its first collision so will calculate the value of y = (9^2+9^2) %
11 = 162 % 11 = 8
Therefore new location is x+y = 1+8 = 9.
(2) Now the sixth input 23151 is having its first collision so will calculate the value of y =
(2^2+1^2) % 11 = 5 % 11 = 5
Therefore new location is x+y = 2+5 = 7
(3) Again the sixth input is having a second collision for the new key and therefore must
calculate |x-y| = |2-5| = 3
Therefore the new location is 3
(4) The final input is having its first collision so will calculate its y = (0^2+7^2) % 11 = 49 % 11
=5
Therefore the new location is 5 locations away from location 10 which if calculated backward
from location 10 gives us location 5.
Conclusion: There are 4 collisions for 3 inputs in total.
hash table of size p=11
Key Value
1 2543
2 71356
3 23151
5 4217
6 25378
7 12345
9 99929
10 131
Hashing using general modular function and linear probing:
Here the key is calculated as the number % p and if collision occurs then it will search for
first next empty position in a circular fashion.
Calculating keys for the given set of 5 numbers:
• 12345 = 12345 % 11 = 1
• 25378 = 25378 % 11 = 1
• 2543 = 2543 % 11 = 1
• 99929 = 99929 % 11 = 1
• 23151 = 23151 % 11 = 1
• 131 = 131 % 11 = 10
• 4217 = 4217 % 11 = 1
Collisions:
(1) The second input is having its first collision, therefore next empty position is 2
(2) The third input is having its first collision, therefore next empty position is 3
(3) The fourth input is having its first collision, therefore next empty position is 4
(4) The fifth input is having its first collision, therefore next empty position is 5
(5) The sixth input is having its first collision, therefore next empty position is 6
(6) The eighth input is having its first collision, therefore next empty position is 7|
Conclusion : There are 6 collisions for 6 inputs
hash table of size p=11 (general hashing)
Key Value
1 12345
2 25378
3 2543
4 71356
5 99929
6 23151
7 4217
10 131
Therefore clearly the metric to measure performance for this specific input is better with
custom hashing over hashing using general modular function and linear probing.
