Katkat
Back

Compute graph distance and impacted services

LinkedInSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to model a directed dependency graph and perform reachability analysis to identify all downstream services affected by a change in a root service.

Problem Statement

Imagine you are building a tool to manage microservice dependencies. You are given a list of service dependencies as a list of pairs (u, v), representing that service u depends on service v (i.e., if v changes, u might be impacted).

Your task is to write a function that, given the list of dependencies and a specific 'root' service that has been updated, returns a list of all services impacted by this update. A service is impacted if it directly or indirectly depends on the root service.

Function Signature

def get_impacted_services(dependencies, root_service):
    # dependencies: List[Tuple[str, str]]
    # root_service: str
    # return: List[str]

Constraints

  • The graph can contain cycles (e.g., circular dependencies).
  • The number of services and dependencies will not exceed 10,000.
  • Return the list of impacted services in any order, excluding the root service itself.

Examples

Example 1: Input: dependencies = [("A", "B"), ("B", "C")], root_service = "C" Output: ["A", "B"] Explanation: C is the base. B depends on C, and A depends on B. Both are impacted.

Example 2: Input: dependencies = [("A", "B"), ("B", "A"), ("C", "B")], root_service = "A" Output: ["B", "C"] Explanation: A and B are in a cycle. C depends on B. All are reachable from A.

Edge Cases

  • The root service does not exist in the dependency list.
  • The graph is disconnected.
  • The graph contains self-loops (e.g., ("A", "A")).

Hints

Hint 1

Represent the dependencies as an adjacency list where each node points to the services that depend on it.

Hint 2

Since we want to find all nodes reachable from the root, perform a traversal like Breadth-First Search (BFS) or Depth-First Search (DFS) starting from the root.

Hint 3

Use a set to keep track of visited nodes to prevent infinite loops when encountering cycles in the dependency graph.

Follow-up questions

  • How would you modify your solution to return the services in the order of their 'distance' from the root (i.e., direct dependencies first, then indirect)?
  • What if you were asked to detect if a circular dependency exists in the entire graph, regardless of the root service?
  • How would your approach change if you had to perform this query millions of times per day across a massive, static dependency graph?