I was asked the following question in Microsoft:

Design a project which is very similar to Microsoft project. A Project has dependencies on various tasks. Each of these tasks have dependencies on various sub tasks each of which can have further dependencies on other sub tasks.
Say:

P
|__ T1
|__ T2

T1
|___ T2

i.e P has a dependency on Task T1 and Task T2.
T1 has a dependency on Task T2.

We are given the time taken for each individual task.
Please note that various tasks can also execute in parallel (tasks which are not dependent on each other)

Please tell:

1. How will you represent such a problem.
2. Find minimum time taken for total project take to execute
3. If we change the time taken for one of the tasks(either increase or decrease) then how to estimate the new time taken for the project.
4. How will the UI updation take place in such cases.

My Thoughts:
I proposed using a directed graph where each edge direction is from the dependency to the dependent task. During the graph construction phase we will also detect for a cycle. I suggested that it is a topological sort problem.

For time taken I proposed to start from nodes with indegree 0 and then moving to nodes with 1 more indegree. At each step calculate the minimum time for start of the task and minimum time for the task to end.

Interviewer was satisfied with the approach after the discussion. But I am not sure if the topological sort is the correct solution of the problem or not. From what I read on the Internet later on, this is not a topological sort problem but is known as critical path method.

Please suggest how to approach this problem from system design point of view.