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.