Compute graph distance and impacted services

## Part A — Graph shortest distance (BFS) You are given an interface representing a node in an unweighted graph: ```java interface Candidate { String id(); List<Candidate> getConnections(); } ``` Implement: ```java int getDistance(Candidate c1, Candidate c2) ``` where `getDistance` returns the length of the shortest path (minimum number of edges) between `c1` and `c2` using the `getConnections()` adjacency list. ### Requirements - Treat connections as edges in an unweighted graph. - Return `0` if `c1` and `c2` are the same node. - Return `-1` if `c2` is unreachable from `c1`. - Avoid infinite loops in the presence of cycles. ### Follow-up (discussion only) If this needs to run in production at large scale (very large graph, frequent queries), discuss how you would optimize and/or redesign the solution (data structures, precomputation, caching, storage, distributed concerns). --- ## Part B — Find services impacted by deleted paths + dependency propagation You are given a JSON-like config mapping service name → I/O paths: ```json { "svcA": {"read_from": "/path123", "write_to": "/path456"}, "svcB": {"read_from": "/path456", "write_to": "/path789"} } ``` You are also given a list of deleted paths: ```text deleted_list = ["/path123", "/path12", ...] ``` ### Task 1 — Directly impacted services Return all services that are impacted by the deletions. A service is **directly impacted** if either its `read_from` or `write_to` is affected by `deleted_list`. ### Task 2 — Directory-tree (subtree) impact rule In addition to exact matches, apply this rule: - If a service’s `read_from` or `write_to` path shares a **common parent directory** with a deleted path, treat it as impacted. - Model paths as a file tree and include **only the affected subtree(s)**; do **not** include sibling subtrees that share a higher-level ancestor. (You should clearly define what you consider the “affected subtree root” and implement consistently, e.g., based on nearest common parent directories / minimal affected roots.) ### Task 3 — Propagate impact through service dependencies (ordered output) Services form a dependency chain via produced/consumed paths: - If service `X.write_to == Y.read_from`, then `Y` depends on `X` (data flows from `X` → `Y`). - If an upstream service is impacted, all downstream dependents are impacted transitively. For each entry in `deleted_list`, output the impacted services **in dependency order** (from upstream producers to downstream consumers). If multiple services are impacted independently, output them in a valid topological order. ### Notes - You may assume `read_from` and `write_to` are single paths per service. - Paths are UNIX-like strings with `/` separators. - The dependency graph may be a chain or a DAG; handle general cases unless otherwise stated.