Design Service Dependency Impact Analyzer
You are given a collection of microservices and their directed dependencies. Analyze the system to determine which services are affected when one service fails, the maximum depth of that impact, and whether the dependency graph contains a cycle.
Dependency Format
Each dependency is represented by a comma-separated string:
"service,dependency"
service is the service that requires another service.dependency is the service that it requires.- For example,
"order,payment" means that order depends on payment.
- If
payment fails, order is directly impacted.
- Dependency edges point from a service to the service it requires. Impact analysis traverses these relationships in the reverse direction, from a failed dependency to services that depend on it.
Impact Rules
- The failed service itself is not included in the list of impacted services.
- Even if a cycle leads back to
failedService, the failed service itself must not appear in the result.
- A service is directly impacted if it depends on the failed service.
- A service is indirectly impacted if it depends on another impacted service.
- A directly impacted service has impact depth
1.
- A service impacted through one intermediate service has impact depth
2, and so on.
- If multiple paths reach the same service, use its smallest possible impact depth.
- Each impacted service must appear only once.
Ordering
Return impacted services in increasing order of impact depth. Services at the same depth must be ordered lexicographically.
Each returned entry must use the format:
"serviceName,depth"
Method Signatures
Get Impacted Services
List<String> getImpactedServices(List<String> services, List<String> dependencies, String failedService)
services contains all unique service names.dependencies contains directed dependency relationships in "service,dependency" format.failedService is the service that has failed.- The method returns impacted services in
"serviceName,depth" format.
- The result is sorted first by increasing depth and then lexicographically by service name.
- If no other service is impacted, return an empty list.
Get Impact Depth
int getImpactDepth(List<String> services, List<String> dependencies, String failedService)
- The method returns the greatest minimum depth among all services impacted by
failedService.
- If no other service is impacted, return
0.
- Cycles must not cause repeated traversal or an infinite loop.
Detect Cyclic Dependencies
boolean hasCyclicDependency(List<String> services, List<String> dependencies)
- The method returns
true if the directed dependency graph contains at least one cycle.
- The method returns
false when the dependency graph is acyclic.
- Cycle detection must examine the complete graph, including disconnected groups of services.
Constraints
1 ≤ services.size() ≤ 100,0000 ≤ dependencies.size() ≤ 200,0001 ≤ services.get(i).length() ≤ 100- Every service name is unique and contains only letters, digits, hyphens, or underscores.
failedService is present in services.- Each dependency contains exactly two valid service names separated by one comma.
- A dependency may not contain the same service on both sides.
- Duplicate dependency entries may appear and must be treated as one dependency.
- No parameter contains a null value.
Examples
Example 1: Multi-Level Impact
services = ["auth", "catalog", "checkout", "notification", "order", "payment"]
dependencies = ["checkout,catalog", "checkout,auth", "order,checkout", "order,payment", "notification,order"]
getImpactedServices(services = services, dependencies = dependencies, failedService = "catalog")
Output: ["checkout,1", "order,2", "notification,3"]
getImpactDepth(services = services, dependencies = dependencies, failedService = "catalog")
Output: 3
hasCyclicDependency(services = services, dependencies = dependencies)
Output: false
checkout directly depends on catalog. The failure then reaches order and finally notification.
Example 2: Multiple Services at the Same Depth
services = ["analytics", "billing", "email", "gateway", "reporting", "shipping"]
dependencies = ["billing,gateway", "shipping,gateway", "email,billing", "analytics,billing", "reporting,shipping"]
getImpactedServices(services = services, dependencies = dependencies, failedService = "gateway")
Output: ["billing,1", "shipping,1", "analytics,2", "email,2", "reporting,2"]
getImpactDepth(services = services, dependencies = dependencies, failedService = "gateway")
Output: 2
Services with the same impact depth are returned in lexicographical order.
Example 3: Cyclic Dependency
services = ["inventory", "pricing", "promotion", "search"]
dependencies = ["pricing,inventory", "promotion,pricing", "inventory,promotion", "search,inventory"]
hasCyclicDependency(services = services, dependencies = dependencies)
Output: true
inventory, pricing, and promotion form a directed dependency cycle.
Example 4: No Impacted Service
services = ["audit", "profile", "storage"]
dependencies = ["profile,storage"]
getImpactedServices(services = services, dependencies = dependencies, failedService = "audit")
Output: []
getImpactDepth(services = services, dependencies = dependencies, failedService = "audit")
Output: 0
No service depends directly or indirectly on audit.