0

Shipping route cost paths

by Frontier Interview· 1 day ago· ⑂ 0 remixes

Question: Shipping route cost paths

Companies: Stripe

Difficulty: Medium

Problem statement

A parcel carrier publishes its shipping routes as a list of strings. Each string has the form source:target:method:cost:

  • source and target are country codes. A route ships one way only.
  • method is the carrier or mode (for example Air, Sea, Rail). The same pair of countries can have several routes with different methods.
  • cost is a non-negative integer.

Implement a class ShippingNetwork(routes: list[str]) that answers these questions in parts:

  1. direct_cost(src, dst) -> int | None. The cheapest single route from src to dst, or None if there is none.
  2. all_paths(src, dst, max_legs=2) -> list[Path]. Every way to ship from src to dst using at most max_legs routes (so by default, direct or through one intermediate country). A path must not visit a country twice. Each path lists its legs (source, target, method, cost) and its total cost. Return the paths sorted by total cost, cheapest first.
  3. cheapest_path(src, dst) -> Path | None. The cheapest path with any number of stops, or None if dst cannot be reached.

Reject malformed route strings with an error.

Example

routes = ["JP:DE:Air:9", "JP:SG:Sea:2", "SG:DE:Air:4", "JP:DE:Sea:7"]
  • direct_cost("JP", "DE") returns 7.
  • all_paths("JP", "DE") returns three paths: JP -Sea-> SG -Air-> DE (6), JP -Sea-> DE (7), JP -Air-> DE (9).
  • direct_cost("DE", "JP") returns None, because routes are one way.

Example with more stops

routes = ["A:B:x:10", "A:C:y:1", "C:D:z:1", "D:B:w:1"]
  • all_paths("A", "B") returns only the direct path (10). The cheaper path needs two stops.
  • cheapest_path("A", "B") returns A -> C -> D -> B with cost 3.

Talk through how your design would change if the interviewer adds a limit on the number of stops, or bans some methods or countries.

Approach

Clarify first. Each route is a string source:target:method:cost. Settle these before coding:

  • Direction. A route ships one way. US:UK does not give you UK:US. Ask; most interviewers say directed.
  • Parallel routes. Two carriers can serve the same pair (JP:DE:Air:9 and JP:DE:Sea:7). Keep both. They are different paths, and the method is part of the answer.
  • Costs. Non-negative integers. Reject malformed strings rather than guessing.
  • What a path is. A list of legs. Report each leg's method and cost plus the total. No country appears twice in one path.

The question comes in parts. Build the parser and the graph once, then answer each part on top of it.

Part 1: direct cost. Group legs by source in a dict of lists (an adjacency list). The direct cost is the cheapest leg from src whose target is dst, or None. A dict keyed by (src, dst) makes this O(1), but the adjacency list serves every later part, so start there.

Part 2: all paths with at most one stop. The brute force is to loop: every direct leg, then every leg src -> mid followed by every leg mid -> dst. That is fine for exactly one stop, but it does not extend. Write a depth-first search with a leg limit instead. Carry the current legs and the set of countries on the path. When you reach dst, record a copy and stop going deeper on that branch. When you have used max_legs, stop. Sort the result by total cost so the cheapest comes first.

The invariant: seen holds exactly the countries on the current path. Adding on the way down and removing on the way back keeps that true, so no path revisits a country and every simple path within the limit is found once per combination of methods.

Part 3: cheapest path, any number of stops. Enumerating all paths is exponential. Costs are non-negative, so use Dijkstra. Keep the best known cost to each country and the leg that reached it. Pop the cheapest frontier country; skip stale heap entries; relax its outgoing legs. Stop when dst is popped, because its cost can no longer improve. Walk the via links back from dst to rebuild the legs. Parallel routes need no special case: relaxation keeps the cheapest leg automatically.

Code

from __future__ import annotations

import heapq
from collections import defaultdict
from dataclasses import dataclass


@dataclass(frozen=True)
class Leg:
    source: str
    target: str
    method: str
    cost: int


@dataclass(frozen=True)
class Path:
    legs: tuple[Leg, ...]

    @property
    def cost(self) -> int:
        return sum(leg.cost for leg in self.legs)

    def describe(self) -> str:
        if not self.legs:
            return "(empty)"
        hops = [f"{l.source} -[{l.method} {l.cost}]-> " for l in self.legs]
        return "".join(hops) + self.legs[-1].target + f" = {self.cost}"


class ShippingNetwork:
    def __init__(self, routes: list[str]) -> None:
        self.out: dict[str, list[Leg]] = defaultdict(list)
        for raw in routes:
            parts = raw.strip().split(":")
            if len(parts) != 4:
                raise ValueError(f"bad route: {raw!r}")
            src, dst, method, cost = parts
            amount = int(cost)
            if amount < 0:
                raise ValueError(f"negative cost: {raw!r}")
            self.out[src].append(Leg(src, dst, method, amount))

    # Part 1: cheapest single leg, or None.
    def direct_cost(self, src: str, dst: str) -> int | None:
        costs = [l.cost for l in self.out.get(src, []) if l.target == dst]
        return min(costs) if costs else None

    # Part 2: every path with at most `max_legs` legs, no country repeated.
    def all_paths(self, src: str, dst: str, max_legs: int = 2) -> list[Path]:
        found: list[Path] = []
        legs: list[Leg] = []
        seen = {src}

        def dfs(node: str) -> None:
            if node == dst and legs:
                found.append(Path(tuple(legs)))
                return
            if len(legs) == max_legs:
                return
            for leg in self.out.get(node, []):
                if leg.target in seen:
                    continue
                seen.add(leg.target)
                legs.append(leg)
                dfs(leg.target)
                legs.pop()
                seen.discard(leg.target)

        if src != dst:
            dfs(src)
        found.sort(key=lambda p: (p.cost, len(p.legs), p.describe()))
        return found

    # Part 3: cheapest path with any number of legs (Dijkstra).
    def cheapest_path(self, src: str, dst: str) -> Path | None:
        if src == dst:
            return Path(())
        best: dict[str, int] = {src: 0}
        via: dict[str, Leg] = {}
        heap: list[tuple[int, str]] = [(0, src)]
        while heap:
            dist, node = heapq.heappop(heap)
            if dist > best[node]:
                continue
            if node == dst:
                break
            for leg in self.out.get(node, []):
                nd = dist + leg.cost
                if nd < best.get(leg.target, nd + 1):
                    best[leg.target] = nd
                    via[leg.target] = leg
                    heapq.heappush(heap, (nd, leg.target))
        if dst not in best:
            return None
        legs: list[Leg] = []
        node = dst
        while node != src:
            leg = via[node]
            legs.append(leg)
            node = leg.source
        return Path(tuple(reversed(legs)))

Example:

net = ShippingNetwork(["JP:DE:Air:9", "JP:SG:Sea:2", "SG:DE:Air:4", "JP:DE:Sea:7"])
net.direct_cost("JP", "DE")              # 7
[p.describe() for p in net.all_paths("JP", "DE")]
# ['JP -[Sea 2]-> SG -[Air 4]-> DE = 6',
#  'JP -[Sea 7]-> DE = 7',
#  'JP -[Air 9]-> DE = 9']
net.cheapest_path("JP", "DE").cost      # 6

Complexity

Let R be the number of routes, V the number of countries, and d the most legs leaving one country.

  • Build: O(R) time and space.
  • direct_cost: O(d) time, O(1) extra space. O(1) with a (src, dst) index.
  • all_paths with max_legs = k: O(d^k * k) time in the worst case, since each of up to d^k paths is copied when found. For one stop that is O(d^2). Space is O(k) for the recursion plus the output.
  • cheapest_path: O((V + R) log R) time with a binary heap, O(V + R) space.

Test cases

Network A: ["JP:DE:Air:9", "JP:SG:Sea:2", "SG:DE:Air:4", "JP:DE:Sea:7", "SG:BR:Sea:6", "BR:DE:Rail:1", "DE:JP:Air:9"]

  • direct_cost("JP", "DE") returns 7 (the cheaper of two parallel routes).
  • direct_cost("DE", "SG") returns None.
  • all_paths("JP", "DE") returns totals [6, 7, 9]: via SG by Sea and Air, then direct Sea, then direct Air.
  • all_paths("JP", "DE", max_legs=3) returns totals [6, 7, 9, 9], adding JP -> SG -> BR -> DE.
  • cheapest_path("JP", "DE").cost is 6.

Network B: ["A:B:x:10", "A:C:y:1", "C:D:z:1", "D:B:w:1"]

  • cheapest_path("A", "B") is A -> C -> D -> B with cost 3, cheaper than the direct 10.
  • all_paths("A", "B") (one stop max) returns only the direct path, cost 10.
  • cheapest_path("B", "A") returns None, because routes are one way.

Edge cases:

  • src == dst: all_paths returns []; cheapest_path returns an empty path with cost 0.
  • Empty route list: every query returns None or [].
  • "bad" or "A:B:x:-1": the constructor raises ValueError.
  • A cycle (DE:JP above) does not cause an infinite loop: seen blocks it in the search, and Dijkstra never improves a settled country.

Follow-ups

  • Fewest stops, or at most K stops at the lowest cost. Dijkstra ignores stop count. For "cheapest with at most K stops", run Bellman-Ford for K + 1 rounds, copying the distance array each round, or run Dijkstra on states (country, legs used). Both are O(K * R).
  • Preferred or banned methods and countries. Filter legs as you relax them (if leg.method in allowed). Banned countries are just never pushed. Nothing else changes.
  • Undirected routes. Add the reverse leg in the constructor. The search code stays the same.
  • Price per parcel weight or currency. Make cost a function of the leg and the parcel, for example base + per_kg * weight, or convert each leg into one currency before summing. Dijkstra still works as long as every leg cost stays non-negative.
  • Many queries on a static network. Cache Dijkstra results per source, or precompute all pairs with Floyd-Warshall (O(V^3)) when V is small, so each query is a lookup.

Interviewer expectations

Mid-level (L4)

  • Parses the strings cleanly and validates them; asks about direction and duplicates.
  • Gets part 1 and part 2 working with readable code and sensible names.
  • Returns paths with legs, methods and totals, not only a number.

Senior (L5)

  • Builds one adjacency list that serves every part, and writes part 2 as a bounded DFS instead of nested loops.
  • Reaches Dijkstra for part 3 unprompted, explains why non-negative costs make it correct, and rebuilds the path.
  • States complexity per method and tests parallel routes, cycles and unreachable targets.

Staff (L6+)

  • Separates parsing, the graph and the queries so new constraints (stop limits, method filters, weight pricing) slot in without rewrites.
  • Explains when Dijkstra breaks (stop limits, negative adjustments such as discounts) and what replaces it.
  • Talks about scale: caching per source, precomputing for a static network, and how to update when a carrier adds or drops a route.

Sign in to comment, vote or remix.