The Shortest Route

A medium Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
medium
Seniority
L4
Asked in
Citadel

Problem

A message-routing service keeps an adjacency dict mapping each node to the nodes it can forward to directly. Given that graph and two node names, return the fewest hops from start to end, or -1 when end can't be reached.

Fewer hops is always better.

Example 1

Input:

graph = {"A":["B","C"],"B":["D"],"C":["D"],"D":[]}, start = "A", end = "D"

Output:

2

Example 2

Input:

graph = {"A":["B"],"B":[],"C":["D"],"D":[]}, start = "A", end = "D"

Output:

-1

Worked solution and explanation

What this really is

This is unweighted shortest-path wearing a neighbor-lookup costume. The real skill: knowing that a breadth-first sweep reaches every node by its fewest-hop distance, so the first time you touch end you already hold the answer. Anyone can walk a neighbor list. What separates candidates is the visited set, and more subtly, marking a node visited the moment you enqueue it rather than when you pop it. Skip that and a cycle like A pointing to B pointing back to A spins forever, or the same node gets re-enqueued from three parents and your O(V+E) sweep quietly degrades into repeated work.

How the sweep goes

Step 1: Seed the frontier and guard the trivial case

Handle start == end before anything else: zero edges reach a node from itself. Then enqueue the start with distance 0 and mark it visited immediately, so it can never be enqueued again.

Step 2: Expand neighbors one level at a time

Pop a node, look at each neighbor. If a neighbor is end, you are one hop past the popped node, so return dist + 1. Otherwise, if it is unseen, mark it visited and enqueue it with dist + 1. Marking at enqueue time is what keeps each node in the queue exactly once.

Step 3: An empty queue means unreachable

If the queue drains without ever hitting end, every node reachable from start has been visited and the target is not among them. Return -1. A missing start or end key falls out of this naturally: graph.get(node, []) yields no neighbors, so an absent target is simply unreachable.

The solution

BFS with distance tracking
from collections import deque


def shortest_path(graph: dict, start: str, end: str) -> int:
    if start == end:
        return 0
    visited = {start}
    queue = deque([(start, 0)])
    while queue:
        node, dist = queue.popleft()
        for neighbor in graph.get(node, []):
            if neighbor == end:
                return dist + 1
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, dist + 1))
    return -1

Common follow-up questions