Memoization for Redundant Computation | Dataford Interview Questions

Tesla Supercharger route planning can represent possible charging transitions as a directed acyclic graph. Given this graph, count how many distinct directed routes exist from a starting station to a destination station. A naive recursive implementation repeatedly counts the same downstream subgraphs, so optimize the calculation with memoization or bottom-up dynamic programming.

Each directed edge represents one valid transition. Distinct edge sequences are distinct routes. Return the result modulo 1,000,000,007.

Formal Specification

Implement count_routes(graph, start, destination), where graph[i] is a list of station indices reachable directly from station i. Return an integer containing the number of directed routes from start to destination. The empty route counts as one route when start == destination.

The graph is guaranteed to be a DAG, and it contains no duplicate edges.

Constraints

1 <= len(graph) <= 10^5
Every neighbor is an integer in [0, len(graph) - 1]
The graph is a DAG with no duplicate edges
The total number of edges is at most 2 * 10^5
0 <= start, destination < len(graph)

Function Signature

def count_routes(graph, start, destination):

Your question is Memoization for Redundant Computation. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem