Google | Onsite | Network flow for the matrix with given row and column sums
Anonymous User
5520

You are given a library called "Calculate flow" for a directed graph.
Every directed edge of the graph has a flow value F and a capacity C. Each node of graph has a value +/- V, and incoming flow/s and outgoing flow/s. The rule is that

  1. Value at node i + Summation of flows incoming into node i == Summation of flows outgoing from node i
  2. For any edge, the flow value is less than capacity of the edge

The library is as follows

CalculateFlow {
   addEdge(int startNode, int endNode, int capacity);
   addNode(int node, int value);
   solve();  // calculates flow values for all edges
}

If you build a graph using the addEdge and addNode APIs, the solve() function of this library can calculate a set of flow values for the directed graph that satisfy the above conditions.
Use this library to generate a matrix whose rowSums and colSums are provided for all rows and columns. There may be multiple matrices possible, but you need to only generate one.

image

Possible answer

1  2
3  5

Note that the graph and matrix to be generated shown above are just examples, and they do not have strong correlation between number of edges and vertices vs number of rows/cols, for this particular example. It is up to the candidate to figure out how many vertices and edges will be needed to generate a M x N matrix, and how to construct the graph.

Comments (9)