Combined 6 Bank Assistant Programmer 200 Marks Written Question Solution

Question 1: Topological sorting for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge u v, vertex u comes before v in the ordering. Topological Sorting for a graph is not possible if the graph is not a DAG. Now write a C/C++ Program with the following input and Output

Input:

5 4

1 2

2 3

1 3

1 5

Output:

4 2 5 3

Solution:

#include <iostream>

#include <list>

#include <stack>

using namespace std;

// Class to represent a graph

class Graph {

// No. of vertices'

int V;

// Pointer to an array containing adjacency listsList

// A function used by topologicalSort

void topologicalSortUtil(int v, bool visited[], stack<int>& Stack);

public:

// Constructor

Graph(int V);

// function to add an edge to graph

// prints a Topological Sort of

// the complete graph

void topologicalSort();

};

Graph::Graph(int V)

{

this->V = V;

}

{

// Add w to v’s list.

}

// A recursive function used by topologicalSort

void Graph::topologicalSortUtil(int v, bool visited[], stack<int>& Stack)

{

// Mark the current node as visited.

visited[v] = true;

// Recur for all the vertices

list<int>::iterator i;

if (!visited[*i])

topologicalSortUtil(*i, visited, Stack);

// Push current vertex to stack

// which stores result

Stack.push(v);

}

// The function to do Topological Sort.

// It uses recursive topologicalSortUtil()

void Graph::topologicalSort()

{

stack<int> Stack;

// Mark all the vertices as not visited

bool* visited = new bool[V];

for (int i = 0; i < V; i++)

visited[i] = false;

// Call the recursive helper function

// to store Topological

// Sort starting from all

// vertices one by one

for (int i = 0; i < V; i++)

if (visited[i] == false)

topologicalSortUtil(i, visited, Stack);

// Print contents of stack

while (Stack.empty() == false) {

cout << Stack.top() << " ";

Stack.pop();

}

}

// Driver Code

int main()

{

// Create a graph given in the above diagram

Graph g(5);

// Function Call

g.topologicalSort();

return 0;

}

Output:

4 2 5 3

Question 2: Write a C/C++ program to check Balanced parenthesis in an Expression

Solution: Take open parentheses immediately into stack. If we get a close parentheses then we check if the stack is nonempty and the top item is the matched open parentheses. In that case we pop the top element. Otherwise we can determine it’s an unbalanced parentheses. Finally if the stack is empty after processing all parentheses then we can say it’s a balanced parentheses.

#include<bits/stdc++.h>

using namespace std;

bool isBalancedExp(string exp) {

stack<char>stk;

char x;

for (int i=0; i<exp.length(); i++) {

if (exp[i]=='(' || exp[i]=='[' || exp[i]=='{') {

stk.push (exp[i]);

continue;

}

if (stk.empty())

return false;

switch (exp[i]) {

case ')':

x = stk.top();

stk.pop();

if (x=='{' || x=='[')

return false;

break;

case '}':

x = stk.top();

stk.pop();

if (x=='(' || x=='[')

return false;

break;

case ']':

x = stk.top();

stk.pop();

if (x == '(' || x == '{')

return false;

break;

}

}

return (stk.empty());

}

int main() {

char expression[100];

gets(expression);

if(isBalancedExp(expression))

cout << "This is Balanced Expression";

else

cout << "This is Not Balanced Expression";

}

Question 3.  We are given an array of integers and a range, we need to find whether the subarray which falls in this range has values in the form of a mountain or not. All values of the subarray are said to be in the form of a mountain if either all values are increasing or decreasing or first increasing and then decreasing.

Write a C/C++ Program that shows input is a Mountain sequence or Not Mountain sequence

Solution:  To check if the sequence is mountain we have to make sure that no neighbouring elements are the same. C++ code here -

#include<bits/stdc++.h>

using namespace std;

#define ll long long

bool isMountain(vector<ll> a)

{

ll n=a.size(),i;

for(i=0;i<n-1;i++)

if((i>0 && a[i]==a[i-1])||(i<n-1 && a[i]==a[i+1]))

return false;

return true;

}

int main()

{

ll i,j,n;

cin>>n;

vector<ll> a(n);

for(i=0; i<n; i++)

cin>>a[i];

if(isMountain(a))

cout<<"Mountain"<<endl;

else

cout<<"Not Mountain"<<endl;

}

Input:

6

1 2 1 1 3 4

Output: Not Mountain

Input:

6

1 2 1 3 2 4

Output: Mountain

Extra program: Find the length of maximum values in mountain sequence

Sample input: 121234531

Output: 7

Explanation: 121=3

1234531=7

Function:

Int longestMountain(int *A, int n)

{

Int n= len(A);

Int ans=base=0, end;

While(base<n)

{

end=base;

While((end+1)<n &&

A[end]< A[end+1])

end++;

While((end+1)<n &&

A[end]> A[end+1])

end++;

ans = max(ans, end-base+1);

base = max(end, base+1);

}

Return ans;

}

Question 4. Given n jobs starting time n[] and duration d[], print maximum number of jobs that don’t overlap between each other.

Solution: This is actually a greedy approach. Sort all the jobs according to their duration in ascending order. Then take jobs one by one which doesn’t overlap with any other previously taken jobs. This will ensure maximum jobs taken without any overlap. C++ code here -

#include<bits/stdc++.h>

using namespace std;

#define ll long long

bool doesOverlap(pair<ll,ll> job1, pair<ll,ll> job2)

{

if(job1.second<=job2.first || job1.first>=job2.second)

return false;

return true;

}

int main()

{

ll i,j,n;

cin>>n;

vector<pair<ll,ll>> job(n);

for(i=0;i<n;i++)

cin>>job[i].second>>job[i].first; //input second element is start time, first element is duration

sort(job.begin(),job.end()); //sort the job array according to their duration in ascending order

vector<pair<ll,ll>> jobTime(n);

for(i=0;i<n;i++)

jobTime[i]=make_pair(job[i].second,job[i].second+job[i].first);

vector<pair<ll,ll>> unoverlappedJobs;

unoverlappedJobs.push_back(jobTime[0]);

for(i=1;i<n;i++)

{

bool doesNotOverlapWithAnyTakenJob=true;

for(j=0;j<unoverlappedJobs.size();j++)

{

if(doesOverlap(jobTime[i],unoverlappedJobs[j]))

{

doesNotOverlapWithAnyTakenJob=false;

break;

}

}

if(doesNotOverlapWithAnyTakenJob)

unoverlappedJobs.push_back(jobTime[i]);

}

sort(unoverlappedJobs.begin(),unoverlappedJobs.end());

cout<<"Total Jobs "<<unoverlappedJobs.size()<<endl;

for(i=0;i<unoverlappedJobs.size();i++)

cout<<unoverlappedJobs[i].first<<" "<<unoverlappedJobs[i].second-unoverlappedJobs[i].first<<endl;

}

Question 5. You are given weights and values of N items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack. Note that we have only one quantity of each item. In other words, given two integer arrays val[0..N-1] and wt[0..N-1] which represent values and weights associated with N items respectively. Also given an integer W which represents knapsack capacity, find out the maximum value subset of val[] such that sum of the weights of this subset is smaller than or equal to W. You cannot break an item, either pick the complete item or don’t pick it (0-1 property).

Write a C/C++ Program that satisfies the following input and Output.

Input:

N = 3

W = 4

values[] = {1,2,3}

weight[] = {4,5,1}

Output: 3

Input:

N = 3

W = 3

values[] = {1,2,3}

weight[] = {4,5,6}

Output: 0

Solution:

/* A Naive recursive implementation of

0-1  Knapsack problem */

0-2

#include <bits/stdc++.h>

using namespace std;

// A utility function that returns

// maximum of two integers

int max(int a, int b) { return (a > b) ? a : b; }

// Returns the maximum value that

// can be put in a knapsack of capacity W

int knapSack(int W, int wt[], int val[], int n)

{

// Base Case

if (n == 0 || W == 0)

return 0;

// If weight of the nth item is more

// than Knapsack capacity W, then

// this item cannot be included

// in the optimal solution

if (wt[n - 1] > W)

return knapSack(W, wt, val, n - 1);

// Return the maximum of two cases:

// (1) nth item included

// (2) not included

else

return max(

val[n - 1]

+ knapSack(W - wt[n - 1],

wt, val, n - 1),

knapSack(W, wt, val, n - 1));

}

// Driver code

int main()

{

int val[] = { 60, 100, 120 }; // this value will be changed

int wt[] = { 10, 20, 30 }; // this value will be changed

int W = 50; // this value will be changed

int n = sizeof(val) / sizeof(val[0]);

cout << knapSack(W, wt, val, n);

return 0;

}

Question 6. Writing True/False (4 sentence), and write reason of true/false. – 16 marks

a. A directed graph contains a strongly connected component of |S| nodes. After adding a new edge to the graph, the maximum number node in new strongly connected component will be 1 to |s|.

(Full questions can not be collected, sample idea is here)

a) Back edge in DAG

b) extra edge in DAG

c) strongly connected component

d) unique path on different weight on graph

Question 7. Write a C/C++ Program that has a Class Account, Subclass Savings Account, Current Account etc with related hierarchy way.

Sample Solution:

#include<bits/stdc++.h>

using namespace std;

//class account declaration and definition

class account

{

public:

char name[30];

int acc_num, acc_type;

int balance;

int amount;

//to initialize instance members

void getData()

{

cout<<"\nEnter the following details\nCustomer Name :";

gets(name);

cout<<"\nAccount number :";

cin>>acc_num;

cout<<"\nAccount type\n1. Saving Account\n2.Current Account\n";

cin>>acc_type;

cout<<"\nAccount balance:";

cin>>balance;

}

//to display balance

void display()

{

}

//to withdraw money from account

void withdraw()

{

cout<<"\nEnter the amount you want to withdraw :";

cin>>amount;

if(amount>balance)

cout<<"\nInsuficient balance";

else

balance=balance-amount;

display();

}

};

//class current account

class cur_acct:public account

{

public:

void panelty()

{

if(balance<200 && acc_type==2)

{

balance=balance-20;

display();

}

}

};

//class saving account

class sav_acct:public account

{

public:

void interest()

{

int t;

cout<<"\nEnter time interval in year:";

cin>>t;

balance=balance*(1+2*t);

display();

}

};

//main() to test account

int main()

{

account ac;

ac.getData();

ac.display();

ac.withdraw();

}

Question 8. Write the definition of Inheritance, polymorphism, encapsulation, abstraction with coding example

Solution:

Inheritance in Java is a mechanism in which one object acquires all the properties and behaviors of a parent object. It is an important part of OOPs (Object Oriented programming system).

Code Example:

class Employee{

float salary=40000;

}

class Programmer extends Employee{

int bonus=10000;

public static void main(String args[]){

Programmer p=new Programmer();

System.out.println("Programmer salary is:"+p.salary);

System.out.println("Bonus of Programmer is:"+p.bonus);

}

}

Polymorphism in Java is a concept by which we can perform a single action in different ways. Polymorphism is derived from 2 Greek words: poly and morphs. The word "poly" means many and "morphs" means forms. So polymorphism means many forms.

There are two types of polymorphism in Java: compile-time polymorphism and runtime polymorphism. We can perform polymorphism in java by method overloading and method overriding.

If you overload a static method in Java, it is the example of compile time polymorphism. Here, we will focus on runtime polymorphism in java.

Code Example:

class Bike{

void run(){System.out.println("running");}

}

class Splendor extends Bike{

void run(){System.out.println("running safely with 60km");}

public static void main(String args[]){

Bike b = new Splendor();//upcasting

b.run();

}

}

Encapsulation in Java is a process of wrapping code and data together into a single unit, for example, a capsule which is mixed of several medicines.

We can create a fully encapsulated class in Java by making all the data members of the class private. Now we can use setter and getter methods to set and get the data in it.

Code Example:

//A Java class which is a fully encapsulated class.

//It has a private data member and getter and setter methods.

package com.javatpoint;

public class Student{

//private data member

private String name;

//getter method for name

public String getName(){

return name;

}

//setter method for name

public void setName(String name){

this.name=name

//A Java class to test the encapsulated class.

package com.javatpoint;

class Test{

public static void main(String[] args){

//creating instance of the encapsulated class

Student s=new Student();

//setting value in the name member

s.setName("vijay");

//getting value of the name member

System.out.println(s.getName());

}

}

Abstraction is a process of hiding the implementation details and showing only functionality to the user.

Another way, it shows only essential things to the user and hides the internal details, for example, sending SMS where you type the text and send the message. You don't know the internal processing about the message delivery.

Abstraction lets you focus on what the object does instead of how it does it.

Code Example:

abstract class Bank{

abstract int getRateOfInterest();

}

class SBI extends Bank{

int getRateOfInterest(){return 7;}

}

class PNB extends Bank{

int getRateOfInterest(){return 8;}

}

--------------------

class TestBank{

public static void main(String args[]){

Bank b;

b=new SBI();

System.out.println("Rate of Interest is: "+b.getRateOfInterest()+" %");

b=new PNB();

System.out.println("Rate of Interest is: "+b.getRateOfInterest()+" %");

}}

Question 9. State diagram of DFA using binary strings having 0 with multiple of 3. Also showing regular expression

Question 10. Write SQL command from the following tables.

Employee(ename, street, city)

Works(ename, cname, salary, joindate)

Company(cname, city)

Manages(ename, mname)

a.      Find name, street, city who work for First Corporation Bank and earn more than 30000

b.      Find name of all employees, who live in the same city and company for which they works.

c.       Give all employees of First Century Bank 10 percent salary raise

d.      Find the company with payroll less than 100000

Solution:

a.      Select e.ename, street, city from Employee e, Works w where e.ename = w.ename and w.cname = “First Corporation Bank” and w.salary > 30000

b.      Select e.ename from Employee e, Works w, Company c where e.ename=w.ename and e.city=c.city and w.cname=c.cname

c.       Update Works set salary = salary + salary*0.1 where cname = “First Corporation Bank”

d.      Select cname from Works group by cname having sum(salary) < 100000

Extra Question. Draw E-R diagram from a story

(the story cannot be collected)

Question 11. à¦«োà¦•াà¦¸ঃà¦¬াংà¦²া à¦¬à¦¨্à¦¡(20 marks)

# Question 12.English Focus: Bhasan Char: A Safe Home for Rohingya Refugees (20 marks)

The government move to relocate 1,642 Rohingya refugees to Bhasan Char has invited some negative international scrutiny, but local NGOs and experts have said international aid agencies might change their minds if they visited the island. Global rights groups claimed that many of those who were relocated to the housing project in the island under Noakhali's Hatiya upazila were coerced to do so. The UN, meanwhile, said it lacked information on the relocation and was not involved in the exercise. The government negated the criticisms, saying the concerns about the Rohingya refugees' safety and the Bhasan Char project's sustainability were well addressed.

It argued that cyclone Amphan could do the project no harm as the structures have been sufficiently elevated and embankments have been built for flood protection. There are cyclone shelters, schools, hospitals, livelihood opportunities and playgrounds -- facilities that are far better than those in the crowded refugee camps in Cox's Bazar.

Apart from the risk of landslides, the government cited issues such as drug peddling, human trafficking, a rising trend of gender-based violence and conflicts between factions of the refugee communities in Cox's Bazar as major reasons for the relocation.

While these and other factors may have prompted the government to opt for the relocation, the fact remains that the relocation of the first batch has happened and the government will eventually transfer about 100,000 to Bhasan Char. The UN and international aid agencies are however yet to be involved in humanitarian assistance. This has given rise to questions about how the lives of Rohingya refugees in Bhasan Char will be funded and managed.

Saiful Islam Chowdhury Kalim, coordinator of the alliance of 22 local NGOs that have been engaged in humanitarian activities in Bhasan Char with their own funds, said the office of the Refugee Relief and Rehabilitation Commissioner (RRRC) that supervises the Rohingya camps in Cox's Bazar is doing the same in Bhasan Char.

"We have stock of food for six months. Now we are assessing the demand and challenges ahead," he told this correspondent. "Initially, the NGOs cooked food for the Rohingyas but now they are provided stoves, gas cylinders and food stuff to cook for themselves [in Bhasan Char]."

Saiful Islam said they too had negative idea about the Bhasan Char project initially, but everything became clear after visiting the site.

"I think international agencies' idea will change if they come here," he said, adding that there is no such infrastructure for refugees anywhere in the world. He said they are searching for international donors, but if they fail, they have contingency plans for mobilising funds locally.

Besides, Rohingyas can eventually be engaged in income-generating activities that can be helpful, he said.

Prof Imtiaz Ahmed, director at the Centre for Genocide Studies of the International Relations Department at Dhaka University, said it is unfortunate that the UN has not congratulated Bangladesh for its efforts to improve the lives of Rohingya refugees through relocation.

He said a country has the right to shelter refugees in places that it finds suitable. There will always be some issues wherever they are, but the government has built a planned housing. The facilities at Bhasan Char may not provide all the privileges the refugees want, but is much better than the present ones in Cox's Bazar.

"Bangladesh is not only a victim of Myanmar's genocidal acts, but also of global and regional geopolitics," Prof Imtiaz said. The international community is not as vocal on Rohingya repatriation as it is on the Rohingya situation in Bangladesh, he added.

"The UN should focus on Myanmar and repatriation, not Bangladesh, on the Rohingya question," he said.

Asked on funds and management of Rohingyas in Bhasan Char, the professor said he expects UN and other aid agencies will get involved in Bhasan Char soon.

Prof Imtiaz said the UN is not against relocation, but there is a communication gap between the government and the UN. "It should be removed immediately for the better."

Meanwhile, a few NGO officials working in the Rohingya camps said the government had become more adamant aboutthe relocation because international aid agencies made "excessive level of criticism" about the Bhasan Char project, even though the government had spent \$350 million from its own fund for the betterment of the refugees. Also, they said the Rohingyas, especially families with young girls unwilling to be engaged in any conflict, had volunteered to go to Bhasan Char.

They also pointed to international aid agencies' high-handedness in management of the Rohingya camps.

A statement Foreign Minister AK Abdul Momen made to this correspondent recently is reflective of this. He said government officials working in refugee camps are provided "financial incentives" by international aid agencies, whose foreign workers also draw high amount of benefits due to high per diems in Cox's Bazar, which is why they are reluctant to move to Bhasan Char.

While these claims need to be verified, local NGOs have long been saying that international aid agencies' operations in the camps were too expensive -- an issue that needs to be addressed by employing Bangladeshi NGOs at operational levels.

Two UN officials reacted differently when asked whether the UN would be involved in Bhasan Char as the government wants it to be. One said they would not go unless a technical assessment by a UN team is done, while the other said the UN Refugee Agency is obliged to go to Bhasan Char if the government wants as looking after refugees -- wherever they are -- is its mandate.

"We are observing what happens in Bhasan Char… how the community fares," a UN official told this correspondent.