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