Code RoomCount probe routes
HardPrep Room Coding #4948

Count probe routes

CodingAlgorithms & data structuresMid–Staff~38 min

A network team counts the diagnostic routes a probe could take. link_ms is a square table where link_ms[a][b] is the one way latency in milliseconds of the link from node a to node b, and 0 means there is no link, including every entry on the diagonal. The table is not always symmetric. A route starts at node 0, ends at the last node, never visits a node twice, totals at most budget milliseconds, and passes through every node listed in must_visit. must_visit may repeat a node and may name the start or the end. Return how many such routes exist. Return 0 when the table has no nodes. A table with a single node gives one route, the one that has already arrived, whenever budget is not negative. There are at most 12 nodes.

Implement
count_relay_routes(link_ms: list[list[int]], budget: int, must_visit: list[int]) → int
Examples
in[[[0,4,9],[4,0,3],[9,3,0]],12,[]]out2
in[[[0,4,9],[4,0,3],[9,3,0]],12,[1]]out1
in[[[0,4,9],[4,0,3],[9,3,0]],6,[]]out0
What a strong answer looks like

State your approach and its time/space complexity out loud before you optimize. Handle the edge cases (empty input, duplicates, overflow), and say why you chose this over the brute force. Green tests are the floor, not the grade.

0:00 of about 38 min
InputExpectedGot
[[[0,4,9],[4,0,3],[9,3,0]],12,[]]2not run yetsample
[[[0,4,9],[4,0,3],[9,3,0]],12,[1]]1not run yetsample
[[[0,4,9],[4,0,3],[9,3,0]],6,[]]0not run yetsample