Order Sources by Their Dependencies
Retool● MediumFULLTIMEPHONE SCREENProblem statement
You receive unique source names and dependency pairs. A pair [source, prerequisite] means that prerequisite must be processed before source.
Return an ordering containing every source exactly once and satisfying every dependency. When several sources are currently available, choose the lexicographically smallest name. This produces a deterministic smallest valid ordering.
If any cycle prevents completing all sources, return the one-element array ["IMPOSSIBLE"]. With no sources, return an empty array.
Function
sourceOrder(sources: String[], dependencies: String[][]) → String[]Examples
Example 1
sources = ["app","lib","core","docs"]dependencies = [["app","lib"],["lib","core"]]return = ["core","docs","lib","app"]Every prerequisite must appear first. Choose the lexicographically smallest currently available source, or report a cycle.
Example 2
sources = ["a","b"]dependencies = [["a","b"],["b","a"]]return = ["IMPOSSIBLE"]Every prerequisite must appear first. Choose the lexicographically smallest currently available source, or report a cycle.
Example 3
sources = []dependencies = []return = []Every prerequisite must appear first. Choose the lexicographically smallest currently available source, or report a cycle.
Constraints
0 <= sources.length <= 1000.- Each unique source name has
1to20lowercase English letters. 0 <= dependencies.length <= 5000.- Every pair references supplied names, and dependency pairs are unique. Self-dependencies are allowed and form a cycle.