Compute graph distance and impacted services

Part A — Graph shortest distance (BFS)

You are given an interface representing a node in an unweighted graph:

interface Candidate {
  String id();
  List<Candidate> getConnections();
}

Implement:

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:

{
  "svcA": {"read_from": "/path123", "write_to": "/path456"},
  "svcB": {"read_from": "/path456", "write_to": "/path789"}
}

You are also given a list of deleted paths:

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.