Compute shortest delivery route with dangerous stops

Q: Compute shortest delivery route with dangerous stops

This question evaluates understanding of graph traversal and shortest-path techniques under constraints, including avoidance of forbidden nodes, multi-criteria optimization (minimizing dangerous-node visits then steps), and reasoning about augmented state and visited-structure design.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Q: What difficulty level is this interview question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Google.

Q: What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Google during technical interviews.

Question

Delivery Route Planning With Dangerous Stops

You are given delivery stops (nodes) and a set of routes. Each route is a list of stops, and you can travel between adjacent stops in the same route (treat travel as an unweighted edge).

Input

N : number of stops labeled 0..N-1 .
routes : a list of routes, where each route is a list like [a, b, c, ...] meaning edges (a,b) , (b,c) , ...
source : starting stop.
target : destination stop.
dangerous : a set of stops considered dangerous.

Part 1

Find the minimum number of steps from source to target without visiting any dangerous stop.

If source or target is dangerous, treat that as invalid (return -1 ).
Return -1 if no such path exists.

Part 2

Now you may pass through dangerous stops. Among all paths from source to target:

Minimize the number of dangerous stops visited (count visits to dangerous nodes; clarify whether source/target count if they are dangerous).
Subject to (1), minimize the number of steps .

Return the minimum steps for the best path under the above ordering (or return both metrics if preferred—clarify with interviewer).

Follow-up

Explain how you would change your visited structure to correctly handle Part 2 (e.g., when the same stop can be reached with fewer dangerous stops or fewer steps).