Reposted from here:
I was asked this in an interview. I am modifying the question a bit to preserve it from being explicitly Googleable but the gist is:
You are given an N x M grid. Some cells in the grid are "evil" (denoted by number 1) and rest are "good" (denoted by 0). You have lasers positioned across each N rows and across each M columns which when turned on kills all cells in their respective row or column e.g. if you have:
LL L1 L2 L3 L4 L5 0 1 0 0 L6 0 1 0 1 L7 0 1 1 0 L8 0 0 0 0
You can turn on either (L2, L3, L4):
LL L1 L2 L3 L4 L5 0 x x x L6 0 x x x L7 0 x x x L8 0 x x x
Or you can turn on (L2, L6, L7):
LL L1 L2 L3 L4 L5 0 x 0 0 L6 x x x x L7 x x x x L8 0 x 0 0
A set of lasers turned-on is called "GoodConfig" iff it kills all evil cells. Note you can always turn on all lasers along a row or column and kill everything and it would be "GoodConfig" but turning on lasers is expensive and killing good cells is bad.
What is the smallest size of "GoodConfig" i.e. least number of lasers we can turn on till kill all evil cells?
What is a "GoodConfig" that minimizes the number of good cells killed?
I realized that part 1 is similar to a step in the Hungarian algorithm but I don't have a good intuition or implementation of it. Part 2 — I have no idea.
For first part: If we consider each row and each column as a node in a graph and there is edge between these nodes if and only if matrix element in corresponding row and column is 1.We can visualize this as bipartite graph.Now,the problem is similar to finding minimum vertex cover in the graph.This is very standard problem you can find more information about it on internet.
For second part maybe we can give weight to this edges on number of minimum good cells that will get killed in selecting that edge..then we can use algorithm for min cost maximum matching.