Design Algorithms for Custom Data Routing | Dataford Interview Questions

How would you design algorithms for custom data routing?

Implement a minimum-cost routing algorithm for a directed network. Each link is [start, end, latency, capacity]. Route exactly units from source to sink with minimum total latency, treating parallel links between the same endpoints as distinct alternatives that can each carry at most one unit. Return -1 if routing is impossible.

Function: def route_data(nodes, links, source, sink, units):

Return an integer total latency. Nodes are integer identifiers, and all latencies and capacities are nonnegative integers.

Constraints

1 <= len(nodes) <= 100
0 <= len(links) <= 500
1 <= units <= 10000
Each link has the form [start, end, latency, capacity]
start and end are values in nodes
0 <= latency <= 10^6
0 <= capacity <= 10^4

Function Signature

def route_data(nodes, links, source, sink, units):

Your question is Design Algorithms for Custom Data Routing. 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