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
<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
list<int>*
adj;
// 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
void
addEdge(int v, int w);
//
prints a Topological Sort of
//
the complete graph
void
topologicalSort();
};
Graph::Graph(int
V)
{
this->V
= V;
adj
= new list<int>[V];
}
void
Graph::addEdge(int v, int w)
{
//
Add w to v’s list.
adj[v].push_back(w);
}
// 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
//
adjacent to this vertex
list<int>::iterator
i;
for
(i = adj[v].begin(); i != adj[v].end(); ++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);
g.addEdge(5,
4);
g.addEdge(1,
2);
g.addEdge(2,
3);
g.addEdge(1,
3);
g.addEdge(1, 5);
//
Function Call
g.topologicalSort();
return
0;
}
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;
}
Courtesy: https://www.facebook.com/Ovi.ICT/ And, https://docs.google.com/document/d/17Ow3jPr9GqNl3Ruqo4a59eue5hMXVNKEUWCRgMN1_38/edit
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()
{
cout<<"\nYour Account
Balance :"<<balance;
}
//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
Solution Help Link:
https://www.geeksforgeeks.org/check-binary-string-multiple-3-using-dfa/
and
https://www.geeksforgeeks.org/dfa-that-recognizes-number-of-0-is-multiple-of-3-on-input-01/
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)
Solution Link:
http://forum.bcsexamination.com/17
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.