Find minimum-latency path across dependent services
Company: Snapchat
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
You are given a set of services and directed dependencies between them. Each dependency edge represents a call from one service to another with a known latency.
- Services are labeled `0..N-1`.
- You are given a list of directed edges `(u, v, latency)` meaning service `u` can call service `v` and that hop adds `latency` milliseconds.
- Given a `start` service and a `target` service, compute the **minimum total latency** along any valid call chain from `start` to `target`.
If there is no route, return `-1`.
### Input
- `N`: number of services
- `edges`: list of `(u, v, w)` with `w > 0`
- `start`, `target`
### Output
- Integer minimum total latency (sum of edge weights), or `-1` if unreachable.
### Notes
- The dependency graph may contain cycles.
- Multiple edges between the same pair may exist; take the best one if helpful.
Quick Answer: This question evaluates understanding of graph algorithms and shortest-path computation on weighted directed graphs, including handling cycles, multiple edges, and reachability in service dependency models.
Given a directed weighted service graph, return the minimum total latency from start to target or -1 if unreachable.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: (4, [(0,1,5),(0,2,2),(2,1,1),(1,3,3),(2,3,10)], 0, 3)
Expected Output: 6
Explanation: Shortest path uses 0-2-1-3.
Input: (3, [(0,1,1)], 1, 2)
Expected Output: -1
Explanation: Unreachable target.
Input: (1, [], 0, 0)
Expected Output: 0
Explanation: Start is target.
Hints
- Pick a representation that makes the requested operation direct.
- Handle empty inputs and boundary cases first.