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 medium 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 dependency load factors in a DAG | Robinhood Coding Question

Compute dependency load factors in a DAG

Company: Robinhood

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

## System Dependency Load Factor You are given: - `programs`: a list of **unique** program names (strings) - `prerequisites`: a list of pairs `[a, b]` meaning **program `a` depends on program `b`** Considering only programs that appear in `programs`, these dependencies form a **directed acyclic graph (DAG)**. ### Load Factor Define the **Load Factor** of a program `x` as the **number of unique programs** in `programs` that **directly or indirectly depend on `x`**. - A program does **not** count as depending on itself. - “Indirectly” means there exists a dependency chain (path) `p -> ... -> x` following edges `a -> b` (depends-on direction). ### Data-cleaning rule The input may contain prerequisite pairs involving programs not present in `programs`. - If either `a` or `b` is **not** in `programs`, **ignore that pair entirely** (do not add either node or edge). ### Task Return a map/dictionary from each program name in `programs` to its Load Factor. ### Example **Input** - `programs = ["A", "B", "C", "D"]` - `prerequisites = [["A","B"],["B","C"],["A","C"],["D","C"],["E","A"]]` (Notice `["E","A"]` is ignored because `E` is not in `programs`.) **Output** - `{ "A": 0, "B": 1, "C": 3, "D": 0 }` Explanation (informal): `C` is depended on by `A`, `B`, and `D` → `3`; `B` is depended on by `A` → `1`. ### Notes - You may return the map in any key order. - Assume the remaining graph (after ignoring invalid pairs) is a DAG.

Quick Answer: This question evaluates understanding of graph theory and algorithms, specifically reachability and dependency analysis in a directed acyclic graph, along with attention to input validation and set-based reasoning.

You are given a list of unique program names and a list of prerequisite pairs [a, b], meaning program a depends on program b. Considering only programs that appear in the programs list, these dependencies form a directed acyclic graph (DAG). The Load Factor of a program x is the number of unique programs in programs that directly or indirectly depend on x. A program does not count as depending on itself. If either name in a prerequisite pair is not present in programs, ignore that pair entirely. Return a dictionary mapping every program in programs to its Load Factor. You may return the dictionary in any key order.

Constraints

0 <= len(programs) <= 500
0 <= len(prerequisites) <= 5000
programs contains unique strings
After ignoring invalid pairs, the remaining dependency graph is a DAG
Duplicate prerequisite pairs may appear and should not change the result

Examples

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

Expected Output: {'A': 0, 'B': 1, 'C': 3, 'D': 0}

Explanation: ['E', 'A'] is ignored because E is not in programs. C is depended on by A, B, and D; B is depended on by A; A and D are not depended on by any listed program.

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

Expected Output: {}

Explanation: There are no valid programs, so the result is an empty dictionary.

Input: (['X'], [['X', 'Y'], ['Y', 'X'], ['Z', 'W']])

Expected Output: {'X': 0}

Explanation: All prerequisite pairs are ignored because at least one endpoint is not in programs. X has no dependents.

Input: (['P', 'Q', 'R', 'S', 'T'], [['P', 'Q'], ['P', 'R'], ['Q', 'S'], ['R', 'S'], ['T', 'S'], ['P', 'Q']])

Expected Output: {'P': 0, 'Q': 1, 'R': 1, 'S': 4, 'T': 0}

Explanation: The duplicate pair ['P', 'Q'] does not change the graph. S is depended on by P, Q, R, and T. Q and R are each depended on only by P.

Input: (['alpha', 'beta', 'gamma'], [])

Expected Output: {'alpha': 0, 'beta': 0, 'gamma': 0}

Explanation: With no dependencies, every program has Load Factor 0.

Hints

Ignore invalid pairs first. For every valid edge a -> b, any program that can reach a can also reach b.
Since the graph is a DAG, process nodes in topological order and propagate ancestor information forward.

Quick Overview

This question evaluates understanding of graph theory and algorithms, specifically reachability and dependency analysis in a directed acyclic graph, along with attention to input validation and set-based reasoning.