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

Viewed 1248

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

    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;
}
4 Answers
Related