How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a easy difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Google.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Google during technical interviews.

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])

Expected Output: [16, 15, 14, 14, 15, 16, 13, 0]

Explanation: Each node takes the best power from torch 0 or torch 5. Node 7 is isolated, so it gets 0.

Input: (5, [(0,1), (2,3)], [])

Expected Output: [0, 0, 0, 0, 0]

Explanation: With no torches, every node is unreachable from any power source.

Input: (18, [(0,1), (1,2), (2,3), (3,4), (4,5), (5,6), (6,7), (7,8), (8,9), (9,10), (10,11), (11,12), (12,13), (13,14), (14,15), (15,16), (16,17)], [0])

Expected Output: [16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 0]

Explanation: Nodes at distances 0 through 15 have powers 16 through 1. Nodes at distance 16 or more have power 0.

Input: (4, [], [2, 2])

Expected Output: [0, 0, 16, 0]

Explanation: Duplicate torch entries do not change the result. Only node 2 has power because there are no edges.

Hints

In an unweighted graph, the shortest distance to the nearest torch can be found with a multi-source BFS: start BFS from all torch nodes at once.
Since power becomes 0 at distance 16 or more, you only need to expand BFS up to distance 15.

Quick Overview

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.