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
Solution
from collections import deque
from typing import List
def shortest_blocked_path(n: int, edges: List[List[int]], start: int, end: int, blocked: List[int]) -> int:
blocked_set = set(blocked)
if start in blocked_set or end in blocked_set:
return -1
if start == end:
return 0
adj = [[] for _ in range(n)]
for e in edges:
if len(e) != 2:
continue
u, v = e
if 0 <= u < n and 0 <= v < n:
adj[u].append(v)
adj[v].append(u)
visited = [False] * n
q = deque([start])
visited[start] = True
dist = 0
while q:
size = len(q)
for _ in range(size):
u = q.popleft()
if u == end:
return dist
for w in adj[u]:
if not visited[w] and w not in blocked_set:
visited[w] = True
q.append(w)
dist += 1
return -1
Explanation
Build an adjacency list and run breadth-first search (BFS) from start. Maintain a visited array and a set of blocked nodes. If start or end is blocked, return -1 immediately. BFS explores the graph in increasing distance layers; when end is first reached, the current layer number is the shortest path length. Skip pushing any neighbor that is blocked or already visited. If the queue empties without reaching end, return -1. Space/time can be improved in practice using bidirectional BFS from both start and end over the unblocked nodes. If blocked nodes were traversable with extra cost, convert the problem to a weighted shortest path and use Dijkstra's algorithm.
Time complexity: O(n + m), where m = len(edges). Space complexity: O(n + m).
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.