Compute decayed power levels in a graph
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Onsite
You are given an unweighted graph representing a network of wires.
- The graph has **N nodes** labeled `0..N-1` and **M edges** (each edge is a bidirectional wire).
- A subset of nodes are **torches**.
- Each torch provides power level **16 at its own node**.
- Power propagates through wires and **decays by 1 per wire traversed** (i.e., by graph distance in number of edges).
- If multiple torches can reach a node, the node receives the **maximum** power among them.
- Power cannot be negative.
For every node `v`, define:
- `dist(v) =` the length (in edges) of the shortest path from `v` to any torch (∞ if unreachable)
- `power(v) = max(0, 16 - dist(v))` (and `power(v)=0` if unreachable)
### Task
Given `N`, the edge list, and the list of torch nodes, compute `power(v)` for all nodes.
### Input (one possible format)
- `N` (number of nodes)
- `edges`: list of pairs `(u, v)`
- `torches`: list of torch node indices
### Output
- Array `power[0..N-1]`.
### Notes / constraints
- Assume `N` can be large (e.g., up to 10^5), so the solution should be near-linear in `N + M`.
- Graph may be disconnected.
Quick Answer: This question evaluates knowledge of graph algorithms and distance-based propagation, testing concepts such as shortest-path distance computation, multi-source reachability, and aggregation of maximum influences with per-edge decay.
You are given an undirected, unweighted graph with N nodes labeled 0 to N-1 and a list of torch nodes. Each torch provides power 16 at its own node. Power travels across edges and decreases by 1 for each edge traversed. If a node can be reached from multiple torches, it keeps the maximum power it can receive. Power cannot be negative. For every node v, compute power(v) = max(0, 16 - shortest_distance_to_any_torch). If a node is unreachable from all torches, its power is 0. Return the power value for every node.
Constraints
- 1 <= n <= 10^5
- 0 <= len(edges) <= 2 * 10^5
- 0 <= u, v < n for every edge (u, v)
- The graph is undirected and unweighted
- 0 <= len(torches) <= n, and torch indices are valid node indices
- The graph may be disconnected, and the torch list may contain duplicates
Examples
Input: (6, [(0,1), (1,2), (2,3), (3,4), (4,5)], [0])
Expected Output: [16, 15, 14, 13, 12, 11]
Explanation: Node 0 is a torch with power 16, and each step along the line decreases power by 1.
Input: (8, [(0,1), (1,2), (1,3), (3,4), (4,5), (2,6)], [5, 0])