## Amazon Interview Question

Software Engineer / Developers**Country:**India

**Interview Type:**Written Test

nice solution. Just to save few more operations, we can also add one more check before doing swap operation:

else{

if(a[j]==0){

swap(a[i],a[j]);

}

j--;

}

For input 1001001 :

First time a[i] = 1, a[j] = 1 (last element of the array)

swap(1,1) , put 1 in position 0, so a[0] is 1 again.

How does the code work for this input, please explain

In this approach,lots of unnecessary swaps are being done.. Say I have array as 0,0,1,0,1,1,0,1. Now as per above logic I would swap when i=2 and j=n-1 , but this swap is not required actually(Swapping 1 with 1 doesn't make any sense). So better approach is already posted by amritaansh123 .Please see below that answer.

```
package algo.solutions;
public class Sort0s1s {
public void sort(int[] a)
{
if(a == null || a.length == 1)
{
return;
}
int i=0;
int j = a.length -1;
while(true)
{
while(i < a.length && a[i] == 0)
{
i++;
}
while(j >= 0 && a[j] == 1)
{
j--;
}
if(i>j)
{
return;
}
swap(a,i,j);
}
}
private static void swap(int[] a, int i, int j)
{
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
}
```

o(n)

Another solution

1) Count the number of Zeros

2) Place zeros in the arrays equal to the count and later place all the ones in the array

```
public class ArrayWithZeroesNOne {
public static void main(String[] args){
int []A={1,0,0,1,1,1,0,1,0,0,0,1,1,1,1,1,0,1,0,1,1,0,0,1};
int l=A.length;
int [] b=sortArr(A, l);
for(int i=0; i<l; i++){
System.out.print(b[i]+" ");
}
}
static int[] sortArr(int[]A, int l){
for(int i=0, j=l-1; i<j;){
while(A[i]==0)
i++;
while(A[j]!=0)
j--;
if(i>=j)
break;
int temp=A[i];
A[i]=A[j];
A[j]=temp;
}
return A;
}
}
```

```
int [] sort(int [] arr)
{
for ( int i= 0; i< arr.Length; i++)
{
if (arr[i] != 0)
{
for ( int j = i; j< arr.Length; j++)
{
if( arr[j] == 0) break;
}
if( j< arr.Length)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
else
break;
}
}
}
```

private static int[] Sort(int[] set) {

// TODO Auto-generated method stub

for(int i = 0; i < set.length - 1;){

if(set[i] == 0){

i++;

} else if (set[i] == 1){

for(int j = i + 1; j < set.length; j++){

if (set[j] == 0){

int temp = set[j];

set[j] = set[i];

set[i] = temp;

}

}

i++;

}

}

return set;

}

```
private static int[] Sort(int[] set) {
// TODO Auto-generated method stub
for(int i = 0; i < set.length - 1;){
if(set[i] == 0){
i++;
} else if (set[i] == 1){
for(int j = i + 1; j < set.length; j++){
if (set[j] == 0){
int temp = set[j];
set[j] = set[i];
set[i] = temp;
}
}
i++;
}
}
return set;
}
```

public static void sortArrayWithZeroAndOne(int [] a)

{

if (a.Length == 0)

return;

else

{

//as we know array is of only two types of value zero and one, so creating another array which hold two int

int[] tempArray = new int[2];

for (int i = 0; i < a.Length; i++)

{

tempArray[a[i]]++;

}

for (int i = 0; i < tempArray[0]; i++)

{

a[i] = 0;

}

for (int i = tempArray[0]; i < a.Length; i++)

{

a[i] = 1;

}

foreach (int i in a)

{

Console.Write(i+ ",");

}

}

}

See the simplest and working solution

```
public static void main(String[] args)
{
int[] arr = { 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1 };
sort(arr);
System.out.println(Arrays.toString(arr));
}
private static void sort(final int[] arr)
{
int i = 0, j = arr.length - 1;
while (i < j)
{
while (arr[i] == 0 && i < arr.length)
i++;
while (arr[j] == 1 && j >= 0)
j--;
if (i < j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
```

use strict;

my @arr=qw(0 1 0 1 0 1 1 0 1 1 0 1 0 1 0 0 1 1 0 1);

my ($i,$cnt);

foreach(@arr) {

$cnt++ if ($_ eq 1);

}

print "@arr\n";

print "1's are : $cnt\n0's are : ", (scalar(@arr)-$cnt), "\n";

for (my $i=0; $i<scalar(@arr); $i++) {

$arr[$i] = 0 if ($i < (scalar(@arr) - $cnt));

$arr[$i] = 1 if ($i >= (scalar(@arr) - $cnt));

}

print "@arr\n";

not with strict programming.

Sort or algorithm below for the logic:

i = a[0], j = a[1]

while( (a[j] != 0) && j <= end of array)

{

if( (a[i] == 1)

{

swap(a[i],a[j]);

i++;

}

j++;

}

checked with such strings: 1100101,...

As per logic: j should point to location where array has element with 0.

if a[i] has value 1 than swap the values and do i++;

correct me if i am wrong

@ avikodak

I have written an algorithm with complexity O(n)

-- 1 -- Traverse Array A

-- 2-- For every '1' increase sum by 1 and set A[count-sum] =1 (at the tail of the array)

-- 3-- For every '0' set A[i-sum] =1 (at the rear end of the array)

```
arr = array('0','0','1','0','1','1','0','1','0');
count = sizeof(arr);
sum = 0;
for(i = 0 ; i < count ; i++){
if(!arr[i]){
newArr[i-sum] = 0;
}else{
sum++;
newArr[count-sum] = 1;
}
}
output newArr has ('0','0','0','0','0','1','1','1','1');
```

sort ( int a[ ] ) {

- william November 04, 2012for(int i =0 , j = a.size()-1 ; i< = j ; ){

if ( a[i] == 0 ){

i++;

}

else{

swap(a[i] , a[j] );

j--;

}

}

}