Amazon Interview Question
Software Engineer / DevelopersCountry: 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--;
}
}
}