Module Rebuild Costs
Airbnb● MediumFULLTIMEOAProblem statement
A codebase is split into modules connected by an acyclic dependency graph. Each string in dependencies is a comma-separated row. The first token names one module, and every later token names a module that it directly depends on.
Changing a module requires rebuilding that module and every module that depends on it, either directly or transitively. The cost of a module is the number of distinct modules rebuilt after changing it.
Return one string "module,cost" for every module, ordered lexicographically by module name.
Function
moduleRebuildCosts(dependencies: String[]) → String[]Examples
Example 1
dependencies = ["A,E,N,S","S,H,N","E,N","H","N"]return = ["A,1","E,2","H,3","N,4","S,2"]Changing N rebuilds N, S, E, and A. Changing A rebuilds only A.
Example 2
dependencies = ["core","api,core","web,api,core"]return = ["api,2","core,3","web,1"]A change to core propagates to both api and web.
Constraints
1 <= dependencies.length <= 10^4.- Every module name is a unique non-empty ASCII identifier containing no comma.
- Every referenced dependency has its own row in
dependencies. - Each direct dependency appears at most once in a row.
- The dependency graph is acyclic.
- The total number of direct dependency edges is at most
2 * 10^5.
Source note: Three original source screenshots show the complete prompt, example, input/output contract, and hint.