Tuesday, July 26, 2016

TCS Mock Code vita-1(Season-5) program-3

Problem : TestVita
TCS is working on a new project called "TestVita". There are N modules in the project. Each module (i) has completion time denoted in number of hours (Hi) and may depend on other modules. If Module x depends on Module y then one needs to complete y before x. 

As Project manager, you are asked to deliver the project as early as possible.
 
Provide an estimation of amount of time required to complete the project.
 
Input Format: 

First line contains
 T, number of test cases. 

For each test case:
 
1.      First line contains N, number of modules.
2.      Next N lines, each contain:
o    (i) Module ID
o    (Hi) Number of hours it takes to complete the module
o    (D) Set of module ids that i depends on - integers delimited by space.

Output Format: 

Output the minimum number of hours required to deliver the project.
 
Constraints:
1. 1 <= T <= 10
2. 0 < N < 1000; number of modules
3. 0 < i <= N; module ID 
4. 0 < Hi < 60; number of hours it takes to complete the module i 
5. 0 <= |D| < N; number of dependencies
6. 0 < Dk <= N; module ID of dependencies 

Sample Input and Output
SNo.
Input
Output
1

1
5
1 5
2 6 1
3 3 2
4 2 3
5 1 3

16


Explanation: 

Module 2 depends on module 1, hence complete module 1 first
 

After completing module 1 we can complete module 2 and then module 3
 

Module 4 and 5 can be started simultaneously in parallel after module 3 is completed.
 

Hence the answer = 5 + 6 + 3 + 2 = 16