Question 1
Introduction
Because there is a ton of code in our app, developers are experiencing very long build times. The way this build system works is, when you make any code change in a module, all modules that depend on that module (either directly or transitively) must be rebuilt. The goal of this challenge is to calculate a metric that represents the cost of making a change to a module in development. We refer to this metric as the cost of the module and it equals the number of modules that need to be rebuilt as the result of a code change.
For Example
The application has the following modules:
- A: App (the application entry-point)
- S: Stays
- H: Homes
- E: Experiences
- N: Networking
And the dependency graph looks like this:
A______
____|____ |
↓ ↓ |
S E |
↙ ↘ ↙ |
H N ←---
Dependencies:
- The Application (A) module depends on Stays (S), Experiences (E), and Networking (N)
- The Stays (S) module depends on Homes (H) and Networking (N)
- The Experiences (E) module depends on Networking (N)
Cost of each module:
The cost of N is 4
- Because making a code change to N requires rebuilding N, S, E, and A
The cost of H is 3
- Because making a code change to H requires rebuilding H, S, and A
The cost of S is 2
- Because making a code change to S requires rebuilding S and A
The cost of E is 2
- Because making a code change to E requires rebuilding E and A
The cost of A is 1
- Because making a code change to A required rebuilding just A
Input
The first line is a number indicating how many lines follow. On each following line of input, the first item represents a module in our dependency graph, then a comma, followed by all of it's children also separated by commas. There is no circles in the dependency graph. For the example, the input looks like this:
5
A,E,N,S
S,H,N
E,N
H
N
The first line says that E, N, and S, are children of A. The second line says that H and N are children of S. The third line says the N is the only child of E. The fourth line says that H has no children.
Output
Given the input as described above, your costOfNodes function should output a line for each module with the module name following by it's cost. The Lines should be sorted by module name. For the example, the output should be:
A,1
E,2
H,3
N,4
S,2
IMPORTANT! Your solution should return an array (or list, vector, etc depending on language) of strings. Ie., the first element of the array for the example above should be the string "A,1".
Hint
Reverse the directions of the arrows, then calculate cost.