Routes through graphs and grids: A Sample Coding Interview Solution

The coding question

You're given a list of roads between intersections, each with a travel time. Given a start and a destination, return the shortest possible travel time, or -1 if you can't get there.

Ask a few questions first

Ask	What we'll assume
Are roads one-way?	Yes, each road goes from one intersection to another. A two-way road shows up twice.
Can travel times be negative?	No, they're zero or more. That matters, because it's what lets us use Dijkstra's algorithm.
How big can it get?	Up to around 100,000 intersections and roads, so anything quadratic is too slow.
What if start and destination are the same?	Return 0.

A couple of examples

Input	Output
roads [("A","B",4), ("A","C",1), ("C","B",2), ("B","D",5)], from "A" to "D"	8 (A to C to B to D)
the same roads, from "D" to "A"	-1, since nothing leaves D
the same roads, from "A" to "A"	0

Start with brute force

Try every route from the start with a depth-first search, skipping intersections already on the current path, and keep the fastest one that reaches the destination.

Cost: the number of possible routes can grow exponentially with the number of intersections, so this only works on tiny maps.

A better way

If every road had the same travel time, a breadth-first search would find the answer. Different times mean the closest-by-count intersection might not be the closest-by-time one.

Dijkstra's algorithm fixes that. Always expand whichever intersection we can currently reach fastest. Because no road takes negative time, once we pop an intersection off the heap, nothing later can reach it faster. That's graph traversal with a priority queue instead of a plain queue.

Build a map from each intersection to its outgoing roads.
Keep the best known time to each intersection, starting with 0 for the start.
Put (0, start) on a min-heap.
Pop the fastest entry. If it's the destination, return its time. If we've already found something faster for this intersection, skip it.
For each road out, if going that way beats the best known time, record it and push it on the heap.
If the heap runs out, the destination can't be reached, so return -1.

The code

solution.pypython

import heapq
from collections import defaultdict


def shortest_time(roads, start, end):
    graph = defaultdict(list)
    for a, b, minutes in roads:
        graph[a].append((b, minutes))

    best = {start: 0}
    heap = [(0, start)]
    while heap:
        time_so_far, node = heapq.heappop(heap)
        if node == end:
            return time_so_far
        if time_so_far > best[node]:
            continue  # an old, slower entry for this node
        for nxt, minutes in graph[node]:
            new_time = time_so_far + minutes
            if new_time < best.get(nxt, float("inf")):
                best[nxt] = new_time
                heapq.heappush(heap, (new_time, nxt))
    return -1

	Cost	Why
Time	O((V + E) log V)	Each road can push one heap entry, and each heap operation is log of its size
Space	O(V + E)	The road map, the best times and the heap

Test it

Walk through one of the examples out loud, then check the cases that tend to break things:

Start equals destination: the first pop returns 0.
No roads at all: the heap empties and we return -1.
A road with travel time 0: still fine, since nothing's negative.
Two roads between the same pair with different times: both get checked, and the faster one wins.
A cycle in the roads: the 'already found faster' check stops us going around it forever.

Common mistakes

Using a plain breadth-first search, which counts roads, not minutes.
Marking an intersection done when you push it instead of when you pop it. A faster route might still turn up.
Forgetting to skip stale heap entries, which makes it slower and can give wrong answers if you also update other state.
Building the graph as two-way when the roads are one-way.

Follow-up questions

What if it's a grid where each cell has a cost to enter?

Same algorithm. Each cell is a node, its up to four neighbors are the edges, and the cost of an edge is the cost of the cell you're moving into.

What if some travel times could be negative?

Dijkstra's no longer works, because a later road could make an already-finished node cheaper. Use Bellman-Ford, which is slower, O(V × E), but handles it and can spot negative loops.

What if you also need the route itself?

Keep a 'came from' map, updated whenever you improve a node's time. When you reach the destination, walk back through it and reverse the list.

How the time adds up

Minutes	What you're doing
0–5	Ask questions and agree on examples
5–10	Brute force and what it costs
10–15	Explain the better idea
15–30	Write the code
30–38	Test it out loud
38–45	Follow-up questions

Key concepts used here

We wrote this sample solution ourselves. Practice Loop is independent and isn't affiliated with or endorsed by Uber.