Katkat
Back

Find minimum cycle cost per node

MicrosoftSoftware Engineer · Online Assessment
HardSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

This problem tests your ability to identify cycles within a weighted directed graph and compute the ratio of cycle cost to node count efficiently.

Problem Statement

You are given a directed graph with n nodes labeled 0 to n-1 and a list of directed edges, where each edge (u, v) has a weight w.

A cycle in this graph is a path that starts and ends at the same node. The cost of a cycle is the sum of the weights of all edges forming the cycle. The "density" of a cycle is defined as the total cost of the cycle divided by the number of nodes in that cycle.

Your task is to find the minimum density among all possible cycles in the graph. If no cycle exists, return -1.

Function Signature

def min_cycle_density(n: int, edges: list[tuple[int, int, int]]) -> float:

Constraints

  • `2 <= n 1 -> 2 -> 0. Cost = 10 + 5 + 3 = 18. Nodes = 3. Density = 18/3 = 6.0.

Example 2:

  • Input: n = 4, edges = [(0, 1, 2), (1, 0, 2), (2, 3, 10), (3, 2, 20)]
  • Output: 2.0
  • Explanation: Two cycles: (0, 1) with density (2+2)/2 = 2.0, and (2, 3) with density (10+20)/2 = 15.0. The minimum is 2.0.

Edge Cases

  • Graphs with multiple disconnected components.
  • Graphs where no cycles exist.
  • Self-loops (a cycle of length 1).

Hints

Hint 1

Consider using binary search on the possible density value `x`.

Hint 2

For a fixed value `x`, transform the edge weights to `w' = w - x`. A cycle with density `d <= x` exists if and only if there is a cycle in the graph with a total weight `<= 0` using the new weights `w'`.

Hint 3

Use the Bellman-Ford algorithm or the Floyd-Warshall algorithm to detect if a cycle with a non-positive sum exists after the weight transformation.

Follow-up questions

  • How would the time complexity change if we used the Bellman-Ford algorithm versus the Floyd-Warshall algorithm for cycle detection?
  • What modifications are necessary if the graph contains negative edge weights initially?
  • How would you identify the specific nodes that constitute the cycle with the minimum density once the optimal density value is found?