Find shortest path with blocked nodes
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
##### Question
Given an unweighted graph, a start node, an end node, and a block_set of nodes that cannot be traversed, return the length of the shortest path from start to end. Follow-up: discuss edge cases and how you would optimize space for the BFS solution. Follow-up: if nodes in block_set are traversable but incur additional cost, how would you find the fastest path?
Quick Answer: This question evaluates proficiency in graph traversal and shortest-path computation, including handling nodes that are blocked or that incur additional costs. It is commonly asked in the coding and algorithms domain (graph algorithms) to assess both practical implementation skills and conceptual understanding of complexity, edge cases, and trade-offs between unweighted and weighted path models.
You are given an undirected, unweighted graph with n nodes labeled 0..n-1, an edge list, a start node, an end node, and a list blocked of nodes that cannot be traversed. Return the length (number of edges) of the shortest path from start to end that never visits any node in blocked. If start or end is in blocked, or no such path exists, return -1. If start == end and it is not blocked, return 0.
Constraints
- 1 <= n <= 200000
- 0 <= len(edges) <= 200000
- 0 <= start, end < n
- Node labels are integers in [0, n-1]
- Graph is undirected and unweighted
- Nodes in blocked cannot be stepped on; if start or end is blocked, return -1
- Return -1 if no path exists
- Edges may contain duplicates or self-loops; ignore duplicates naturally
Hints
- Use BFS from start while skipping any neighbor that is blocked or already visited.
- Return the level at which you first dequeue end; if start == end and not blocked, the answer is 0.
- For space optimization, consider bidirectional BFS from start and end on the unblocked subgraph.
- If blocked nodes are traversable with extra cost, model entering a blocked node as higher edge weight and use Dijkstra's algorithm.