FastPrepMaximum-Weight Bipartite Matching

Maximum-Weight Bipartite Matching

Google logoGoogle● HardNEW GRADONSITE INTERVIEW
Learn

Problem statement

A rectangular matrix weights describes a bipartite graph. Row i is a left vertex and column j is a right vertex. A non-negative entry is the weight of edge (i,j); -1 means the edge is absent.

Choose edges of maximum total weight so that no vertex is used more than once. Vertices may remain unmatched. Return the maximum total weight as a signed 64-bit integer.

Function

maximumMatchingWeight(weights: int[][]) → long

Examples

Example 1

weights = [[5,1],[4,7]]return = 12

Match row 0 to column 0 and row 1 to column 1.

Example 2

weights = [[9,8,7],[6,-1,5]]return = 14

Choose weights 8 and 6 using distinct columns.

Example 3

weights = [[-1,-1],[3,-1]]return = 3

Only one available edge is useful; the other row stays unmatched.

Constraints

  • 0 <= rows <= 50.
  • 0 <= columns <= 15.
  • Every entry is -1 or lies in [0,10^9].

More Google problems

See Google hiring insights
public long maximumMatchingWeight(int[][] weights) {
    // Write your code here.
}
weights[[5,1],[4,7]]
expected12
Checking account…