Find Affected Services After Shutdown
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
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:
```text
dependencies = {
"A": ["B", "C"],
"B": ["D"],
"C": ["E"],
"D": [],
"E": []
}
stopped = {"A"}
```
Expected output:
```text
{"A", "B", "C", "D", "E"}
```
Quick Answer: 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.
You are given a directed acyclic graph of service dependencies. Each key in `dependencies` is a service, and its value is a list of services that directly depend on it. If a service is shut down, then every service that depends on it becomes affected. This effect continues transitively through the graph.
Given a map `dependencies` and a set `stopped` containing services intentionally taken offline, return the set of all affected services, including the initially stopped services.
If a service appears in a dependency list but not as a key in the map, treat it as a leaf service with no further dependents.
Constraints
- 0 <= number of services <= 100000
- 0 <= total dependency relationships <= 200000
- Service names are strings
- The dependency graph has no cycles
Examples
Input: ({'A': ['B', 'C'], 'B': ['D'], 'C': ['E'], 'D': [], 'E': []}, {'A'})
Expected Output: {'A', 'B', 'C', 'D', 'E'}
Explanation: Stopping A directly affects B and C, which then affect D and E.
Input: ({'Auth': ['Checkout', 'Profile'], 'Checkout': ['Payments'], 'Profile': ['Settings'], 'Payments': ['Ledger'], 'Settings': ['Ledger'], 'Ledger': []}, {'Auth', 'Settings'})
Expected Output: {'Auth', 'Checkout', 'Profile', 'Payments', 'Settings', 'Ledger'}