Katkat
Back

Compute dependency load factors in a DAG

RobinhoodSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to model dependencies in a Directed Acyclic Graph (DAG) and calculate the cumulative 'load' contribution of each node, requiring efficient graph traversal techniques like topological sorting or recursion with memoization.

Problem Description

In a distributed computing system, tasks are represented as nodes in a Directed Acyclic Graph (DAG), where an edge from A to B means task B depends on task A. Each task i has an intrinsic load value. The 'Total Load' of a task is defined as its own intrinsic load plus the sum of the total loads of all tasks that directly or indirectly depend on it.

Given a list of tasks and a list of directed edges representing dependencies, calculate the Total Load for every task in the system.

Function Signature

def compute_total_loads(n: int, intrinsic_loads: List[int], dependencies: List[List[int]]) -> List[int]

  • n: Number of tasks (labeled 0 to n-1).
  • intrinsic_loads: A list where intrinsic_loads[i] is the intrinsic load of task i.
  • dependencies: A list of pairs [u, v] meaning v depends on u (i.e., the flow of load is v -> u).

Examples

Example 1

  • n = 3
  • intrinsic_loads = [1, 2, 3]
  • dependencies = [[0, 1], [1, 2]]
  • Output: [6, 5, 3]
  • Explanation: Task 2 depends on 1, 1 depends on 0. Total load of 2 = 3. Total load of 1 = 2 + 3 = 5. Total load of 0 = 1 + 2 + 3 = 6.

Constraints

  • 1 <= n <= 10^4
  • 0 <= len(dependencies) <= 10^5
  • The graph is guaranteed to be a DAG.
  • Intrinsic loads are non-negative integers.

Edge Cases

  • Disconnected components in the graph.
  • Tasks with no dependencies (Total load = Intrinsic load).
  • A task that is a dependency for multiple other tasks.

Hints

Hint 1

Model the dependencies as an adjacency list, but be careful with the direction: since we want to sum the load of dependents, the graph should be represented such that a task points to the tasks that depend on it.

Hint 2

Think of this as a variation of post-order traversal or dynamic programming on a DAG; the total load of a node is its intrinsic value plus the sum of the total loads of all nodes pointing to it.

Hint 3

Using memoization will prevent redundant calculations and ensure the algorithm runs in O(V + E) time, where V is the number of tasks and E is the number of dependencies.

Follow-up questions

  • How would your approach change if the graph contained cycles, and how would you detect them?
  • If the 'Total Load' calculation involved a decay factor (e.g., a dependency's contribution is halved as it gets further away), how would you modify the traversal?
  • How would you optimize the memory footprint if the graph is extremely sparse versus extremely dense?