abhijeets7663@gmail.com
help@ccatcracker.in

Section B Question



32. 

Find pair with given sum in array


Input .   Array = [ 8,7, 2, 5, 3, 1] sum = 10
Output.   Pair found at index (0,2)(8+2) or Pair found at index 1 and 4 (7+3)

                  

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

// A heap node
struct Node
{
// value stores the element,
// list_num stores list number of the element
// index stores column number of the list from which element was taken
int value, list_num, index;
};

// Comparison object to be used to order the heap
struct comp {
bool operator()(const Node lhs, const Node rhs) const
{
return lhs.value > rhs.value;
}
};

// Function to compute the minimum range that includes
// at-least one element from given M lists
pair<int, int> findMinimumRange(vector<int> list[], int M)
{
// high will be maximum element in the heap
int high = INT_MIN;

// stores minimum and maximum element found so
// far in heap
pair<int,int> p = { 0, INT_MAX };

// create an empty min-heap
priority_queue<Node, std::vector<Node>, comp> pq;

// push first element of each list into the min-heap
// along with list number and their index in the list
for (int i = 0; i < M; i++)
{
pq.push({list[i][0], i, 0});
high = max(high, list[i][0]);
}

// run till end of any list is not reached
for (;;)
{
// get root node information from the min-heap
int low = pq.top().value;
int i = pq.top().list_num;
int j = pq.top().index;

// remove root node
pq.pop();

// update low, high if new min is found
if (high - low < p.second - p.first) {
p = {low, high};
}

// return on reaching the end of any list
if (j == list[i].size() - 1) {
return p;
}

// take next element from "same" list and
// insert it into the min-heap
pq.push({list[i][j + 1], i, j + 1});

// update high if new element is greater
high = max(high, list[i][j + 1]);
}
}

// main function
int main()
{
vector<int> list[] =
{
{ 3, 6, 8, 10, 15 },
{ 1, 5, 12 },
{ 4, 8, 15, 16},
{ 2, 6 }
};

const size_t M = sizeof(list) / sizeof(list[0]);

pair<int, int> p = findMinimumRange(list, M);
cout << "Minimum range is " << p.first << "-" << p.second << "\n";

return 0;
}



31. 

Given m sorted list with n elements print them in sorted order .


Input .   M list : { 10, 20, 30, 40 }, { 15, 25, 35, 45 }, { 27, 29, 37, 48 }, { 32, 33, 39, 50 }, { 16, 18, 22, 28 }
Output.   Sorted : 10 15 16 18 20 22 25 27 28 29 30 32 33 35 37 39 40 45 48 50

                  

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// M arrays of size N each
#define N 4
#define M 5

// A min-heap node
struct Node
{
// val stores the element,
// i stores list number of the element,
// index stores column number of ith list from which element was taken
int val, i, index;
};

// Comparison object to be used to order the min-heap
struct comp
{
bool operator()(const Node &lhs, const Node &rhs) const
{
return lhs.val > rhs.val;
}
};

// Function to merge M sorted lists each of size N and
// print them in ascending order
void printSorted(int list[][N])
{
// create an empty min-heap
priority_queue<Node, std::vector<Node>, comp> pq;

// push first element of each list into the min-heap
// along with list number and their index in the list
for (int i = 0; i < M; i++)
pq.push({list[i][0], i, 0});

// run till min-heap is not empty
while (!pq.empty())
{
// extract minimum node from the min-heap
Node min = pq.top();
pq.pop();

// print the minimum element
cout << min.val << " ";

// take next element from "same" list and
// insert it into the min-heap
if (min.index + 1 < N)
{
min.index += 1;
min.val = list[min.i][min.index];
pq.push(min);
}
}
}

// main function
int main()
{
// M lists of size N each in the form of 2D-matrix
int list[M][N] =
{
{ 10, 20, 30, 40 },
{ 15, 25, 35, 45 },
{ 27, 29, 37, 48 },
{ 32, 33, 39, 50 },
{ 16, 18, 22, 28 }
};

printSorted(list);

return 0;
}



30. 

Find k smallest element in array using C++


Input .   Array : { 7, 4, 6, 3, 9, 1 }; K = 3
Output.   K small number : 4

                  

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// Function to find the K'th smallest element in the
// array using max-heap
int findKthSmallest(vector<int> const &v, int k)
{
// create an max-heap using std::priority_queue and
// insert first k elements of the array into the heap
priority_queue<int, vector<int>> pq(v.begin(), v.begin() + k);

// do for remaining array elements
for (int i = k; i < v.size(); i++)
{
// if current element is less than the root of the heap
if (v[i] < pq.top())
{
// replace root with the current element
pq.pop();
pq.push(v[i]);
}
}

// return the root of max-heap
return pq.top();
}

// Find K'th smallest element in an array
int main()
{
vector<int> vec = { 7, 4, 6, 3, 9, 1 };
const size_t k = 3;

cout << "K'th smallest element in the array is " <<
findKthSmallest(vec, k);

return 0;
}



29. 

Write a C++ program to reverse a linked list


Input .   List : 85 15 4 20
Output.   Reversed list 20 4 15 85

                  

// Iterative C++ program to reverse
// a linked list
#include <iostream>
using namespace std;

/* Link list node */
struct Node {
int data;
struct Node* next;
Node(int data)
{
this->data = data;
next = NULL;
}
};

struct LinkedList {
Node* head;
LinkedList()
{
head = NULL;
}

/* Function to reverse the linked list */
void reverse()
{
// Initialize current, previous and
// next pointers
Node* current = head;
Node *prev = NULL, *next = NULL;

while (current != NULL) {
// Store next
next = current->next;

// Reverse current node's pointer
current->next = prev;

// Move pointers one position ahead.
prev = current;
current = next;
}
head = prev;
}

/* Function to print linked list */
void print()
{
struct Node* temp = head;
while (temp != NULL) {
cout << temp->data << " ";
temp = temp->next;
}
}

void push(int data)
{
Node* temp = new Node(data);
temp->next = head;
head = temp;
}
};

/* Driver program to test above function*/
int main()
{
/* Start with the empty list */
LinkedList ll;
ll.push(20);
ll.push(4);
ll.push(15);
ll.push(85);

cout << "Given linked list\n";
ll.print();

ll.reverse();

cout << "\nReversed Linked list \n";
ll.print();
return 0;
}



28. 

write a CPP program to reverse a string using stack


Input .   Enter a string : abc
Output.   Result : cba

                  

// CPP program to reverse a string using stack
#include <bits/stdc++.h>
using namespace std;

// A structure to represent a stack
class Stack
{
public:
int top;
unsigned capacity;
char* array;
};

// function to create a stack of given
// capacity. It initializes size of stack as 0
Stack* createStack(unsigned capacity)
{
Stack* stack = new Stack();
stack->capacity = capacity;
stack->top = -1;
stack->array = new char[(stack->capacity * sizeof(char))];
return stack;
}

// Stack is full when top is equal to the last index
int isFull(Stack* stack)
{ return stack->top == stack->capacity - 1; }

// Stack is empty when top is equal to -1
int isEmpty(Stack* stack)
{ return stack->top == -1; }

// Function to add an item to stack.
// It increases top by 1
void push(Stack* stack, char item)
{
if (isFull(stack))
return;
stack->array[++stack->top] = item;
}

// Function to remove an item from stack.
// It decreases top by 1
char pop(Stack* stack)
{
if (isEmpty(stack))
return -1;
return stack->array[stack->top--];
}

// A stack based function to reverse a string
void reverse(char str[])
{
// Create a stack of capacity
//equal to length of string
int n = strlen(str);
Stack* stack = createStack(n);

// Push all characters of string to stack
int i;
for (i = 0; i < n; i++)
push(stack, str[i]);

// Pop all characters of string and
// put them back to str
for (i = 0; i < n; i++)
str[i] = pop(stack);
}

// Driver code
int main()
{
char str[] = "GeeksQuiz";

reverse(str);
cout << "Reversed string is " << str;

return 0;
}



27. 

C++ Program to convert infix expression to postfix


Input .   
Output.   abcd^e-fgh*+^*+i-

                  

/* C++ implementation to convert infix expression to postfix*/
// Note that here we use std::stack for Stack operations
#include<bits/stdc++.h>
using namespace std;

//Function to return precedence of operators
int prec(char c)
{
if(c == '^')
return 3;
else if(c == '*' || c == '/')
return 2;
else if(c == '+' || c == '-')
return 1;
else
return -1;
}

// The main function to convert infix expression
//to postfix expression
void infixToPostfix(string s)
{
std::stack<char> st;
st.push('N');
int l = s.length();
string ns;
for(int i = 0; i < l; i++)
{
// If the scanned character is an operand, add it to output string.
if((s[i] >= 'a' && s[i] <= 'z')||(s[i] >= 'A' && s[i] <= 'Z'))
ns+=s[i];

// If the scanned character is an ‘(‘, push it to the stack.
else if(s[i] == '(')

st.push('(');

// If the scanned character is an ‘)’, pop and to output string from the stack
// until an ‘(‘ is encountered.
else if(s[i] == ')')
{
while(st.top() != 'N' && st.top() != '(')
{
char c = st.top();
st.pop();
ns += c;
}
if(st.top() == '(')
{
char c = st.top();
st.pop();
}
}

//If an operator is scanned
else{
while(st.top() != 'N' && prec(s[i]) <= prec(st.top()))
{
char c = st.top();
st.pop();
ns += c;
}
st.push(s[i]);
}

}
//Pop all the remaining elements from the stack
while(st.top() != 'N')
{
char c = st.top();
st.pop();
ns += c;
}

cout << ns << endl;

}

//Driver program to test above functions
int main()
{
string exp = "a+b*(c^d-e)^(f+g*h)-i";
infixToPostfix(exp);
return 0;
}



26. 

C++ program to demonstrate all insertion methods on Linked List


Input .   Insert Numbers
Output.   Created Linked list is: 1 7 8 6 4

                  

// A complete working C++ program to demonstrate
// all insertion methods on Linked List
#include <bits/stdc++.h>
using namespace std;

// A linked list node
class Node
{
public:
int data;
Node *next;
};

/* Given a reference (pointer to pointer)
to the head of a list and an int, inserts
a new node on the front of the list. */
void push(Node** head_ref, int new_data)
{
/* 1. allocate node */
Node* new_node = new Node();

/* 2. put in the data */
new_node->data = new_data;

/* 3. Make next of new node as head */
new_node->next = (*head_ref);

/* 4. move the head to point to the new node */
(*head_ref) = new_node;
}

/* Given a node prev_node, insert a new node after the given
prev_node */
void insertAfter(Node* prev_node, int new_data)
{
/*1. check if the given prev_node is NULL */
if (prev_node == NULL)
{
cout<<"the given previous node cannot be NULL";
return;
}

/* 2. allocate new node */
Node* new_node = new Node();

/* 3. put in the data */
new_node->data = new_data;

/* 4. Make next of new node as next of prev_node */
new_node->next = prev_node->next;

/* 5. move the next of prev_node as new_node */
prev_node->next = new_node;
}

/* Given a reference (pointer to pointer) to the head
of a list and an int, appends a new node at the end */
void append(Node** head_ref, int new_data)
{
/* 1. allocate node */
Node* new_node = new Node();

Node *last = *head_ref; /* used in step 5*/

/* 2. put in the data */
new_node->data = new_data;

/* 3. This new node is going to be
the last node, so make next of
it as NULL*/
new_node->next = NULL;

/* 4. If the Linked List is empty,
then make the new node as head */
if (*head_ref == NULL)
{
*head_ref = new_node;
return;
}

/* 5. Else traverse till the last node */
while (last->next != NULL)
last = last->next;

/* 6. Change the next of last node */
last->next = new_node;
return;
}

// This function prints contents of
// linked list starting from head
void printList(Node *node)
{
while (node != NULL)
{
cout<<" "<<node->data;
node = node->next;
}
}

/* Driver code*/
int main()
{
/* Start with the empty list */
Node* head = NULL;

// Insert 6. So linked list becomes 6->NULL
append(&head, 6);

// Insert 7 at the beginning.
// So linked list becomes 7->6->NULL
push(&head, 7);

// Insert 1 at the beginning.
// So linked list becomes 1->7->6->NULL
push(&head, 1);

// Insert 4 at the end. So
// linked list becomes 1->7->6->4->NULL
append(&head, 4);

// Insert 8, after 7. So linked
// list becomes 1->7->8->6->4->NULL
insertAfter(head->next, 8);

cout<<"Created Linked list is: ";
printList(head);

return 0;
}



25. 

C++ program to demonstrate example of friend function with class


Input .   
Output.   Value of a (private data member of class Number): 1000

                  

/*C++ program to demonstrate example of friend function with class.*/
#include <iostream>

using namespace std;

class Number
{
private:
int a;
public:
void getNum(int x);
//declaration of friend function
friend void printNum(Number NUM);


};

//class member function definitions
void Number::getNum(int x)
{
a=x;
}

//friend function definition, no need of class name with SRO (::)
void printNum(Number NUM)
{
cout << "Value of a (private data member of class Number): " << NUM.a;

}

int main()
{
Number nObj; //Object declaration
nObj.getNum(1000);
printNum(nObj);
return 0;
}



24. 

C++ program to create class to get and print details of a student


Input .   Enter name: mike Enter roll number: 112 Enter total marks outof 500: 456
Output.   Student details: Name:mike,Roll Number:112,Total:456,Percentage:91.2

                  

/*C++ program to create class for a student.*/
#include <iostream>
using namespace std;

class student
{
private:
char name[30];
int rollNo;
int total;
float perc;
public:
//member function to get student's details
void getDetails(void);
//member function to print student's details
void putDetails(void);
};

//member function definition, outside of the class
void student::getDetails(void){
cout << "Enter name: " ;
cin >> name;
cout << "Enter roll number: ";
cin >> rollNo;
cout << "Enter total marks outof 500: ";
cin >> total;

perc=(float)total/500*100;
}

//member function definition, outside of the class
void student::putDetails(void){
cout << "Student details:\n";
cout << "Name:"<< name << ",Roll Number:" << rollNo << ",Total:" << total << ",Percentage:" << perc;
}

int main()
{
student std; //object creation

std.getDetails();
std.putDetails();

return 0;
}



23. 

C++ program to demonstrate example of Constructor Overloading


Input .   Default Constructor: Value after initialization: X: 10 Y: 20
Output.   Parameterized Constructor: Value after initialization: X: 30 Y: 40

                  

/*C++ program to demonstrate example of Constructor Overloading.*/
#include <iostream>
using namespace std;

//Class declaration.
class Demo
{
//Private block to declare data member( X,Y ) of integer type.
    private:
int X;
int Y;

//Public blocks of member function to access data members.
    public:
//Declaration of default constructor to initialize data members.
Demo ();

//Declaration of parameterized constructor to initialize data members.
Demo (int a, int b);
//To display output onn screen.
void Display();

};//End of class

//Definition of parameterized constructor.
Demo:: Demo()
{
X = 10;
Y = 20;
}

//Definition of parameterized constructor.
Demo:: Demo(int a, int b)
{
X = a;
Y = b;
}


//Definition of Display() member function.
void Demo:: Display()
{
cout << endl << "X: " << X;
cout << endl << "Y: " << Y << endl;
}

int main()
{
Demo d1;
cout << "Default Constructor: " << endl;
cout << "Value after initialization : " ;
d1.Display();

Demo d2(30,40) ; //Ctor automatically call when object is created.
cout << "Parameterized Constructor: " << endl;
cout << "Value after initialization : " ;
d2.Display();

return 0;
}



Enter Email If You are new here So You will get Daily Notification Dont Forget any single Question:

E-mail: