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):

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.

1. What is the smallest size of "GoodConfig" i.e. least number of lasers we can turn on till kill all evil cells?

2. 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.