Service Dependency Shortest Latency Path

Given services and pairwise service latencies, return the lowest-latency path from a start service to a destination service. Requirements Implement shortest path over a service dependency graph. Input shape can be normalized as: edges = [(from_service, to_service, latency_ms), ...] start = "A" target = "Z" You should: Build an adjacency list from service latency records. Clarify whether edges are directed dependencies or bidirectional communication links. Return the minimum total latency from start to target; if asked, also return the path. Handle unreachable targets. Assume latencies are non-negative unless the interviewer says otherwise. Notes For non-negative latencies, Dijkstra is the expected solution. Keep a min-heap of (distance, service), skip stale heap entries, and store a parent map if the full path is required. If all latencies are equal, BFS is enough; if negative edges appear, Dijkstra is no longer valid and you should discuss Bellman-Ford. The service framing often invites operational follow-ups: latency can be p50 or p99, edges can change over time, and a path with low average latency may be unreliable. Keep the coding answer simple first, then discuss how production routing would include health, timeouts, and circuit breakers. Preparation Write Dijkstra with path reconstruction from memory. Add tests for one edge, multiple competing paths, cycles, duplicate edges, and unreachable target. Practice explaining why the heap can contain stale distances and how the dist map handles them.