Real-Time Event Propagation | Dataford Interview Questions

You are given a directed graph of app components. Each node represents a component, and each directed edge u -> v means component v depends on updates from component u. When a component receives a new event, that event must be propagated to all reachable components in dependency order: a component can only process an event after all of its direct prerequisites for that event have been processed.

Implement a function that returns the order in which components process a single event starting from one or more source nodes. If multiple components are ready at the same time, process the component with the smaller node id first. Ignore duplicate events for the same component within the same propagation run.

Constraints

1 <= n <= 10^5
0 <= len(edges) <= 2 * 10^5
0 <= u, v < n
The graph may contain duplicate edges
sources contains at least one node
The graph is guaranteed to be acyclic

Function Signature

def propagate_updates(n, edges, sources):

Your question is Real-Time Event Propagation. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem

Constraints

1 <= n <= 10^5
0 <= len(edges) <= 2 * 10^5
0 <= u, v < n
The graph may contain duplicate edges
sources contains at least one node
The graph is guaranteed to be acyclic

Function Signature

def propagate_updates(n, edges, sources):

Your question is Real-Time Event Propagation. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.