Pregunta de la entrevista... Tratando de resolverlo, pero no pudo obtener una solución eficiente

algorithm data-structures

Question

Estoy atrapado en una pregunta de la entrevista. La pregunta es,

* dados dos matrices A y B. A tiene enteros sin clasificar. B tiene la misma longitud que A y sus valores están en el conjunto {-1,0,1}

tienes que devolver una matriz C con el siguiente procesamiento en A.

si B [i] tiene 0, entonces C [i] debe tener A [i]
si B [i] tiene -1, entonces A [i] debe estar en C dentro de la matriz secundaria C [0] - C [i-1], es decir. subarray izquierdo
si B [i] tiene 1, entonces A [i] debe estar en C dentro de la matriz secundaria C [i + 1] - C [longitud (A)], es decir, la matriz secundaria derecha.

si no existe tal solución entonces printf ("no hay solución"); *

Apliqué las siguientes lógicas:

int indMinus1 = n-1;
int indPlus1 = 0;
//while(indPlus1 < n && indMinus1 > 0)
while(indPlus1 < indMinus1)
{
while(b[indMinus1] != -1) {
if(b[indMinus1] == 0)
c[indMinus1] = a[indMinus1];
indMinus1--;
}
while(b[indPlus1] != +1) {
if(b[indPlus1] == 0)
c[indPlus1] = a[indPlus1];
indPlus1++;
}
c[indMinus1] = a[indPlus1];
c[indPlus1] = a[indMinus1];
b[indMinus1] = 0;
b[indPlus1] = 0;
indMinus1--;
indPlus1++;
}

Pero esto no va a funcionar, para algunos casos como {1,2,3} >> {1, -1, -1} ... Una salida es posible, es decir, {2,3,1};

Por favor ayuda ... ¿existe alguna técnica de algoritmo disponible para este problema?

Código de solución correcta

int arrange(int a[], int b[], int c[], int n)
{
for (int i = 0; i < n; ++i) {
if(b[i] == 0)
c[i] = a[i];
}
int ci = 0;
for (int i = 0; i < n; ++i) {
if(b[i] == -1) {
while(c[ci] != 0 && ci < i)
ci ++;
if(c[ci] != 0 || ci >= i)
return -1;
c[ci] = a[i];
ci++;
}
}
for (int i = 0; i < n; ++i) {
if(b[i] == 1) {
while(c[ci] != 0 && ci < n)
ci ++;
if(c[ci] != 0 || ci <= i)
return -1;
c[ci] = a[i];
ci++;
}
}
return 0;
}

Answer 1

Aquí hay una solución con un solo paso exterior. A medida que voy de 0 a n-1 , j va de n-1 a 0 . Los índices l y r apuntan al primer punto "flex" disponible (donde b[i] != 0 ). Si en cualquier punto l pasa r , entonces no hay más puntos de flexión libres, y la próxima vez que b[i] != 0 el bucle externo se romperá prematuramente con "no solución".

Parecía ser preciso, pero si falla en algunos casos, agregar algunas condiciones más a los bucles que hacen avanzar los índices de flexibilidad debería ser suficiente para solucionarlo.

Hay una asignación extraña que sucederá (cuando b[i] == 0 , c se establecerá con i y j ), pero es inofensivo. (Lo mismo ocurre con el cheque l > r ).

#include <stdio.h>
#define EMPTY 0
int main()
{
int a[] = {1, 2, 3};
int b[] = {1, -1, -1};
int c[] = {EMPTY, EMPTY, EMPTY};
int n = sizeof(a) / sizeof(int);
int l = 0, r = n - 1;
int i, j;
/* Work from both ends at once.
* i = 0 .. n-1
* j = n-1 .. 0
* l = left most free "flex" (c[i] != 0) slot
* r = right most free flex slot
*
* if (l > r) then there are no more free flex spots
*
* when going right with i, check for -1 values
* when going left with j, check for 1 values
* ... but only after checking for 0 values
*/
for (i = 0, j = n - 1; i < n; ++i, --j)
{
/* checking i from left to right... */
if (b[i] == 0)
{
c[i] = a[i];
/* advance l to the next free spot */
while (l <= i && c[l] != EMPTY) ++l;
}
else if (b[i] == -1)
{
if (i <= l) break;
c[l] = a[i];
/* advance l to the next free spot,
* skipping over anything already set by c[i] = 0 */
do ++l; while (l <= i && c[l] != EMPTY);
}
/* checking j from right to left... */
if (b[j] == 0)
{
c[j] = a[j];
while (r >= j && c[r] != EMPTY) --r;
}
else if (b[j] == 1)
{
if (j >= r) break;
c[r] = a[j];
do --r; while (r >= j && c[r] != EMPTY);
}
if (l > r)
{
/* there cannot be any more free flex spots, so
advance l,r to the end points. */
l = n;
r = -1;
}
}
if (i < n)
printf("Unsolvable");
else
{
for (i = 0; i < n; ++i)
printf("%d ", c[i]);
}
printf("/n");
return 0;
}

Answer 2

Demasiado tiempo pasado: ;-)

#include <stdint.h>
#include <string.h>
#include <stdio.h>
static int doit(int A[], int B[], int C[], size_t size)
{
size_t first_free = size - 1;
size_t last_free = 0;
for (size_t i = 0; i < size; ++i) {
if (B[i]) {
if (i < first_free) {
first_free = i;
}
if (i >= last_free) {
last_free = i;
}
}
}
for (int i = 0; i < size; ++i) {
if (B[i] < 0) {
if (first_free >= i) {
return 0;
}
C[first_free] = A[i];
first_free = i;
} else if (B[i] == 0) {
C[i] = A[i];
}
}
for (int i = size - 1; i >= 0; --i) {
if (B[i] > 0) {
if (last_free <= i) {
return 0;
}
C[last_free] = A[i];
last_free = i;
}
}
return 1;
}
int a[] = { 1, 2, 3 };
int b[] = { 1, -1, -1 };
int c[sizeof(a) / sizeof(int)];
int main(int argc, char **argv)
{
if (!doit(a, b, c, sizeof(a) / sizeof(int))) {
printf("no solution");
} else {
for (size_t i = 0; i < sizeof(a) / sizeof(int); ++i)
printf("c[%zu] = %d/n", i, c[i]);
}
}

Answer 3

Esto se puede reducir al flujo de la red. Aquí es cómo construir el gadget:

1. Para cada elemento, i, de A, cree un nodo a_i, y agregue un límite de capacidad de la unidad desde la fuente a a_i.

2. Para cada elemento, i, de C, cree un nodo c_i, y agregue un límite de capacidad de la unidad desde c_i al sumidero.

3. Para todos los valores 0 en B con el índice i, agregue un borde de a_i a c_i, nuevamente con capacidad de la unidad.

4. Para todos los valores -1 en B con el índice i, agregue un borde de a_j a c_i, donde 0 <= j <i.

5. Para todo 1 en B con el índice i, agregue un borde de a_j a c_i donde i <j <n.

Ejemplo de gadget:

 a_0 *----* c_0
/ / /
/ / /
/ | /
/ a_1 | c_1 /
S *----* | *----* T
/ / // /
/ /// /
/ // | /
/ / /|/
* *
a_2 c_2
B = [ 0, 1, -1]

Un flujo máximo en esta red con capacidad = n corresponde a una asignación de a''s a c''s. Para obtener la permutación, simplemente calcule el corte mínimo de la red.

Answer 4

Sugiero el siguiente algoritmo:
1. Inicialmente considere todos los C[ i ] como nidos vacíos.
2. Para cada i donde B[ i ] = 0 ponemos C[ i ] = A[ i ]
3. Recorra la matriz de izquierda a derecha , y para cada i donde B[ i ] = -1 ponga
C[ j ] = A[ i ] , donde 0 <= j < i es el índice más pequeño para el que C[ j ] aún está vacío. Si no existe tal índice, la respuesta es imposible.
4. Ir a través de la matriz de derecha a izquierda , y para cada i donde B[ i ] = 1 puesto
C[ j ] = A[ i ] , donde i < j < n es el mayor índice para el que C[ j ] aún está vacío. Si no existe tal índice, la respuesta es imposible.

¿Por qué colocamos A [i] en la posición más a la izquierda en el paso 2? Bueno, sabemos que debemos ponerlo en alguna posición j <i. Por otro lado, si lo pone más a la izquierda, aumentarán nuestros cambios para no quedarnos atascados en el paso 3. Consulte este ejemplo para ver una ilustración:

A: [ 1, 2, 3 ]
B: [ 1, 1,-1 ]

Inicialmente C está vacío: C:[ _, _, _ ]
No tenemos 0-s, así que vamos al paso 2.
Tenemos que elegir si colocar el elemento A[ 2 ] en C[ 0 ] o en C[ 1 ] .
Si no lo colocamos más a la izquierda, obtendremos la siguiente situación:
C: [ _, 3, _ ]
Y ... Vaya, no podemos organizar los elementos A[ 0 ] y A[ 1 ] debido a un lugar insuficiente :(
Pero , si ponemos A [2] a la izquierda, obtendremos
C: [ 3, _, _ ] , Y es bastante posible terminar el algoritmo con
C: [ 3, 1, 2 ] :)

Complejidad :
Lo que hacemos es pasar tres veces a lo largo de la matriz, por lo que la complejidad es O(3n) = O(n) - lineal.

Otro ejemplo:

A: [ 1, 2, 3 ]
B: [ 1, -1, -1 ]

Vayamos a través del algoritmo paso a paso:
1. C: [ _, _, _ ]
2. Vacío, porque no hay 0-s en B
3. Poniendo A[ 1 ] y A[ 2 ] en las posiciones vacías más a la izquierda:

C: [ 2, 3, _ ]

4. Colocar A[ 0 ] en la posición libre más a la derecha (en este ejemplo, la única) libre:

C: [ 2, 3, 1 ]

Cual es la respuesta

Código fuente:

#include <iostream>
#include <string>
#include <vector>
using namespace std;
vector< int > a;
vector< int > b;
vector< int > c;
int n;
bool solve ()
{
int i;
for( i = 0; i < n; ++i )
c[ i ] = -1;
for( i = 0; i < n; ++i )
if( b[ i ] == 0 )
c[ i ] = a[ i ];
int leftmost = 0;
for( i = 0; i < n; ++i )
if( b[ i ] == -1 )
{
for( ; leftmost < i && c[ leftmost ] != -1; ++leftmost ); // finding the leftmost free cell
if( leftmost >= i )
return false; // not found
c[ leftmost++ ] = a[ i ];
}
int rightmost = n - 1;
for( i = n - 1; i >= 0; --i )
if( b[ i ] == 1 )
{
for( ; rightmost > i && c[ rightmost ] != -1; --rightmost ); // finding the rightmost free cell
if( rightmost <= i )
return false; // not found;
c[ rightmost-- ] = a[ i ];
}
return true;
}
int main ()
{
cin >> n;
a.resize(n);
b.resize(n);
c.resize(n);
int i;
for( i = 0; i < n; ++i )
cin >> a[ i ];
for( i = 0; i < n; ++i )
cin >> b[ i ];
if( !solve() )
cout << "Impossible";
else
for( i = 0; i < n; ++i )
cout << c[ i ] << '' '';
cout << endl;
return 0;
}