Best-scoring ski run through a trail map: Frontier Interview's solution

Question: Best-scoring ski run through a trail map

Companies: Airbnb

Difficulty: Hard

Problem statement

A ski area has mapped its one-way trails between named checkpoints. The trail map has no cycles: once you ski down a trail you can never get back to where you were.

Every trail has a cost to ski it, and some checkpoints award points when you arrive. The skier starts at the checkpoint START and may finish at any checkpoint whose name begins with END_.

The net score of a run is the sum of the rewards of every checkpoint on it (including START and the finish) minus the sum of the costs of the trails it uses.

Implement:

def max_net_score(routes: list[list], checkpoints: list[list]) -> int | None

routes[i] = [from, cost, to] is a one-way trail from from to to with a non-negative integer cost.
checkpoints[j] = [name, reward] gives the reward for arriving at name. A checkpoint that is not listed has reward 0.
Return the highest net score over all runs from START to any END_ checkpoint. The answer may be negative. Return None if no finish can be reached from START.

Constraints

Up to 10^5 checkpoints and 2 * 10^5 trails.
The graph is a DAG. There may be more than one trail between the same two checkpoints.
Rewards fit in a 32-bit integer.

Example 1

routes = [["START", 3, "A"], ["START", 1, "B"], ["A", 2, "END_1"],
          ["B", 4, "C"], ["C", 1, "END_1"], ["C", 6, "END_2"]]
checkpoints = [["A", 8], ["B", 2], ["C", 9], ["END_1", 5], ["END_2", 14]]

Output: 14. The run START -> B -> C -> END_2 scores -1 + 2 - 4 + 9 - 6 + 14 = 14. The other runs score 8 (START -> A -> END_1) and 10 (START -> B -> C -> END_1).

Example 2

routes = [["START", 5, "END_X"]]
checkpoints = [["END_X", 2]]

Output: -3. The only run costs more than it earns, but it is still the best run.

Be ready to return the route itself, and to discuss what changes if each trail also takes time and the skier has a time limit.

Approach

The trail map is a directed acyclic graph. A path's net score is the sum of
rewards at the checkpoints it visits (including START) minus the sum of the
costs of the trails it uses. We want the best net score over all paths that
begin at START and end at any checkpoint whose name starts with END_.

Brute force. DFS from START, carrying the running score, and record the
score each time we reach an END_ checkpoint. Correct, but the number of
paths in a DAG can be exponential (a ladder of k diamonds has 2^k paths),
so this blows up.

Optimal: DP in topological order. Because the graph has no cycles, the
best way to reach a checkpoint v only depends on the best ways to reach its
predecessors:

best[START] = reward[START]
best[v]     = reward[v] + max over edges (u -> v, cost) of (best[u] - cost)

If we process checkpoints in topological order, every best[u] is final
before any edge out of u is relaxed. Kahn's algorithm gives that order and
also detects a cycle (some node never reaches in-degree zero), which we
report as invalid input instead of returning a wrong answer.

Two details matter:

Only nodes reachable from START may get a value. We keep best[v] = -inf
for everything else and skip relaxing from -inf, so an unreachable chain
cannot contribute.
Scores can go negative (costs larger than rewards). We still have to pick
the best END_ checkpoint, so we never clamp to zero. If no END_ is
reachable, return None.

Invariant: when a node is popped from the queue, all its incoming edges have
been relaxed, so best[node] is the maximum over all START -> node paths.
Keeping a parent pointer for the edge that set best[v] lets us rebuild
the winning route.

Code

from collections import defaultdict, deque
from typing import Optional

NEG_INF = float("-inf")


def best_ski_route(
    routes: list[tuple[str, int, str]],
    checkpoints: list[tuple[str, int]],
    start: str = "START",
    end_prefix: str = "END_",
) -> tuple[Optional[int], list[str]]:
    """Return (best net score, path) from start to any end checkpoint.

    routes: (from, cost, to) one-way trails. checkpoints: (name, reward);
    names missing from checkpoints have reward 0. Returns (None, []) when no
    end checkpoint is reachable. Raises ValueError if the graph has a cycle.
    """
    reward: dict[str, int] = defaultdict(int)
    for name, value in checkpoints:
        reward[name] = value

    adj: dict[str, list[tuple[str, int]]] = defaultdict(list)
    indegree: dict[str, int] = defaultdict(int)
    nodes: set[str] = {start} | set(reward)
    for u, cost, v in routes:
        adj[u].append((v, cost))
        indegree[v] += 1
        nodes.update((u, v))

    best: dict[str, float] = {n: NEG_INF for n in nodes}
    parent: dict[str, Optional[str]] = {start: None}
    best[start] = reward[start]

    queue = deque(n for n in nodes if indegree[n] == 0)
    processed = 0
    while queue:
        u = queue.popleft()
        processed += 1
        for v, cost in adj[u]:
            if best[u] != NEG_INF:
                candidate = best[u] - cost + reward[v]
                if candidate > best[v]:
                    best[v] = candidate
                    parent[v] = u
            indegree[v] -= 1
            if indegree[v] == 0:
                queue.append(v)

    if processed != len(nodes):
        raise ValueError("trail map contains a cycle")

    finish = None
    for n in nodes:
        if n.startswith(end_prefix) and best[n] != NEG_INF:
            if finish is None or best[n] > best[finish]:
                finish = n
    if finish is None:
        return None, []

    path: list[str] = []
    node: Optional[str] = finish
    while node is not None:
        path.append(node)
        node = parent[node]
    return int(best[finish]), path[::-1]


def max_net_score(routes, checkpoints) -> Optional[int]:
    return best_ski_route(routes, checkpoints)[0]


if __name__ == "__main__":
    routes = [
        ("START", 3, "A"), ("START", 1, "B"),
        ("A", 2, "END_1"), ("B", 4, "C"),
        ("C", 1, "END_1"), ("C", 6, "END_2"),
    ]
    points = [("A", 8), ("B", 2), ("C", 9), ("END_1", 5), ("END_2", 14)]
    assert best_ski_route(routes, points) == (14, ["START", "B", "C", "END_2"])
    assert max_net_score([("START", 5, "END_X")], [("END_X", 2)]) == -3
    assert max_net_score([("START", 1, "A")], [("A", 4)]) is None
    assert max_net_score([("X", 1, "END_Z")], [("END_Z", 100)]) is None
    try:
        best_ski_route([("START", 1, "A"), ("A", 1, "START")], [])
        raise AssertionError("expected cycle error")
    except ValueError:
        pass
    print("ok")

Complexity

Building the graph: O(V + E) time, O(V + E) space.
Kahn's topological pass with relaxation: each node is queued once and each
edge is relaxed once, so O(V + E) time.
Choosing the best finish and rebuilding the path: O(V).
Total: O(V + E) time and O(V + E) space. The DFS brute force is
O(number of paths), exponential in the worst case.

Test cases

Routes START -3-> A, START -1-> B, A -2-> END_1, B -4-> C,
C -1-> END_1, C -6-> END_2; rewards A=8, B=2, C=9, END_1=5, END_2=14.
Candidates: START,A,END_1 = -3+8-2+5 = 8; START,B,C,END_1 =
-1+2-4+9-1+5 = 10; START,B,C,END_2 = -1+2-4+9-6+14 = 14.
Expected: 14, path ["START", "B", "C", "END_2"].
Only route costs more than the reward: START -5-> END_X, END_X = 2 →
-3 (negative answers are allowed; do not clamp to 0).
No finish reachable: only START -1-> A → None.
A finish exists but only from an unreachable node: X -1-> END_Z,
END_Z = 100 → None (the -inf guard stops X from leaking a score).
Cycle START -> A -> START → ValueError.
START has its own reward, say 4: every path's score goes up by 4.
A checkpoint missing from checkpoints has reward 0.
Two parallel trails START -> END_1 with costs 5 and 2, END_1 = 3 → 1
(the cheaper edge wins).

Follow-ups

Return the route, not just the score. Keep a parent pointer for the
edge that last improved best[v] and walk back from the winning finish,
as the code does. For ties, define a rule (e.g. fewest trails, then
lexicographic) and compare (score, -length, ...) tuples.
Time budget. Each trail also takes t minutes and the skier has T
minutes. The state becomes (checkpoint, time used):
best[v][t + t_uv] = max(best[u][t] + reward[v] - cost), still in
topological order. O((V + E) * T) time; with large T keep, per node,
only Pareto-optimal (time, score) pairs.
Rewards collected once on revisits / the map has cycles (lifts back up).
With cycles, a positive-net loop makes the score unbounded; detect it with
Bellman-Ford on negated weights (looking for a negative cycle reachable
from START that can reach an END_). If each reward counts only once,
the problem becomes a prize-collecting path problem (NP-hard in general);
discuss bitmask DP over checkpoints for small V.
Many queries from different starts. Reverse the DP: process in reverse
topological order and compute toEnd[u] = reward[u] + max(toEnd[v] - cost),
with toEnd[e] = reward[e] for finishes. Every start is then an O(1)
lookup after one O(V + E) pass.
Top-k routes or at most k trails. For top-k keep the k best scores
per node (merge from predecessors, O((V + E) k log k)). For a trail limit,
add the number of trails used to the state, O((V + E) k).

Interviewer expectations

Mid-level (L4)

Parses [from, cost, to] and [checkpoint, reward] into an adjacency list
and reward map without mixing up the field order.
Gets to a working solution, DFS with memoization or topological DP, and
states O(V + E).
Handles negative scores and the no-reachable-finish case when prompted.

Senior (L5)

Starts from the recurrence and explains why topological order (or memoized
DFS) is correct on a DAG and why plain DFS over paths is exponential.
Unprompted: reachability guard (-inf), START reward, missing rewards,
parallel edges, cycle detection in the input.
Reconstructs the path and adapts quickly to the time-budget follow-up.

Staff (L6+)

Frames the problem as a longest path in a DAG and explains why it becomes
hard (or unbounded) once cycles or once-only rewards appear.
Picks forward vs reverse DP based on the query pattern (one start vs many,
updates to rewards) and discusses incremental recomputation when trails
open or close.
Discusses input validation, recursion depth (prefers iterative Kahn's over
recursive DFS for deep maps), and how they would test it.