Hot Topics
Company Based – Codewindow
Nagarro Question Solved | Cheat Ways | Codewindow.in
It is examination time and as always, the backbenchers are finding ways to cheat in the exam and they need your help. Their teacher is very fond of data structures and has mad the seating arrangment in the form of a tree.
There are N students in class numbered from 1,2….N with 1 as the root of this tree.We have k first benchers(teachers favorites) students in the class.
The backbenchers are planning to pass chits in teams,but are afraid of the first benchers.If any chit reaches them. They will complain to the teacher.
A cheat way is defined as the path along which a chit can be passed without going through a first bencher. Given the seating arrangement and numbers of first benchers,
Your task is to find the longest cheat way possible.
Input Specification:
Input 1: Total number of students in the class N.
1<=N<=10000.
Input 2: A 2D array with N-1 rows, each consisting of two integers C and D,
Denoting C and D are sitting adjacent. Only adjacent students can pass chits directly to each other.
Input 3: Number of first benchers.
0<=k<=N
Input 4: Array of K numbers denoting position of each first bencher.
1<=input4[i]<=N
Output Specifications:
Return length of the longest cheat way possible.
Example 1:
input1: 5
input2: {{1,2},{1,3}{3,4},{3,5}}
input3: 1
input4: {3}
Output: 1
C++
int Helper(vector<vector<int>> &matrix, int input1, unordered_set <int> &uset, vector<int> &visited, int root) {
visited[root] = 1;
int length = 0;
for (int i-1; i<=input1 i++) {
int len = 0;
if(matrix[root][i] == 1 && uset.find (i ) == uset.end () && visited [i] == 0) {
len = 1 + Helper(matrix, input1, uset, visited, i);
}
length += len
}
visited[root] = 0;
return length;
}
int cheat (int input1, int **input2, int input3, int input4[t]){
vector<vector><int>> matrix(input1+1, vector<int>(input1+1 , 0));
for (int i=0; i<input1-1 i++) {
matrix[input2[i][0]i[input2[il[1]] = 1;
}
unordered_set<int> uset;
for(int i=0;i<input3; i++){
uset.insert(input4[i]);
}
int length = 0
vector<int> visited (input1+1, 0);
for(int i=1 ; i<=input1; i++){
if(!visited [i] && uset. find (i) == uset.end ()){
//Call dfs
int len = Helper(matrix, input1, uset, visited, i);
length = max(length len);
}
}
return length;
}
Automata Fixing
Popular Category
Hot Topics
Company Based – Codewindow