DAG Downstream Nodes
Notion● MediumFULLTIMEONSITE INTERVIEWProblem statement
A directed acyclic graph is encoded by adjacency rows. The first value in each row is a node and the remaining values are its direct downstream nodes.
Each query is either DIRECT node or ALL node. A direct query returns that node's direct downstream nodes. An all query returns every distinct node reachable by one or more edges. Sort every answer lexicographically and format it as [node1,node2]; return [] when the answer is empty.
Return one formatted answer for every query in order.
Function
queryDownstream(adjacency: String[][], queries: String[]) → String[]Examples
Example 1
adjacency = [["A","B","C"],["B","D"],["C","D","E"],["D"],["E"]]queries = ["DIRECT A","ALL A","DIRECT D","ALL C"]return = ["[B,C]","[B,C,D,E]","[]","[D,E]"]A directly reaches B and C. Its transitive result includes those nodes plus D and E once, even though D has two incoming paths.
Constraints
1 <= adjacency.length <= 100000.- Every node has exactly one adjacency row, including nodes with no outgoing edges.
- Node IDs are unique non-empty ASCII strings containing neither a comma nor whitespace.
- The graph has no self-edge, duplicate edge, or directed cycle.
1 <= queries.length <= 100000, and every queried node exists.- The total number of nodes visited across all
ALLqueries is at most300000.