## Goldman Sachs Interview Question

Developer Program EngineersYour algorithm is right, but it would take O(N) time. It's not possible to do in O(N/2) time. Only if array contains N/2 ones and N/2 zeros.

m@}{, that statement is complete nonsense. O(N) and O(N/2) specify the same set of functions.

int a[10] = {0,1,1,1,0,1,0,0,1,0};

int y = 0;

int l = 4;

for(int i = 0, int n = 9;i < n;)

{

cout << "Execution " << y++ << endl;

if((a[i] == 0) && (a[n] == 1))

{

l = a[i];

a[i] = a[n];

a[n] = l;

i++;

n--;

// k--;

}

else if((a[i] == 1) && (a[n] == 1))

{

i++;

l = a[i];

a[i] = a[n];

a[n] = l;

i++;

}

else if((a[i] == 0) && (a[n] == 0))

{

n--;

l=a[n];

a[n]=a[i];

a[i]=l;

n--;

}

else

{

n--;

i++;

}

}

int[] input = new int[] { 1,0,0,1,1,0,0,1};

int i = 0, j = input.Length - 1;

while (i <= j)

{

if (input[i] == 1 && input[j] == 0)

{

i++; j--;

}

else if (input[i] == 0 && input[j] == 1)

{

input[i] = 1;

input[j] = 0;

i++; j--;

}

else if (input[i] == 0 && input[j] == 0)

{

j--;

}

else if (input[i] == 1 && input[j] == 1)

{

i++;

}

}

//considering no. of 0 and 1s in array are same it will take o(n/2) time

```
int[] a = {0, 1, 1, 0, 0, 0, 0, 1, 1, 1};
int i = 0;
int j = a.length - 1;
int temp = 0;
do {
if (a[i] == 0 && a[j] == 1) {
temp = a[i];
a[i] = a[j];
a[j] = temp;
i++;
j--;
}
if (a[i] == 1) {
i++;
}
if (a[j] == 0) {
j--;
}
} while (i < j);
```

int i = 0,j=9;

- Anonymous April 28, 2011while(i<j){

if(a[i]==0 && a[j]==1){

a[j]=0;

a[i] =1;

i++;

j--;

}else{

if(a[i]==0)

j--;

else

i++;

}

}