Throughput Bottleneck Identification | Dataford Interview Questions

Identify the bottlenecks in this distributed system diagram and propose a strategy to increase throughput.

Represent the diagram as a directed graph whose edges have capacities. Implement the function below to compute maximum throughput and identify the input edges forming a minimum cut. The recommended strategy is to increase capacity on one or more returned bottleneck edges.

edges contains [from_node, to_node, capacity] entries. Return a dictionary with max_throughput and zero-based bottleneck_edges.

Constraints

2 <= node_count <= 500
1 <= len(edges) <= 5000
0 <= from_node, to_node < node_count
from_node != to_node
1 <= capacity <= 10^9
source != sink
Parallel directed edges are allowed
All capacities are integers

Function Signature

def analyze_network(node_count, edges, source, sink):

Your question is Throughput Bottleneck Identification. 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

Identify the bottlenecks in this distributed system diagram and propose a strategy to increase throughput.

edges contains [from_node, to_node, capacity] entries. Return a dictionary with max_throughput and zero-based bottleneck_edges.

Constraints

2 <= node_count <= 500
1 <= len(edges) <= 5000
0 <= from_node, to_node < node_count
from_node != to_node
1 <= capacity <= 10^9
source != sink
Parallel directed edges are allowed
All capacities are integers

Function Signature

def analyze_network(node_count, edges, source, sink):

Your question is Throughput Bottleneck Identification. 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.