Find Affected Services After Shutdown

Q: Find Affected Services After Shutdown

This question evaluates understanding of graph traversal, reachability, and dependency analysis by measuring the ability to identify transitive impacts across a directed acyclic service dependency graph.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

You are given a set of services and their dependency relationships. The input is a hash map where each key is a service name, and the value is a list of services that directly depend on it.

For example, if dependencies["Auth"] = ["Checkout", "Profile"], then shutting down Auth will directly affect Checkout and Profile.

Given:

dependencies: Map<String, List<String>>
stopped: Set<String> representing the services that are intentionally taken offline

Return the set of all services that will be affected by the shutdowns, either directly or transitively. Include the initially stopped services in the result.

Assumptions:

The dependency graph is valid.
There are no cycles.
You may choose any reasonable function signature.
The goal is to design an efficient algorithm.

Example:

dependencies = {
  "A": ["B", "C"],
  "B": ["D"],
  "C": ["E"],
  "D": [],
  "E": []
}
stopped = {"A"}

Expected output:

{"A", "B", "C", "D", "E"}

Find Affected Services After Shutdown

Quick Overview

Comments (0)