How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a easy difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Robinhood.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Robinhood during technical interviews.

Compute trigger counts in a DAG | Robinhood Coding Question

Compute trigger counts in a DAG

Company: Robinhood

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Technical Screen

You are given a **directed acyclic graph (DAG)** that represents trigger dependencies between tasks. - Each node represents a task. - There is exactly one **entry node**. - When a node is **triggered** once, it immediately triggers **each of its outgoing neighbors once**. - A node may have multiple incoming edges; its total trigger count is the **sum of triggers from all its parents**. - The entry node is triggered exactly **once** initially. Your job is to compute how many times **each node** is triggered. ### Input - A list of directed edges `edges`, where each edge is a pair `(u, v)` meaning there is an edge `u -> v`. - A designated `entry` node ID. - You may assume: - The graph is acyclic. - All nodes that appear in `edges` are valid nodes. - Node IDs can be strings or integers (you can pick a representation and document it). Example: - Nodes: `A, B, C, D, E, F` - Edges: - `A -> B` - `B -> C` - `B -> D` - `C -> D` - `D -> E` - `D -> F` - `E -> F` - Entry node: `A` Trigger propagation: - `A` is triggered once (given). - `B` is triggered once (from `A`). - `C` is triggered once (from `B`). - `D` is triggered twice (once from `B`, once from `C`). - `E` is triggered twice (both from `D`). - `F` is triggered four times (twice from `D`, twice from `E`). So the result is something equivalent to: ```text A: 1 B: 1 C: 1 D: 2 E: 2 F: 4 ``` ### Task Implement a function **in Python** with a signature such as: ```python def count_triggers(edges, entry): """Return a mapping from node to its trigger count.""" ``` The function should: - Validate that all reachable nodes from `entry` are handled. - Run efficiently for graphs with up to around 10^5 nodes and 10^5 edges. You may assume there are **no cycles** in the input graph.

Quick Answer: This question evaluates understanding of directed acyclic graphs, graph traversal and accumulation of values across dependency edges, as well as algorithmic efficiency for handling large sparse graphs.

You are given a directed acyclic graph (DAG) of task dependencies. Each directed edge (u, v) means that whenever task u is triggered once, it immediately triggers task v once. The entry node is triggered exactly once at the start. A node may have multiple parents, so its total trigger count is the sum of triggers it receives from all of its reachable parents. Return a mapping from each node reachable from the entry node (including the entry itself) to the total number of times it is triggered. Node IDs may be integers or strings. Nodes that are not reachable from the entry node should not appear in the returned mapping.

Constraints

0 <= len(edges) <= 10^5
The graph is acyclic
Node IDs are strings or integers
Only nodes reachable from entry should be included in the result
The solution should run in O(V + E) time, where V is the number of nodes and E is the number of edges

Examples

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

Expected Output: {'A': 1, 'B': 1, 'C': 1, 'D': 2, 'E': 2, 'F': 4}

Explanation: A starts with 1. B gets 1 from A. C gets 1 from B. D gets 1 from B and 1 from C, so 2. E gets 2 from D. F gets 2 from D and 2 from E, so 4.

Input: ([], 'X')

Expected Output: {'X': 1}

Explanation: With no edges, only the entry node is triggered once.

Input: ([(1,2),(1,3),(2,4),(3,4)], 1)

Expected Output: {1: 1, 2: 1, 3: 1, 4: 2}

Explanation: Node 4 is reached through two distinct parent triggers: one from 2 and one from 3.

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

Expected Output: {'A': 1, 'B': 1, 'C': 1}

Explanation: X is unreachable from A, so it never triggers B. Only the reachable path A -> B -> C contributes.

Input: ([('s','a'),('a','b'),('x','y')], 's')

Expected Output: {'s': 1, 'a': 1, 'b': 1}

Explanation: The component x -> y is unreachable from s, so it is ignored.

Input: ([(0,1),(0,2),(1,3),(2,3),(1,4),(3,4),(4,5)], 0)

Expected Output: {0: 1, 1: 1, 2: 1, 3: 2, 4: 3, 5: 3}

Explanation: Node 3 gets one trigger from 1 and one from 2. Node 4 gets one directly from 1 plus two from 3, for a total of 3. Node 5 then gets 3.

Hints

The trigger count of a node is the sum of the trigger counts of its parents. In a DAG, this is equivalent to counting paths from the entry node.
Process only the reachable part of the graph in topological order so every parent contributes before its child is finalized.

Quick Overview

This question evaluates understanding of directed acyclic graphs, graph traversal and accumulation of values across dependency edges, as well as algorithmic efficiency for handling large sparse graphs.