Facebook Interview Question
Software Engineer / Developersint [] arr = {0,0,0,0,2,1,2,0,2,1,2,1,2,0,1,0,1,0,2,0,1};
int pointer1 = 0,pointer2 = arr.length - 1;
for(int i = 0;i<pointer2;)
{
if(arr[i]==0)
{
if(i == pointer1)
{//do this to skip the worst case
i++;
pointer1++;
}else
{
arr[i] = arr[pointer1];
arr[pointer1++] = 0;
}
}else if( arr[i] == 2 )
{
arr[i] = arr[pointer2];
arr[pointer2--] = 2;
}else
{
i++;
}
}
System.out.println(Arrays.toString(arr));
<pre lang="" line="1" title="CodeMonkey54578" class="run-this">/*
My algorithm:
1. iterate thru array and count number of 0,1,2
2. based on the counts update the new array as we know the elements in the array are just 0,1,2 using this peice of information form the solution.
*/
public class ArrangeInOrder {
public static void main(String args[])
{
int[] inputArray={0,1,2,0,1,2,2,2,2,1,0,0,0,0};
System.out.println("Initial array is: ");
display(inputArray);
inputArray=Rearrange(inputArray);
System.out.println("ordered array is: ");
display(inputArray);
}
private static void display(int[] inputArray) {
for(int ii=0;ii<inputArray.length;ii++)
{
System.out.println(inputArray[ii]);
}
}
private static int[] Rearrange(int[] inputArray) {
int countZeros=0;
int countOnes=0;
int countTwos=0;
int i= 0;
int j= 0;
int k=0;
for(int ii=0;ii<inputArray.length;ii++)
{
if(inputArray[ii] ==0)
{
countZeros++;
}
if(inputArray[ii] ==1)
{
countOnes++;
}
if(inputArray[ii] ==2)
{
countTwos++;
}
}
System.out.println("zero =" +countZeros + " and ones: "+countOnes+ " and two's: "+countTwos);
for(i=0;i<countZeros;i++)
{
inputArray[i]=0;
System.out.println("entering at location: "+i +" value= 0");
}
System.out.println("i is-----: "+i);
for(j=i;j<countOnes+i;j++)
{
inputArray[j]=1;
System.out.println("entering at location: "+j +" value= 1");
}
System.out.println("j is-----: "+j);
for(k=j;k<countTwos+j;k++)
{
System.out.println("entering at location: "+k +" value= 2");
inputArray[k]=2;
}
System.out.println("k is-----: "+k);
return inputArray;
}
}
</pre>
Including the three counts into an array will produce shorter and cleaner code.
----------------------------------
import java.util.Arrays;
public class SortOutZeroTwoThree {
public static void rearrange(int[] arr) {
int[] counts = { 0, 0, 0 };
for (int i : arr) {
++counts[i];
}
int index = 0;
for (int i = 0; i < counts.length; ++i) {
while (counts[i]-- > 0) {
arr[index++] = i;
}
}
}
public static void main(String[] args) {
int[] arr = { 0, 1, 2, 1, 0, 2, 1, 2, 0, 1, 1 }; System.out.println(Arrays.toString(arr));
rearrange(arr); System.out.println(Arrays.toString(arr));
}
}
import java.util.Arrays;
public class SortOutZeroTwoThree {
public static void rearrange(int[] arr) {
int[] counts = { 0, 0, 0 };
for (int i : arr) {
++counts[i];
}
int index = 0;
for (int i = 0; i < counts.length; ++i) {
while (counts[i]-- > 0) {
arr[index++] = i;
}
}
}
public static void main(String[] args) {
int[] arr = { 0, 1, 2, 1, 0, 2, 1, 2, 0, 1, 1 };
System.out.println(Arrays.toString(arr));
rearrange(arr);
System.out.println(Arrays.toString(arr));
}
}
This is a special case of quick sort, which can be done efficiently in-place and by going through the array only once.
void rearrange(int *arr, int size)
{
if (NULL == arr || size <= 0) return;
int head = 0;
int tail = size-1;
int idx = 0;
while (idx <= tail) {
if (arr[idx] == 0) {
arr[head++] = 0;
arr[idx++] = 1;
} else if (arr[idx] == 1)
idx++;
else
swap(arr+(tail--), arr+idx);
}
}
hi,
you have written the code but there should be some change then it will work..
see in this for loop
for(i=0;i<size;i++)
{
if(i==0)
n1++;
else if(i==1)
n2++;
else
n3++;
}
in if loop you are not checking for element array for that you should write code like this
for(i=0;i<size;i++)
{
if(a[i]==0)
n1++;
else if(a[i]==1)
n2++;
else
n3++;
}
public static void dutchFlag(int[] array)
{
int start = 0;
int end = array.length - 1;
int cursor = start;
while (cursor < end)
{
int current = array[cursor];
if (current == 1)
{
swap(array, cursor, start);
start++;
cursor++;
}
else if (current == 3)
{
swap(array, cursor, end);
end--;
}
else
{
cursor++;
}
}
}
- ashot madatyan May 04, 2012