This is a puzzle offered by HireVue as a challenge to would be programmers and algorithm designers. To my knowledge there is no reward, it's just for fun. And I take great interest in such puzzles.
Suppose we have a matrix with $N$ rows and $M$ columns. The matrix has the entries $0$ and $1$.
We can change the value of an entry from $0$ to $1$ or $1$ to $0$, but when we do, we also change the value of all adjacent entries in a $+$ sign (meaning we change entry to the right, left, above and below). Our goal is that the entire matrix will be zero.
The challenge is to design an algorithm that will change the entire matrix to zero in the minimum amount of steps.
For example:
Suppose we were given $\begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{pmatrix}$. The optimal solution would be:
1) switch state of row $1$ column $4$ to get $\begin{pmatrix} 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1\\ 0 & 0 & 0 & 0 \end{pmatrix}$
2) switch state of row $2$ column $3$ to get $\begin{pmatrix} 0 & 0 & 0 & 1 \\ 0 & 0& 1 & 0\\ 0 & 0 & 1 & 0 \end{pmatrix}$
3) switch state of row $2$ column $4$ to get $\begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & 0& 0 & 1\\ 0 & 0 & 1 & 1 \end{pmatrix}$
4) switch state of row $3$ column $4$ to get $\begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & 0& 0 & 0\\ 0 & 0 & 0 & 0\end{pmatrix}$
We are done. We solved the puzzle optimally in four steps. That however was just a solved example. I am interested in an algorithm that will yield the optimal solution (meaning least number of state switches) regardless of input.
note: We can have more than one $1$ in the matrix we were given. For example the identity matrix or just a matrix full of ones are also valid inputs. If there is no way to make all the entries $0$, the algorithm needs to recognize that as well.
