algorithm - Entrevista a Microsoft: transformando una matriz

matrix bit-manipulation

Question

Dada una matriz de tamaño nxm rellena con 0''s y 1''s.

p.ej:

1 1 0 1 0

0 0 0 0 0

0 1 0 0 0

1 0 1 1 0

si la matriz tiene 1 en (i, j), llene la columna j y la fila i con 1

es decir, obtenemos:

1 1 1 1 1

1 1 1 1 0

1 1 1 1 1

1 1 1 1 1

Complejidad requerida: O (n * m) tiempo y O (1) espacio

NOTA: no está permitido almacenar nada excepto ''0'' o ''1'' en las entradas de la matriz

Arriba hay una pregunta de entrevista de Microsoft.

Pensé por dos horas ahora. Tengo algunas pistas pero no puedo continuar.

De acuerdo. La primera parte importante de esta pregunta es que, Even using a straight forward brute-force way , no se puede resolver fácilmente.

Si solo utilizo dos bucles para recorrer cada celda de la matriz y cambiar la fila y la columna correspondientes, no se puede hacer, ya que la matriz resultante debe basarse en la matriz de origen.

Por ejemplo, si veo a[0][0] == 1 , no puedo cambiar la row 0 y la column 0 a 1 , porque eso afectará a la row 1 ya que la row 1 no tiene 0 originalmente.

Lo segundo que noté es que si una fila r contiene solo 0 y una columna c contiene solo 0 , entonces a[r][c] debe ser 0 ; para cualquier otra posición que no esté en este patrón debe ser 1 .

Luego surge otra pregunta: si encuentro una fila y una columna de este tipo, ¿cómo puedo marcar la celda correspondiente a[r][c] como special , ya que es 0?

Mi intuición es que debería usar algún tipo de operaciones de bits en esto. O para cumplir con la complejidad requerida, tengo que hacer algo como After I take care of a[i][j], I should then proceed to deal with a[i+1][j+1], instead of scan row by row or column by column

Incluso para la fuerza bruta sin considerar la complejidad del tiempo, no puedo resolverlo con las otras condiciones.

¿Alguien tiene una pista?

Solución: versión de Java

@japreiss ha respondido esta pregunta y su respuesta es inteligente y correcta. Su código está en Python, y ahora le doy la versión de Java. Todos los créditos van a @japreiss

public class MatrixTransformer {

    private int[][] a;
    private int m;
    private int n;

    public MatrixTransformer(int[][] _a, int _m, int _n) {
        a = _a;
        m = _m;
        n = _n;
    }

    private int scanRow(int i) {
        int allZero = 0;
        for(int k = 0;k < n;k++)
            if (a[i][k] == 1) {
                allZero = 1;
                break;
            }

        return allZero;
    }

    private int scanColumn(int j) {
        int allZero = 0;
        for(int k = 0;k < m;k++)
            if (a[k][j] == 1) {
                allZero = 1;
                break;
            }

        return allZero;
    }

    private void setRowToAllOnes(int i) {
        for(int k = 0; k < n;k++)
            a[i][k] = 1;
    }

    private void setColToAllOnes(int j) {
        for(int k = 0; k < m;k++)
            a[k][j] = 1;
    }

//  # we''re going to use the first row and column
//  # of the matrix to store row and column scan values,
//  # but we need aux storage to deal with the overlap
//  firstRow = scanRow(0)
//  firstCol = scanCol(0)
//
//  # scan each column and store result in 1st row - O(mn) work



    public void transform() {
        int firstRow = scanRow(0);
        int firstCol = scanColumn(0);


        for(int k = 0;k < n;k++) {
            a[0][k] = scanColumn(k);
        }

        // now row 0 tells us whether each column is all zeroes or not
        // it''s also the correct output unless row 0 contained a 1 originally

        for(int k = 0;k < m;k++) {
            a[k][0] = scanRow(k);
        }

        a[0][0] = firstCol | firstRow;

        for (int i = 1;i < m;i++)
            for(int j = 1;j < n;j++)
                a[i][j] = a[0][j] | a[i][0];



        if (firstRow == 1) {
            setRowToAllOnes(0);
        }

        if (firstCol == 1) 
            setColToAllOnes(0);
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i< m;i++) {
            for(int j = 0;j < n;j++) {
                sb.append(a[i][j] + ", ");
            }
            sb.append("/n");
        }

        return sb.toString();
    }
    /**
     * @param args
     */
    public static void main(String[] args) {
        int[][] a = {{1, 1, 0, 1, 0}, {0, 0, 0, 0, 0},{0, 1, 0, 0, 0},{1, 0, 1, 1, 0}};
        MatrixTransformer mt = new MatrixTransformer(a, 4, 5);
        mt.transform();
        System.out.println(mt);
    }

}

Answer 1

Aquí hay otra intuición que da un algoritmo limpio y simple para resolver el problema.

Un algoritmo inicial utilizando el espacio O (n).

Por ahora, ignoremos la restricción de memoria O (1). Supongamos que puede utilizar la memoria O (n) (si la matriz es m × n). Eso facilitaría mucho este problema y podríamos usar la siguiente estrategia:

• Crea una matriz booleana con una entrada por columna.
• Para cada columna, determine si hay algún 1 en la columna y almacene esa información en la entrada de la matriz correspondiente.
• Para cada fila, establezca esa fila para que sea todo 1 si hay 1 en la fila.
• Para cada columna, configure esa columna para que sea toda 1 si la entrada de la matriz correspondiente está establecida.

Como ejemplo, considere esta matriz:

1 1 0 1 0
0 0 0 0 0
0 1 0 0 0
1 0 1 1 0

Comenzaríamos creando y rellenando la matriz auxiliar, que se puede hacer en el tiempo O (mn) visitando cada columna de una en una. Esto se muestra aquí:

1 1 0 1 0
0 0 0 0 0
0 1 0 0 0
1 0 1 1 0

1 1 1 1 0  <--- aux array

A continuación, iteramos a través de las filas y rellenamos cada una de ellas si contiene algún 1. Esto da este resultado:

1 1 1 1 1
0 0 0 0 0
1 1 1 1 1
1 1 1 1 1

1 1 1 1 0  <--- aux array

Finalmente, completamos cada columna con 1 si la matriz auxiliar tiene un 1 en esa posición. Esto se muestra aquí:

1 1 1 1 1
1 1 1 1 0
1 1 1 1 1
1 1 1 1 1

1 1 1 1 0  <--- aux array

Entonces, hay un problema: ¡esto usa O (n) espacio, que no tenemos! Entonces, ¿por qué incluso ir por esta ruta?

Un algoritmo revisado utilizando el espacio O (1).

Resulta que podemos usar un truco muy lindo para ejecutar este algoritmo utilizando el espacio O (1). Necesitamos una observación clave: si cada fila contiene al menos un 1, entonces toda la matriz se convierte en 1. Por lo tanto, comenzamos por ver si este es el caso. Si lo es, ¡genial! Hemos terminado

De lo contrario, debe haber alguna fila en la matriz que sea todos 0. Como esta fila es de 0, sabemos que en el paso "rellenar cada fila que contiene un 1 con 1", la fila no se completará. Por lo tanto, podemos usar esa fila como nuestra matriz auxiliar.

Veamos esto en acción. Comience con esto:

1 1 0 1 0
0 0 0 0 0
0 1 0 0 0
1 0 1 1 0

Ahora, podemos encontrar una fila con todos los 0 en ella y usarla como nuestra matriz auxiliar:

1 1 0 1 0
0 0 0 0 0  <-- Aux array
0 1 0 0 0
1 0 1 1 0

Ahora completamos la matriz auxiliar mirando cada columna y marcando cuáles contienen al menos un 1:

1 1 0 1 0
1 1 1 1 0  <-- Aux array
0 1 0 0 0
1 0 1 1 0

Es perfectamente seguro rellenar los 1 aquí porque sabemos que se van a completar de todos modos. Ahora, para cada fila que contiene un 1, a excepción de la fila de la matriz auxiliar , completamos esas filas con 1:

1 1 1 1 1
1 1 1 1 0  <-- Aux array
1 1 1 1 1
1 1 1 1 1

Omitimos la matriz auxiliar porque inicialmente era todo 0, por lo que normalmente no se rellenaría. Finalmente, completamos cada columna con un 1 en la matriz auxiliar con 1, dando este resultado final:

1 1 1 1 1
1 1 1 1 0  <-- Aux array
1 1 1 1 1 
1 1 1 1 1

Hagamos otro ejemplo. Considere esta configuración:

1 0 0 0
0 0 1 0
0 0 0 0
0 0 1 0

Comenzamos encontrando una fila que es todo ceros, como se muestra aquí:

1 0 0 0
0 0 1 0
0 0 0 0 <-- Aux array
0 0 1 0

A continuación, rellenemos esa fila marcando columnas que contengan un 1:

1 0 0 0
0 0 1 0
1 0 1 0 <-- Aux array
0 0 1 0

Ahora, rellene todas las filas que contienen un 1:

1 1 1 1
1 1 1 1
1 0 1 0 <-- Aux array
1 1 1 1

A continuación, rellene todas las columnas que contengan un 1 en la matriz auxiliar con 1. ¡Esto ya está hecho aquí, y tenemos nuestro resultado!

Como otro ejemplo, considere esta matriz:

1 0 0
0 0 1
0 1 0

Cada fila aquí contiene al menos un 1, así que simplemente rellenamos la matriz con unos y estamos listos.

Finalmente, probemos este ejemplo:

0 0 0 0 0
0 0 0 0 0
0 1 0 0 0
0 0 0 0 0
0 0 0 1 0

Tenemos muchas opciones para arreglos auxiliares, así que vamos a elegir la primera fila:

0 0 0 0 0 <-- aux array
0 0 0 0 0
0 1 0 0 0
0 0 0 0 0
0 0 0 1 0

Ahora, completamos la matriz auxiliar:

0 1 0 1 0 <-- aux array
0 0 0 0 0 
0 1 0 0 0
0 0 0 0 0
0 0 0 1 0

Ahora, llenamos las filas:

0 1 0 1 0 <-- aux array
0 0 0 0 0 
1 1 1 1 1
0 0 0 0 0
1 1 1 1 1

Ahora, rellenamos las columnas basadas en la matriz auxiliar:

0 1 0 1 0 <-- aux array
0 1 0 1 0 
1 1 1 1 1
0 1 0 1 0
1 1 1 1 1

¡Y hemos terminado! Todo funciona en tiempo O (mn) porque nosotros

• Haga el trabajo O (mn) para encontrar la matriz auxiliar, y posiblemente el trabajo O (mn) inmediatamente si no existe uno.
• Haga el trabajo O (mn) para completar la matriz auxiliar.
• Trabaje O (mn) para completar filas que contengan 1s.
• Trabaje O (mn) para completar columnas que contengan 1s.

Además, solo usa espacio O (1), ya que solo necesitamos almacenar el índice de la matriz auxiliar y suficientes variables para hacer bucles sobre la matriz.

EDITAR : Tengo una implementación Java de este algoritmo con comentarios que lo describen en detalle disponible en mi sitio personal. ¡Disfrutar!

¡Espero que esto ayude!

Answer 2

Aquí hay una solución en pseudocódigo de Python que utiliza 2 bool adicionales de almacenamiento. Creo que está más claro de lo que podría hacer en inglés.

def scanRow(i):
    return 0 if row i is all zeroes, else 1

def scanColumn(j):
    return 0 if col j is all zeroes, else 1

# we''re going to use the first row and column
# of the matrix to store row and column scan values,
# but we need aux storage to deal with the overlap
firstRow = scanRow(0)
firstCol = scanCol(0)

# scan each column and store result in 1st row - O(mn) work
for col in range(1, n):
    matrix[0, col] = scanColumn(col)

# now row 0 tells us whether each column is all zeroes or not
# it''s also the correct output unless row 0 contained a 1 originally

# do the same for rows into column 0 - O(mn) work
for row in range(1, m):
    matrix[row, 0] = scanRow(row)

matrix[0,0] = firstRow or firstCol

# now deal with the rest of the values - O(mn) work
for row in range(1, m):
    for col in range(1, n):
        matrix[row, col] = matrix[0, col] or matrix[row, 0]


# 3 O(mn) passes!

# go back and fix row 0 and column 0
if firstRow:
    # set row 0 to all ones

if firstCol:
    # set col 0 to all ones

Answer 3

Otra solución sería escanear la matriz como de costumbre, y en el primer 1 se divide la matriz en 4 cuadrantes. A continuación, establece la línea y la columna en 1 y procesa recursivamente cada cuadrante. Solo asegúrese de configurar las columnas y filas completas, aunque esté escaneando solo un cuadrante.

Answer 4

Suponiendo que la matriz está basada en 0, es decir, el primer elemento está en la matriz [0] [0]

1. Use la primera fila y la primera columna como encabezados de tabla para contener información de columna y fila respectivamente. 1.1 Note el elemento en el tapete [0] [0]. Si es 1, requerirá un manejo especial al final (descrito más adelante)

2. Ahora, comience a escanear la matriz interna desde el índice [1] [1] hasta el último elemento 2.1 Si el elemento en [fila] [col] == 1 luego actualice los datos del encabezado de la tabla como sigue Fila: mat [fila] [0 ] = 1; Columna: mat [0] [col] = 1;

En este punto, tenemos la información completa sobre qué columna y fila se deben establecer en 1

1. De nuevo, comience a escanear la matriz interna comenzando desde mat [1] [1] y configure cada elemento en 1 si la fila o columna actual contiene 1 en el encabezado de la tabla: if ((mat [row] [0] == 1) | | (mat [0] [col] == 1)) luego coloque mat [row] [col] en 1.

En este punto, hemos procesado todas las celdas en la matriz interna y todavía tenemos que procesar el encabezado de la tabla.

1. Procese el encabezado de la tabla Si el mate [0] [0] == 1, configure todos los elementos en la primera columna y la primera fila en 1
2. Hecho

Complejidad de tiempo O (2 * ((n-1) (m-1) + (n + m-1)), es decir, O (2 * n * m - (n + m) + 1), es decir, O (2 * n * m) Espacio O (1)

Ver mi implementación en http://codepad.org/fycIyflw

Answer 5

public void setOnes(int [][] matrix){

    boolean [] row = new boolean [matrix.length]
    boolean [] col = new boolean [matrix[0].length]
    for (int i=0;i<matrix.length;i++){
        for(int j=0;j<matrix[0].length;j++){
            if (matrix[i][j] == 1){
                row[i] = true
                col[j] = true
            }
        }
    }

    for (int i=0;i<matrix.length;i++){
        for(int j=0;j<matrix[0].length;j++){
            if (row[i] || col[j]){
                matrix[i][j] = 1;
            }
        }
    }
}