FastPrepUnique Transitive Dependent Counts

Unique Transitive Dependent Counts

Robinhood logoRobinhood● MediumFULLTIMEPHONE SCREEN
Learn

Problem statement

You are given a list of known node names and directed dependency rows. A row [dependent, dependency] means dependent relies on dependency.

For each name in the original names order, return the number of distinct known nodes that depend on it directly or through one or more intermediate dependencies. Count a reachable node once even when several paths reach it. Ignore a dependency row when either endpoint is absent from names.

The retained known-node graph is a directed acyclic graph.

Function

uniqueDependentCounts(names: String[], dependencies: String[][]) → int[]

Examples

Example 1

names = ["a","b","c","d"]dependencies = [["b","a"],["c","a"],["d","b"],["d","c"]]return = [3,1,1,0]

a reaches b, c, and d; d is counted only once despite two paths.

Example 2

names = ["x","y"]dependencies = [["z","x"],["y","missing"]]return = [0,0]

Both rows are ignored because one endpoint is unknown.

Constraints

  • 1 <= names.length <= 2000.
  • Names are unique, nonempty, and contain no spaces.
  • 0 <= dependencies.length <= 20000.
  • The graph induced by known names is acyclic.

More Robinhood problems

See Robinhood hiring insights
public int[] uniqueDependentCounts(String[] names, String[][] dependencies) {
    // Write your solution here.
}
names["a","b","c","d"]
dependencies[["b","a"],["c","a"],["d","b"],["d","c"]]
expected[3,1,1,0]
Checking account…