Recently went through Google phone screen. Given a matrix which is filled with 0, 1 and -1.

• -1 represents it's a house position.
• 0 represents you can not pass by this cell.
• 1 represent you can pass by this cell.

You need to connect all the cities by using the 1-cells. Minimize the number of cells you pick to connect all the cities.

When you connect two cells of 1s, It becomes an undirected edge and you can travel this as many times as you want.