## Amazon Interview Question

Software Engineer / Developerspublic class array {

public static void main(String[] args) {

int arr[] = {1,0,0,0,0,1,1,0,0,1,1,0,0,0,0};

int noOfZeros = 0;

for(int i =0 ; i<arr.length;i++) {

if(arr[i] == 0) {

noOfZeros++;

}

}

for(int i =0 ; i<noOfZeros;i++) {

arr[i] = 0;

}

for(int i = noOfZeros ; i<arr.length;i++) {

arr[i] = 1;

}

for(int i = 0 ; i<arr.length;i++) {

System.out.print(arr[i] + " ");

}}}

```
public class array {
public static void main(String[] args]){
int arr[] = {1,0,0,0,0,0,1,1,0,0,1,1,0,0,0,0};
int i = 0;
int j = arr.length() - 1;
while ( i < j ) {
if ( arr[i] != 1 ) {
i++;
} else if ( arr[j] != 0 ) {
j++;
} else {
arr[i] = 0;
arr[j] = 1;
i++; j++;
```

}

use the idea from quick sort can solve it

```
void sortZeroOne( int [] v, int len )
{
int firstOne = 0;
for ( int i = 0; i < len - 1; i++ ) {
if ( v[i] == 0 ) {
if ( i != firstOne ) {
swap( v[i], v[firstOne] );
}
firstOne++;
}
}
}
```

}

#include<stdio.h>

int main()

{

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

int len = 0, i = 0, j = 0;

len = (sizeof(a)/sizeof(int));

j = (len - 1);

for(;i<j;)

{

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

{

a[i++] = 0;

a[j--] = 1;

}

else if(a[i] == 0)

{

i++;

}

else if(a[j] == 1)

{

j--;

}

}

for(i=0;i<len;i++)

printf("Value: %d\n", a[i]);

return 0;

}

1) Count the number of 0s. Let count be C.

2) Once we have count, we can put C 0s at the beginning and 1s at the remaining n – C positions in array.

Time Complexity: O(n)

The method 1 traverses the array two times. Method 2 does the same in a single pass.

Maintain two indexes. Initialize first index left as 0 and second index right as n-1.

Do following while left < right

a) Keep incrementing index left while there are 0s at it

b) Keep decrementing index right while there are 1s at it

c) If left < right then exchange arr[left] and arr[right]

And interviewer liked the first approach but asked me other ways around.he was very helpful

<pre lang="java" line="1" title="CodeMonkey91211" class="run-this">/*

* To change this template, choose Tools | Templates

* and open the template in the editor.

*/

package subseq;

public class Main {

public static void main(String[] args) {

//Given an array of 0s and 1s , in O(n) time and inplace,

//make all the 0s in one side and all the 1s in other.

int num[] = {1,1,1,0,0,0,0,1};

int zero = 0;

for(int i=0;i<num.length;i++)

{

if(num[i]==0)

{

zero++;

}

}

for(int j = 0,k=zero;j<num.length;j++)

{

if(zero>0)

{

System.out.println("0");

zero--;

}

else

{

System.out.println("1");

}

}

}

}

</pre><pre title="CodeMonkey91211" input="yes">

</pre>

I reached the solution, but it took me sometime,the interviewer was very helpful.But I don't think I was fast enuf..

- Anonymous August 23, 2010