Google·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

May 2026

Summary

Google SWE interview with a graph problem that looked like a BFS warmup but had enough wrinkles to slow me down. Not a bad experience, just one of those rounds where you feel like you're one step behind the whole time.

Questions Asked (1)

You have a graph where nodes are connected by edges. Some nodes are torches that emit power at level 16, and power drops by 1 for each edge traversed. A node's final power level is the maximum it receives from any torch via any path, and anything below 0 means unpowered. Compute the final power level at every node.

Algorithms & Data Structures

Author's notes

I went straight to single-source BFS and the interviewer just kind of waited.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as a multi-source shortest path where each torch is a source with initial power 16, and edge weights are 1. Use a modified Dijkstra or BFS with a priority queue to propagate the maximum power to each node, updating only when a higher power is found.

Pro tip: Clarify edge cases upfront: disconnected components, multiple torches on the same node, and nodes that remain unpowered. Also, mention that if all edge weights are 1, a BFS with a max-heap can be used, but Dijkstra is more general.

1. Understand the problem and constraints

Restate the problem: each torch starts with power 16, power decreases by 1 per edge, and each node takes the maximum power from any path. Ask about graph size, edge weights, and whether power can be negative.

2. Choose the right algorithm

Recognize this as a multi-source shortest path with maximization. Use Dijkstra's algorithm with a max-heap, initializing all torch nodes with power 16 and others with -1 (unpowered).

3. Implement the propagation

Push all torches into a priority queue with their power. While the queue is not empty, pop the node with the highest power; for each neighbor, compute new power = current power - 1. If new power > existing power, update and push.

4. Handle edge cases and output

After propagation, any node with power < 0 is unpowered (set to -1 or 0 as required). Return the array of final power levels.

5. Analyze complexity and optimize

Time complexity is O((V+E) log V) with a binary heap. Mention that if all edges have weight 1, a BFS with a deque can achieve O(V+E) by processing in decreasing power order.

Key Points to Mention

Multi-source shortest path with maximization objective
Dijkstra's algorithm with a max-heap (or priority queue with negative values)
Initialization: torches at 16, others at -1 (or -infinity)
Relaxation condition: new_power = current_power - 1; update if greater than existing
Handling unpowered nodes: final power < 0 means unpowered
Time and space complexity: O((V+E) log V) time, O(V+E) space

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.