How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

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

What role is this question designed for?

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

Compute shortest delivery route with dangerous stops

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.

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.

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

Expected Output: -1

Explanation: The source itself is dangerous, so the trip is invalid.

Input: (1, [], 0, 0, [])

Expected Output: 0

Explanation: Source and target are the same safe stop, so no movement is needed.

Solution

def solution(n, routes, source, target, dangerous):
    from collections import deque

    danger = set(dangerous)
    if source in danger or target in danger:
        return -1
    if source == target:
        return 0

    graph = [set() for _ in range(n)]
    for route in routes:
        for i in range(len(route) - 1):
            a, b = route[i], route[i + 1]
            graph[a].add(b)
            graph[b].add(a)

    dist = [-1] * n
    dist[source] = 0
    q = deque([source])

    while q:
        node = q.popleft()
        for nei in graph[node]:
            if nei in danger or dist[nei] != -1:
                continue
            dist[nei] = dist[node] + 1
            if nei == target:
                return dist[nei]
            q.append(nei)

    return -1

Time complexity: O(n + m), where `m` is the number of adjacent stop-pairs across all routes.. Space complexity: O(n + m).

Hints

Convert each route into graph edges by connecting consecutive stops.
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]`.

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

Expected Output: [2, 2]

Explanation: The source and target are both dangerous, and both count. The only path is `0 -> 1 -> 2`, so the result is 2 dangerous visits and 2 steps.

Input: (1, [], 0, 0, [0])

Expected Output: [1, 0]

Explanation: Source and target are the same stop, and it is dangerous, so the path has 1 dangerous visit and 0 steps.

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

Expected Output: [-1, -1]

Explanation: There is no path at all from `0` to `3`.

Solution

def solution(n, routes, source, target, dangerous):
    import heapq

    danger = set(dangerous)

    graph = [set() for _ in range(n)]
    for route in routes:
        for i in range(len(route) - 1):
            a, b = route[i], route[i + 1]
            graph[a].add(b)
            graph[b].add(a)

    start_cost = (1 if source in danger else 0, 0)
    dist = [None] * n
    dist[source] = start_cost
    heap = [(start_cost[0], start_cost[1], source)]

    while heap:
        danger_used, steps, node = heapq.heappop(heap)
        if dist[node] != (danger_used, steps):
            continue
        if node == target:
            return [danger_used, steps]

        for nei in graph[node]:
            new_cost = (danger_used + (1 if nei in danger else 0), steps + 1)
            if dist[nei] is None or new_cost < dist[nei]:
                dist[nei] = new_cost
                heapq.heappush(heap, (new_cost[0], new_cost[1], nei))

    return [-1, -1]

Time complexity: O((n + m) log n), where `m` is the number of adjacent stop-pairs across all routes.. Space complexity: O(n + m).

Hints

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

Quick Overview