Quick Overview

Count unique direct and transitive dependents in a DAG, preserving edge direction, ignoring unknown endpoints, and handling shared descendants without double-counting.

Count Unique Dependents in a Referral DAG

Company: Robinhood

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

Given named nodes and a dependency DAG, compute how many unique nodes directly or indirectly depend on each node. An edge `[a,b]` means `a` depends on `b`, so `a` contributes to `b`'s count, not the other way around. Implement `referral_counts(nodes: string[], edges: string[][]) -> int[]`. Return one count per node in the same order as `nodes`; this parallel-array output is a portable representation of the source's name-to-count map. ### Constraints & Assumptions - Between 0 and 2000 unique nonempty node names and at most 10000 edges. Each edge contains exactly two names. - Discard an edge if either endpoint is absent from `nodes`. Excluded nodes must not create paths connecting known nodes. - The remaining graph is a DAG. Duplicate edges may occur and must not multiply reachability counts. - Count distinct reachable dependents, excluding the node itself. Shared descendants reached by multiple paths count once. - Isolated nodes have count zero. Names are case-sensitive. ### Example ```text nodes = ["A","B","C","D","E"] edges = [["B","A"],["C","A"],["D","B"],["D","C"], ["E","ghost"],["ghost","A"]] result = [3,1,1,0,0] ``` `D` contributes only once to A. Ignoring the unknown node does not create an E-to-A relationship. Explain a topological-order approach and why adding child counts is insufficient when dependency paths merge. Compare set or bitset propagation with performing a graph search separately for each node, including time and memory tradeoffs. ```hint Counts alone lose overlap information When two direct dependents share another dependent, you need enough information to union their reachable nodes without counting that shared node twice. ```

Overview: Count unique direct and transitive dependents in a DAG, preserving edge direction, ignoring unknown endpoints, and handling shared descendants without double-counting.

Read the full Robinhood Software Engineer interview experience this question came from

Given named nodes and a dependency DAG, compute how many unique nodes directly or indirectly depend on each node. An edge `[a,b]` means `a` depends on `b`, so `a` contributes to `b`'s count, not the other way around. Implement `referral_counts(nodes: string[], edges: string[][]) -> int[]`. Return one count per node in the same order as `nodes`; this parallel-array output is a portable representation of the source's name-to-count map. ### Constraints & Assumptions - Between 0 and 2000 unique nonempty node names and at most 10000 edges. Each edge contains exactly two names. - Discard an edge if either endpoint is absent from `nodes`. Excluded nodes must not create paths connecting known nodes. - The remaining graph is a DAG. Duplicate edges may occur and must not multiply reachability counts. - Count distinct reachable dependents, excluding the node itself. Shared descendants reached by multiple paths count once. - Isolated nodes have count zero. Names are case-sensitive. ### Example ```text nodes = ["A","B","C","D","E"] edges = [["B","A"],["C","A"],["D","B"],["D","C"], ["E","ghost"],["ghost","A"]] result = [3,1,1,0,0] ``` `D` contributes only once to A. Ignoring the unknown node does not create an E-to-A relationship. Explain a topological-order approach and why adding child counts is insufficient when dependency paths merge. Compare set or bitset propagation with performing a graph search separately for each node, including time and memory tradeoffs. ```hint Counts alone lose overlap information When two direct dependents share another dependent, you need enough information to union their reachable nodes without counting that shared node twice. ```

Constraints

  • 0 through 2000 unique nonempty case-sensitive node names and at most 10000 edges.
  • Discard edges with any unknown endpoint; the remaining graph is a DAG.
  • Edge [a,b] means a depends on b; count distinct dependents and exclude the node itself.
  • Duplicate paths and edges do not multiply counts; output follows nodes order.

Examples

Input: (['A', 'B', 'C', 'D', 'E'], [['B', 'A'], ['C', 'A'], ['D', 'B'], ['D', 'C'], ['E', 'ghost'], ['ghost', 'A']])

Expected Output: [3, 1, 1, 0, 0]

Explanation: The diamond shares D once; unknown endpoints cannot connect E to A.

Input: (['B', 'A'], [['B', 'A']])

Expected Output: [0, 1]

Explanation: B depends on A, so only A gains a dependent; output retains the input node order.

Loading coding console...

Show the approach

Approach

Map known names to their input-order indices and discard edges with either unknown endpoint before building paths. Keep each valid edge once, directed from dependent a to dependency b. Initialize each node bitset with itself. Process this directed DAG in topological order: nodes with no incoming dependents start ready, and a node becomes ready only after every direct dependent has propagated to it. For each a-to-b edge, union the completed bitset of a into b. By topological induction, a bitset contains exactly the node itself and every node depending on it through one or more paths. Union is idempotent, so shared descendants and duplicate paths never inflate counts. Subtract one from each final population count and return counts in the original node order. Adding child counts alone loses overlap information and overcounts diamonds. With V nodes, E input edges, and machine-word width w, packed propagation takes O(V+E+(V+E)ceil(V/w)) expected time including name lookup and deduplication, and O(V+E+V ceil(V/w)) words of space; string hashing also costs the characters inspected. Explicit sets offer the same union semantics with up to O(EV+V^2) element work and O(V^2) stored entries, but may help for sparse reachability. An independent graph search from each node on reversed adjacency avoids storing all reachability sets and uses O(V+E) working space, while taking O(V(V+E)) time. Python uses packed integer bitsets, Java uses BitSet, and the other references use fixed-width packed words.

Time complexity:
O(V+E+(V+E) ceil(V/w)) expected word operations, plus name hashing.
Space complexity:
O(V+E+V ceil(V/w)) words, plus node-name storage.