Katkat
Back

Find shortest path with blocked nodes

GoogleSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

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.

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?