TopCoder problem "FunctionDependency" used in SRM 276 (Division II Level Three)

Problem Statement


You are developing a database platform that supports, among other things, user defined functions. User-defined functions may call internal functions, other user-defined functions, or both. A user-defined function, FuncA, is said to be dependent on another function, FuncB, if it calls FuncB.

You have been tasked with writing a module that will "script" (list out the code for) all of the functions in a given database. However, because of dependency issues, they must be scripted in a specific order that meets the following criteria:

  • A function cannot be scripted until all of its dependent functions have already been scripted.
  • Whenever more than one function could be scripted (subject to the first requirement), the one whose name occurs first lexicographically will be scripted first.

You are given a String[] funcs, each element of which is the name of a function in the database. You are also given a String[] depends, a list describing the dependency of each function. Each element of depends is a space-delimited list of integers. Each element of depends corresponds to the element of funcs with the same index. Each number represented in each element of depends refers to the 0-based index of another function.

For instance, suppose a database has two functions, A and B, each of which is dependent on a third function, C. The input might then be given by:

{"B", "C", "A"}
{"1", "", "1"}

Now, since functions A and B both depend upon C, we have to script C first. After that, either A or B could be scripted, since C has already been scripted. We use the second rule to determine that we should script A first. Our return is thus:

{"C", "A", "B"}

You are to return a String[] containing the names of the functions in the order in which they should be scripted.



Parameters:String[], String[]
Method signature:String[] scriptingOrder(String[] funcs, String[] depends)
(be sure your method is public)


-funcs will contain between 1 and 50 elements, inclusive.
-depends will contain the same number of elements as funcs.
-Each element of funcs will contain between 1 and 50 upper case ('A'-'Z') character, inclusive.
-Each element of depends will be a space-delimited list of integers, with no leading zeroes.
-Each integer represented in depends will be between 0 and n-1, inclusive, where n is the number of elements in funcs.
-There will be no circular dependencies.


{"B", "C", "A"}
{"1", "", "1"}
Returns: {"C", "A", "B" }
The example from the problem statement.
{"B", "C", "A"}
{"1", "", "0"}
Returns: {"C", "B", "A" }
{"K", "A", "B", "C", "D", "E", "F", "G", "H", "I"}
{"", "", "1 1", "2", "3", "4", "5", "6", "7", "8"}
Returns: {"A", "B", "C", "D", "E", "F", "G", "H", "I", "K" }
Careful! It is permissible for the same dependency to be listed twice.

Problem url:

Problem stats url:




PabloGilberto , brett1479 , Olexiy

Problem categories: