NINJA’S ACADEMY

Hard
0/120
Average time to solve is 15m
profile
Contributed by
6 upvotes
Asked in company
Amazon

Problem statement

Coding Ninjas is offering lots of courses. But for enrolled in courses, there may be some prerequisites according to the course. So lots of queries are coming for confirming the sequence, of course, to confirm that the sequence of taking the course is correct or not.

So help our ninja to write a code so he can give an answer to the queries whether the sequence is correct or not.

So your task is to answer each query whether it is a correct sequence or not. You will be provided with the total number of courses 'N', a list of direct prerequisite pairs, and a list of query pairs.

Example:

Example

In the image left side represents the prerequisite and on-right queries.
consider the following example suppose the number of courses ‘N = 2’prerequisites pair is [ [ 1, 0 ] ] and queries are [ [ 0, 1 ], [ 1, 0 ] ] so we return [ False, True ]  as ‘0’is not a prerequisite for the course ‘1’but ‘1’is prerequisite for the course ‘0’.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains an integer  ‘T' which denotes the number of test cases or queries to be run. Then the test cases follow:

The first line of each test case contains, the total number of courses.

The second line of each test case contains an integer ‘M’ and ‘Q’ denoting the number of rows in the array ‘PREREQUISITE’ and ‘Q’ rows in array queries.

Then, ‘M’ lines follow:
Each line contains ‘2’ space-separated integers denoting the row values.

Then, ‘Q’ lines follow:
Each line contains ‘2’ space-separated integers denoting the row values.
Output Format : 
For each test case, print ‘True’ if the order is correct else ‘False’.

Print output of each test case in a separate line.
Note: 
You are not required to print anything explicitly. It has already been taken care of. Just implement the function.
Constraints: 
1 <= T <= 10^2
1 <= N <= 3*10^3
0 <= PREREQUISITE[i] <= 3*10^3

Where ‘T’ is the total number of test cases, ‘N’ is the number of courses and 'PREREQUISITE[i]' is the value of that courses.

Time Limit: 1 sec
Sample Input 1:
2
3
2 2
1 0
2 0
0 1
2 0
5
4 4
1 2
0 1
2 3
3 4
0 4
4 0
1 3
3 0

Sample Output 1:

False True
True False True False

Explanation of Sample Input 1:

Test Case 1:

Example

In this image left side represents the prerequisite array and the right side represents the query array.
So according to this test case, the number of courses is ‘N = 3’ prerequisite array is [ [ 1, 0 ], [ 2, 0 ] ] and queries array is [ [ 0, 1 ], [ 2, 0 ] ] so we return ‘False’ and ‘True’ as ‘0’ is not prerequisite for ‘1’ course and 2 is prerequisite for the course ‘0’.

Test Case 2:

Example

In this image left side represents the prerequisite array and the right side represents the query array.

So according to this test case, the number of courses is ‘N = 5’ prerequisite array is [ [ 0,1 ], [ 1, 2 ], [ 2, 3 ], [ 3, 4 ] ] and queries array is [ [ 0, 4 ], [ 4, 0 ], [ 1, 3 ], [ 3, 0 ] ] so we return ‘True’ for the first query and the third query as ‘1’ is indirectly prerequisite for course ‘4’ as well as for course ‘3’.and we return ‘False’ for the second and fourth query as ‘0’ is prerequisite for course ‘3’ and ‘4’ not ‘3’ and ‘4’ are prerequisite for the course ‘0’.

Sample Input 2:

2
3
3 2
1 2
1 0
2 0
1 0
1 2
3
2 2
1 0
2 0
0 1
2 0

Sample Output 2:

True True
False True
Hint

Can you iterate over the courses? 

Approaches (2)
Dynamic Programming

We can think of solving this problem like a graph where we can link courses with a directed edge if the prerequisite is needed and now we can check if it is possible or not for each query. Like we make nodes with the value of courses and join them in the form of the directed graph if the prerequisite is needed.

 

  1. First, we create a graph with the help of a prerequisite and join our nodes according to the pair given in the prerequisite
    • For creating the graph we declare a matrix of size N*N where N is a number of courses.
    • Now if there is a pair of prerequisites we fill that position with ‘1’which indicates there is a link between them.
    • We join with the help of a directed edge.
  2. Now we used a loop and check for each and every pair whether we are able to visit that node or not.
  3. We used three nested for loop and if a node exists between that node we check if the shortest path is different from infinity we are able to visit that node.
  4. If we are able to visit that node we return ‘True’else we return ‘False’if we are not able to visit that node and our control comes out of while statement.
Time Complexity

O(N^3), where ‘N’ is size of the array.

 

We are iterating a three-nested loop of size ‘N’ to fill the value of ‘DP’ array. Hence the time complexity is O(N^3).

Space Complexity

O(N^2), where ‘N’ is the size of the array.

 

As we are declaring a ‘DP’ array of size ‘N’ ^ 2. Hence the space complexity is O(N^2).

Code Solution
(100% EXP penalty)
NINJA’S ACADEMY
Full screen
Console