CareerCup

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

public 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] + " ");
}}}

Will the above solution work for this kind of problem

Was the interviewer satisfied with this solution or does this need to be further optimised??

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

void ArrangeZerosAndOnes(char arr[], int N)
{
	int i=0, j= N-2;
	while(i<j)
	{
		while(arr[i]=='0')
			i++;
		while(arr[j]=='1')
			j--;

		arr[j--]='1';
		arr[i++]='0';
	}

	return ;
}

In Groovy

def sortArray(int[] a) {
    int zeroidx = -1;
    for (int i = 0; i < a.length; i++) {
        if (a[i] == 0 && i != ++zeroidx) {
            a[zeroidx] = 0;
            a[i] = 1
        }
    }
    return a
}

println sortArray([0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0] as int[])

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

only 1 pass of quick sort

static void Group0sAnd1s(int[] a)
{
int i = 0;
int j = a.Length - 1;

while (i < j)
{
while (i < a.Length && a[i] == 0)
i++;

while (a[j] == 1 && j >= 0)
j--;

if (i < j && i < a.Length && j >= 0)
{
int t = a[i];
a[i] = a[j];
a[j] = t;
}
}
}

This works...Do you see a case which can break this code?

void func(int a[], int n)
{
int left = a[0];
int i =0 ;int j; int temp;

for(j=1;j<n;j++)
{
if(a[j]!=left && a[j-1]==left)
i++;
if(a[j] == left && i<j)
{
temp = a[i];
a[i] = a[j];
a[j]=temp;
i++;
}
}
return;
}


}