Interview Question... Trying to work it out, but couldn't get an efficient solution

I am stuck in one interview question.. The question is,

*given two arrays A and B. A has integers unsorted. B has the same length as A and its values are in the set {-1,0,1}

you have to return an array C with the following processing on A.

if B[i] has 0 then C[i] must have A[i]

if B[i] has -1 then A[i] must be in C within the sub array C[0] - C[i-1] ie. left subarray

if B[i] has 1 then A[i] must be in C within the sub array C[i+1] - C[length(A)] ie right subarray.

if no such solution exists then printf("no solution");*

I applied following logics:-

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开发者_JS百科++;
    }

    c[indMinus1] = a[indPlus1];
    c[indPlus1] = a[indMinus1];
    b[indMinus1] = 0;
    b[indPlus1] = 0;
    indMinus1--;
    indPlus1++;
}

But this will not going to work,, for some cases like {1,2,3} >> {1,-1,-1}... One output is possible i.e. {2,3,1};

Please help.... does their any algorithm technique available for this problem?

Correct Solution Code

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;
}

I suggest the following algorithm:
1. Initially consider all C[ i ] as empty nests.
2. For each i where B[ i ] = 0 we put C[ i ] = A[ i ]
3. Go through array from left to right, and for each i where B[ i ] = -1 put
C[ j ] = A[ i ], where 0 <= j < i is the smallest index for which C[ j ] is still empty. If no such index exists, the answer is impossible.
4. Go through array from right to left, and for each i where B[ i ] = 1 put
C[ j ] = A[ i ], where i < j < n is the greatest index for which C[ j ] is still empty. If no such index exists, the answer is impossible.

Why do we put A[ i ] to the leftmost position in step 2 ? Well, we know that we must put it to some position j < i. On the other hand, putting it leftmost will increase our changes to not get stucked in step 3. See this example for illustration:

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

Initially C is empty: C:[ _, _, _ ]
We have no 0-s, so let's pass to step 2.
We have to choose whether to place element A[ 2 ] to C[ 0 ] or to C[ 1 ].
If we place it not leftmost, we will get the following situation:
C: [ _, 3, _ ]
And... Oops, we are unable to arrange elements A[ 0 ] and A[ 1 ] due to insufficient place :(
But, if we put A[ 2 ] leftmost, we will get
C: [ 3, _, _ ], And it is pretty possible to finish the algorithm with
C: [ 3, 1, 2 ] :)

Complexity:
What we do is pass three times along the array, so the complexity is O(3n) = O(n) - linear.

Further example:

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

Let's go through the algorithm step by step:
1. C: [ _, _, _ ]
2. Empty, because no 0-s in B
3. Putting A[ 1 ] and A[ 2 ] to leftmost empty positions:

C: [ 2, 3, _ ]

4. Putting A[ 0 ] to the rightmost free (in this example the only one) free position:

C: [ 2, 3, 1 ]

Which is the answer.

Source code:

#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;
}

Far too much time spent: ;-)

#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]);
    }
}

This can be reduced to network flow. Here is how to construct the gadget:

1. For every element, i, of A, create a node a_i, and add a unit capacity edge from the source to a_i.

2. For every element, i, of C, create a node c_i, and add a unit capacity edge from c_i to the sink.

3. For all 0 values in B with index i, add an edge from a_i to c_i, again with unit capacity.

4. For all -1 values in B with index i, add an edge from a_j to c_i, where 0<= j < i.

5. For all 1 in B with index i, add an edge from a_j to c_i where i < j < n.

Example gadget:

   a_0 *----* c_0
      / \    \
     /   \    \
    /     |    \
   /  a_1 | c_1 \
S *----*  | *----* T
   \    \ \/    /
    \    \/\   /
     \   /\ | /
      \ /  \|/
       *    *
      a_2   c_2


  B = [ 0, 1, -1]

A maximal flow in this network with capacity = n corresponds to an assignment of a's to c's. To get the permutation, just compute the min-cut of the network.

Here's a solution with a single outer pass. As i goes from 0 to n-1, j goes to n-1 to 0. The l and r indexes point to the first available "flex" spot (where b[i] != 0). If at any point l passes r, then there are no more free flex spots, and the next time b[i] != 0 the outer loop will break prematurely with a "no solution."

It seemed to be accurate, but if it does fail on some cases, then adding a few more conditions to the loops that advance the flex indexes should be sufficient to fix it.

There is an extraneous assignment that will happen (when b[i] == 0, c will be set by both i and j), but it is harmless. (Same goes for the l > r check.)

#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;
}