Quick Overview

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.

Compute shortest delivery route with dangerous stops

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

## 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`: 1. Minimize the **number of dangerous stops visited** (count visits to dangerous nodes; clarify whether `source/target` count if they are dangerous). 2. 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).

Quick Answer: 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.

Part 1: Minimum Steps While Avoiding Dangerous Stops

You are given `n` delivery stops labeled `0` to `n - 1` and a list of routes. Each route such as `[a, b, c, d]` creates undirected edges only between adjacent stops in that route: `(a, b)`, `(b, c)`, and `(c, d)`. Given `source`, `target`, and a collection `dangerous`, find the minimum number of steps needed to travel from `source` to `target` without visiting any dangerous stop. Rules: - If `source` or `target` is dangerous, the trip is invalid and you must return `-1`. - If no safe path exists, return `-1`. - A route of length `0` or `1` adds no edges. - A step means traversing one edge.

Constraints

  • 1 <= n <= 100000
  • 0 <= len(routes) <= 100000
  • 0 <= total number of stops across all routes <= 200000
  • 0 <= source, target < n
  • Every stop listed in `routes` and `dangerous` is in the range [0, n - 1]

Examples

Input: (5, [[0, 1, 2, 3], [0, 4, 3]], 0, 3, [4])

Expected Output: 3

Explanation: The shorter path `0 -> 4 -> 3` is blocked because stop `4` is dangerous. The best safe path is `0 -> 1 -> 2 -> 3`, which takes 3 steps.

Input: (5, [[0, 1, 2], [2, 3, 4]], 0, 4, [2])

Expected Output: -1

Explanation: Every path from `0` to `4` must pass through stop `2`, which is dangerous.

Hints

  1. Convert each route into graph edges by connecting consecutive stops.
  2. Because every edge has the same weight, breadth-first search is the right tool once you ignore dangerous stops.

Part 2: Lexicographically Best Route by Dangerous Visits Then Steps

You are given `n` delivery stops labeled `0` to `n - 1` and a list of routes. Each route such as `[a, b, c, d]` creates undirected edges only between adjacent stops in that route: `(a, b)`, `(b, c)`, and `(c, d)`. You may travel through dangerous stops. Among all possible paths from `source` to `target`, choose the one with the smallest cost under this ordering: 1. Minimize the number of dangerous stops visited. 2. If there is still a tie, minimize the number of steps. For this problem, a dangerous stop counts every time the path starts on or enters that stop. So: - `source` counts if it is dangerous. - `target` counts if it is dangerous. Return the result as `[min_dangerous_visits, min_steps]`. If no path exists, return `[-1, -1]`. Important note: a simple boolean `visited` array is not enough here, because the same stop may need to be processed again if you later reach it with fewer dangerous visits, or with the same dangerous visits but fewer steps.

Constraints

  • 1 <= n <= 100000
  • 0 <= len(routes) <= 100000
  • 0 <= total number of stops across all routes <= 200000
  • 0 <= source, target < n
  • Every stop listed in `routes` and `dangerous` is in the range [0, n - 1]

Examples

Input: (6, [[0, 1, 5], [0, 2, 3, 4, 5]], 0, 5, [1])

Expected Output: [0, 4]

Explanation: Path `0 -> 1 -> 5` takes only 2 steps but visits 1 dangerous stop. Path `0 -> 2 -> 3 -> 4 -> 5` takes 4 steps and visits 0 dangerous stops, so it is better.

Input: (6, [[0, 1, 5], [0, 2, 3, 5]], 0, 5, [1, 2])

Expected Output: [1, 2]

Explanation: Both main paths visit exactly 1 dangerous stop. The shorter one is `0 -> 1 -> 5`, so the answer is `[1, 2]`.

Hints

  1. Think of the path cost as a pair: `(dangerous_visits, steps)`, and compare pairs lexicographically.
  2. Instead of a boolean `visited`, store the best pair seen so far for each stop and update it when you find a better one.

Loading coding console...