10. Route an Escalated Ticket Through a Team Graph

Problem

When Fin can't resolve a ticket, it hands the customer off to a human. Human support is organized into teams that can each escalate further to other teams, but only some teams have the specific skill/tag the ticket needs. Given a directed graph of team handoff relationships and a starting team, find the shortest escalation path (fewest hops) from the start to any team that has the required skill.

Return the full path as a list of team names, or None if no skilled team is reachable from the start.

Source: src/10_shortest_escalation_path.py

def shortest_escalation_path(start_team: str, handoffs: dict[str, list[str]], skilled_teams: set[str]) -> list[str] | None

>>> shortest_escalation_path(
...     "tier1",
...     {"tier1": ["tier2", "billing"], "tier2": ["tier3"], "billing": []},
...     {"tier3"},
... )
['tier1', 'tier2', 'tier3']

>>> shortest_escalation_path("tier1", {"tier1": ["tier2"]}, {"tier1"})
['tier1']

Step-by-Step Approach

1. Recognize "fewest hops in an unweighted directed graph" as a textbook Breadth-First Search — BFS explores in order of distance from the start, so the first time you reach a skilled team is guaranteed to be via the shortest path.
2. Handle the trivial case first: if the starting team already has the required skill, return a single-element path immediately, no traversal needed.
3. Otherwise, set up a queue seeded with the path so far (just [start_team]) and a visited set containing the start team, to avoid revisiting nodes and looping forever on cycles.
4. Pop paths off the front of the queue (FIFO, not a stack) so nodes are explored in strict distance order.
5. For each neighbor of the current path's last team that hasn't been visited yet, build the extended path.
6. If that neighbor is a skilled team, return the extended path immediately — since BFS processes nodes in increasing distance order, this is provably the shortest such path.
7. Otherwise mark it visited and push the extended path onto the back of the queue to be explored later.
8. If the queue empties without finding any skilled team, return None — no such team is reachable.

The key insight is carrying the whole path (not just the current node) through the queue — this trades a bit of extra memory for getting the final answer directly on the first skilled-team hit, avoiding a separate parent-pointer reconstruction pass.

Reference solution

from collections import deque


def shortest_escalation_path(
    start_team: str, handoffs: dict[str, list[str]], skilled_teams: set[str]
) -> list[str] | None:
    # BFS over the handoff graph, tracking full paths: O(teams + handoff edges).
    if start_team in skilled_teams:
        return [start_team]

    visited = {start_team}
    # deque for O(1) pops off the front
    queue: deque[list[str]] = deque([[start_team]])
    while queue:
        # FIFO order guarantees shortest-path-first
        path = queue.popleft()
        current = path[-1]
        # get() avoids KeyError on leaf teams
        for neighbor in handoffs.get(current, []):
            if neighbor in visited:
                continue
            # carry full path so answer needs no reconstruction
            new_path = path + [neighbor]
            # check at discovery time, not on pop
            if neighbor in skilled_teams:
                return new_path
            # mark-on-push to avoid duplicate enqueues
            visited.add(neighbor)
            queue.append(new_path)
    return None

Key Functions & Tricks

• collections.deque — O(1) append/pop from both ends, unlike O(n) list.pop(0)
• deque[list[str]] type annotation — documents each queue entry as a full path, no runtime effect
• Carrying full paths in the queue — path + [neighbor] avoids a separate parent-pointer reconstruction
• set for visited — O(1) average membership checks, avoids cycles
• dict.get(current, []) — returns [] instead of raising on a leaf team
• Mark-on-push, not mark-on-pop — prevents the same node being enqueued multiple times
• Early return at discovery time — returns the instant a skilled team is found, no extra BFS layer

How to Recognize This Pattern