How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Amazon.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Amazon during technical interviews.

Find Affected Services After Shutdown | Amazon Coding Question

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'}

Explanation: Auth affects Checkout and Profile, which lead to Payments, Settings, and Ledger. Settings is also initially stopped.

Input: ({'A': ['B'], 'B': []}, set())

Expected Output: set()

Explanation: If no services are stopped, then no services are affected.

Input: ({'A': ['B', 'B'], 'B': ['C']}, {'A', 'X'})

Expected Output: {'A', 'B', 'C', 'X'}

Explanation: A affects B and then C. X is included even though it does not appear in the map. The duplicate edge to B should not change the result.

Hints

Model the services as a directed graph and start a traversal from every service in `stopped`.
Use a visited set so that shared downstream services are only processed once.

Quick Overview

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.