Compute shortest paths with blocked nodes
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given a graph with nodes and edges and a designated source node s, compute the shortest distance from s to every other node. Some nodes are inaccessible (blocked) and cannot be traversed or reached; treat them as removed from the graph. Return a distance for each node where unreachable nodes (including blocked ones) are -1. Describe your algorithm, data structures, and time/space complexity, and note any differences for directed vs. undirected graphs.
Quick Answer: This question evaluates proficiency with graph algorithms, shortest-path and reachability concepts when nodes are removed or blocked, and the ability to analyze time and space complexity across directed and undirected graphs.
Given n nodes labeled 0..n-1, edges, a source, and blocked nodes, return shortest unweighted distances from the source. Blocked and unreachable nodes must be -1. Set directed=True to treat edges as directed.
Constraints
- Nodes are labeled 0 through n-1
- Edges are unweighted
Examples
Input: (5, [[0, 1], [1, 2], [0, 3], [3, 4]], 0, [3], False)
Expected Output: [0, 1, 2, -1, -1]
Input: (4, [[0, 1], [1, 2], [2, 3]], 0, [], True)
Expected Output: [0, 1, 2, 3]
Hints
- Treat blocked nodes as removed before BFS.
- For directed graphs, only add the given edge direction.