Dataford
Interview QuestionsInterview GuidesExperiencesMock InterviewsPricing
Get started

Real-Time Event Propagation

Hard
CodingHash TablesQueueArraysAsked 1 times

Problem

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):

You are practicing as a guest. Sign up free to run your code against the sample data. Your draft stays right here.

Sign up freeI have an account
def solve(rows):
    counts = {}
    for row in rows:
        ...
    return result
Sign up to unlock solutions
Toast Mobile Engineer Interview QuestionsToast Interview Questions
Python 3.10